二叉树的下一个节点（C语法）

ゝ一世哀愁。 2022-02-13 19:39 199阅读 0赞

### **二叉树的下一个节点（C语法）** ###

给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左右子树的指针，还有一个指向父节点的指针。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70][]

分析下一个节点位置的可能：

1）如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。即：从右子节点出发一直沿着指向左子节点的指针，就能找到它的下一个节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70 1][]

BinaryTreeNode* GetNext(BinaryTreeNode* pNode){
        if (pNode ==  null){
          return nullptr;
        }
    
        /**
         * 当前节点有右子树，那么下一个节点就是它右子树的最左节点
         */
        BinaryTreeNode* pNext = nullptr;
        if (pNode->m_pRight != nullptr){
          BinaryTreeNode* pRight = pNode->m_pRight;
          while(pRight->m_pLeft != nullptr){
              pRight = pRight->m_pLeft;
          }
          pNext = pRight;
        }else if(pNode->m_pParent != nullptr){
            BinaryTreeNode* pCurrent = pNode;
            /**
             * 如果当前节点没有右子树且是一个左节点，那么它的下一个节点就是它的父节点pNode->m_pParent
             */
            BinaryTreeNode* pParent = pNode->m_pParent;
            /**
             * 如果当前节点没有右子树且是一个右节点，那么它的下一个节点就是父节点之中为左节点的那个
             */
            while(pParent!=nullptr && pCurrent==pParent->m_pRight){
                pCurrent = pParent;
                pParent = pParent->m_pParent;
            }
            pNext = pParent;
        }
        return pNext;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70]: /images/20220213/b7f29c3ed9a1425991efbfda2056ef15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70 1]: /images/20220213/73461bd92797475f8d5eeeea19b4ebfb.png