【8】求二叉树某节点的下一个节点

素颜马尾好姑娘i 2022-05-27 08:43 179阅读 0赞

## 面试题8：二叉树的下一个结点 ##

**1、题目**   
**2、分析**   
**3、测试代码**   
**4、测试结果如下**

### **1、 题目：** ###

给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？  
树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针，如下所示：

typedef struct BinTreeNode
    {
        int _value;
         BinTreeNode* _pLeft;
         BinTreeNode* _pRight;
         BinTreeNode* _pParent;
    };

### **2、分析：** ###

分为两个大的方面来求解：  
【1】、该节点没有右孩子节点  
<1>该节点是其父节点的左节点  
那么，所求的下一个节点就是其父节点

<2>该节点是其父节点的右节点  
那么，所求的节点就是从该节点向上遍历，直到它的某个父节点为左子节点为止

【2】、该节点存在右孩子节点  
那么，所求的节点沿着右孩子节点的左孩子节点一直向下遍历，直到遍历成叶子节点为止

### **3、测试代码：** ###

#include<iostream>
    using namespace std;
    typedef struct BinTreeNode
    {
        int _value;
         BinTreeNode* _pLeft;
         BinTreeNode* _pRight;
         BinTreeNode* _pParent;
    };
    
    BinTreeNode* GetNext(BinTreeNode* pNode)
    {
        if(pNode == NULL)
        {
            return NULL;
        }
        BinTreeNode* pNext = NULL;
        if(pNode->_pRight != NULL)
        {
            BinTreeNode* right = pNode->_pRight ;
            while(right->_pLeft != NULL)
            {
                right =right->_pLeft;
            }
            pNext= right;
        }
        else 
            {
                if(pNode->_pParent != NULL)
                {
                    BinTreeNode* pCur = pNode;
                    BinTreeNode* pParent =pNode->_pParent ;
                    while(pParent != NULL && pCur == pParent->_pRight )
                    {
                        pCur = pCur->_pParent ;
                        pParent = pParent->_pParent;
                    }
                    pNext = pParent;
                }
        }
            return pNext;
    }
    
    // ==================== 辅助代码用来构建二叉树 ====================
    BinTreeNode* CreateBinaryTreeNode(int value)
    {
        BinTreeNode* pNode = new BinTreeNode();
        pNode->_value = value;
        pNode->_pLeft = NULL;
        pNode->_pRight = NULL;
        pNode->_pParent = NULL;
    
        return pNode;
    }
    
    void ConnectTreeNodes(BinTreeNode* pParent, BinTreeNode* pLeft, BinTreeNode* pRight)
    {
        if(pParent != NULL)
        {
            pParent->_pLeft = pLeft;
            pParent->_pRight = pRight;
    
            if(pLeft != NULL)
                pLeft->_pParent = pParent;
            if(pRight != NULL)
                pRight->_pParent = pParent;
        }
    }
    
    void PrintTreeNode(BinTreeNode* pNode)
    {
        if(pNode != NULL)
        {
            printf("value of this node is: %d\n", pNode->_value);
    
            if(pNode->_pLeft != NULL)
                printf("value of its left child is: %d.\n", pNode->_pLeft->_value);
            else
                printf("left child is null.\n");
    
            if(pNode->_pRight != NULL)
                printf("value of its right child is: %d.\n", pNode->_pRight->_value);
            else
                printf("right child is null.\n");
        }
        else
        {
            printf("this node is null.\n");
        }
    
        printf("\n");
    }
    
    void PrintTree(BinTreeNode* pRoot)
    {
        PrintTreeNode(pRoot);
    
        if(pRoot != NULL)
        {
            if(pRoot->_pLeft != NULL)
                PrintTree(pRoot->_pLeft);
    
            if(pRoot->_pRight != NULL)
                PrintTree(pRoot->_pRight);
        }
    }
    
    void DestroyTree(BinTreeNode* pRoot)
    {
        if(pRoot != NULL)
        {
            BinTreeNode* pLeft = pRoot->_pLeft;
            BinTreeNode* pRight = pRoot->_pRight;
    
            delete pRoot;
            pRoot = NULL;
    
            DestroyTree(pLeft);
            DestroyTree(pRight);
        }
    }
    
    
    
    // ====================测试代码====================
    void Test(char* testName, BinTreeNode* pNode, BinTreeNode* expected)
    {
        if(testName != NULL)
            printf("%s 开始: ", testName);
    
        BinTreeNode* pNext = GetNext(pNode);
        if(pNext == expected)
            printf("测试成功.\n");
        else
            printf("测试失败.\n");
    }
    
    //            8
    //        6      10
    //       5 7    9  11
    void Test1_7()
    {
        BinTreeNode* pNode8 = CreateBinaryTreeNode(8);
        BinTreeNode* pNode6 = CreateBinaryTreeNode(6);
        BinTreeNode* pNode10 = CreateBinaryTreeNode(10);
        BinTreeNode* pNode5 = CreateBinaryTreeNode(5);
        BinTreeNode* pNode7 = CreateBinaryTreeNode(7);
        BinTreeNode* pNode9 = CreateBinaryTreeNode(9);
        BinTreeNode* pNode11 = CreateBinaryTreeNode(11);
    
        ConnectTreeNodes(pNode8, pNode6, pNode10);
        ConnectTreeNodes(pNode6, pNode5, pNode7);
        ConnectTreeNodes(pNode10, pNode9, pNode11);
    
        Test("Test1", pNode8, pNode9);
        Test("Test2", pNode6, pNode7);
        Test("Test3", pNode10, pNode11);
        Test("Test4", pNode5, pNode6);
        Test("Test5", pNode7, pNode8);
        Test("Test6", pNode9, pNode10);
        Test("Test7", pNode11, NULL);
        printf("\n");
        DestroyTree(pNode8);
    }
    
    //            5
    //          4
    //        3
    //      2
    void Test8_11()
    {
        BinTreeNode* pNode5 = CreateBinaryTreeNode(5);
        BinTreeNode* pNode4 = CreateBinaryTreeNode(4);
        BinTreeNode* pNode3 = CreateBinaryTreeNode(3);
        BinTreeNode* pNode2 = CreateBinaryTreeNode(2);
    
        ConnectTreeNodes(pNode5, pNode4, NULL);
        ConnectTreeNodes(pNode4, pNode3, NULL);
        ConnectTreeNodes(pNode3, pNode2, NULL);
    
        Test("Test8", pNode5, NULL);
        Test("Test9", pNode4, pNode5);
        Test("Test10", pNode3, pNode4);
        Test("Test11", pNode2, pNode3);
        printf("\n");
        DestroyTree(pNode5);
    }
    
    //        2
    //         3
    //          4
    //           5
    void Test12_15()
    {
         BinTreeNode* pNode2 = CreateBinaryTreeNode(2);
         BinTreeNode* pNode3 = CreateBinaryTreeNode(3);
         BinTreeNode* pNode4 = CreateBinaryTreeNode(4);
         BinTreeNode* pNode5 = CreateBinaryTreeNode(5);
    
        ConnectTreeNodes(pNode2, NULL, pNode3);
        ConnectTreeNodes(pNode3, NULL, pNode4);
        ConnectTreeNodes(pNode4, NULL, pNode5);
    
        Test("Test12", pNode5, NULL);
        Test("Test13", pNode4, pNode5);
        Test("Test14", pNode3, pNode4);
        Test("Test15", pNode2, pNode3);
        printf("\n");
        DestroyTree(pNode2);
    }
    
    void Test16()
    {
        BinTreeNode* pNode5 = CreateBinaryTreeNode(5);
    
        Test("Test16", pNode5, NULL);
        printf("\n");
        DestroyTree(pNode5);
    }
    
    int main(int argc, char* argv[])
    {
        Test1_7();
        Test8_11();
        Test12_15();
        Test16();
    }

### **4、测试结果如下：**  ###

![这里写图片描述][70]

[70]: /images/20220527/ca01a6cb5381489ba4544a0bc9c2c668.png