《剑指offer》--008--二叉树的下一个结点

末蓝、 2022-05-27 04:45 201阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

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

**思路：**

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

**代码如下：**

#include <iostream>
    using namespace std;
    
    typedef int DataType;
    
    typedef struct BTreeNode
    {
        DataType _data;
        struct BTreeNode* _parent;
        struct BTreeNode* _left;
        struct BTreeNode* _right;
    }BTreeNode;
    
    BTreeNode* BuyBTreeNode(DataType data)
    {
        BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
        if (node == NULL)
        {
            perror("malloc");
            exit(1);
        }
        node->_data = data;
        node->_parent = NULL;
        node->_left = NULL;
        node->_right = NULL;
        return node;
    }
    
    void CreateBTree(BTreeNode* parent, BTreeNode* leftChild, BTreeNode* rightChild)//构建特殊二叉树
    {
        if (parent != NULL)
        {
            parent->_left = leftChild;
            parent->_right = rightChild;
    
            if (leftChild != NULL)
            {
                leftChild->_parent = parent;
            }
            if (rightChild != NULL)
            {
                rightChild->_parent = parent;
            }
        }
    
    }
    
    void PrintNode(BTreeNode* node, BTreeNode* next)//打印结点的全部信息
    {
        if (node == NULL)
        {
            return;
        }
        cout << "该结点为" << node->_data << endl;
        cout << "该结点的下一个结点的信息如下："<< endl;
        if (next != NULL)
        {
            cout << "值为：" << next->_data << endl;
            if (next->_left != NULL)
            {
                cout << "左孩子的值为：" << next->_left->_data << endl;
            }
            else
            {
                cout << "左孩子为空" << endl;
            }
            if (next->_right != NULL)
            {
                cout << "右孩子的值为：" << next->_right->_data << endl;
            }
            else
            {
                cout << "右孩子为空" << endl;
            }
            if (next->_parent != NULL)
            {
                cout << "父结点的值为：" << next->_parent->_data << endl;
            }
            else
            {
                cout << "父结点为空" << endl;
            }
        }
        else
        {
            cout << "空" << endl;
        }
        cout << endl;
    }
    
    BTreeNode* GetNextNode(BTreeNode* node)//按中序顺序，获取该结点的下一个节点
    {
        if (node == NULL)
        {
            return NULL;
        }
        if (node->_parent != NULL)//非根节点
        {
            if (node->_left == NULL && node->_right == NULL)//叶子结点
            {
                if (node->_parent->_left == node)//3
                {
                    return node->_parent;
                }
                else if (node->_parent->_right == node)
                {
                    while (node != NULL)
                    {
                        node = node->_parent;
                        if (node != NULL && node->_parent != NULL && node->_parent->_left == node)//2
                        {
                            return node->_parent;
                        }
                    }
                    return NULL;//1
    
                }
            }
            else//非叶子结点
            {
                if (node->_right != NULL)//4
                {
                    return node->_right;
                }
                else
                {
                    if (node->_parent->_left == node)//3
                    {
                        return node->_parent;
                    }
                    else if (node->_parent->_right == node)
                    {
                        while (node != NULL)
                        {
                            node = node->_parent;
                            if (node!=NULL && node->_parent != NULL && node->_parent->_left == node)//2
                            {
                                return node->_parent;
                            }
                        }
                        return NULL;//1
    
                    }
                }
            }
        }
        else//根结点
        {
            return node->_right;
        }
    }
    
    void Test1()
    {
        BTreeNode* node1 = BuyBTreeNode(1);
        BTreeNode* node2 = BuyBTreeNode(2);
        BTreeNode* node3 = BuyBTreeNode(3);
        BTreeNode* node4 = BuyBTreeNode(4);
        BTreeNode* node5 = BuyBTreeNode(5);
        BTreeNode* node6 = BuyBTreeNode(6);
    
        CreateBTree(node1, node2, node3);
        CreateBTree(node2, node4, node5);
        CreateBTree(node3, node6, NULL);
    
        PrintNode(node1, GetNextNode(node1));
        PrintNode(node2, GetNextNode(node2));
        PrintNode(node3, GetNextNode(node3));
        PrintNode(node4, GetNextNode(node4));
        PrintNode(node5, GetNextNode(node5));
        PrintNode(node6, GetNextNode(node6));
        //cout << GetNextNode(node1)->_data << endl;
        //cout << GetNextNode(node2)->_data << endl;
        //cout << GetNextNode(node3)->_data << endl;
        //cout << GetNextNode(node4)->_data << endl;
        //cout << GetNextNode(node5)->_data << endl;
        //cout << GetNextNode(node6)->_data << endl;
    }
    
    
    void Test2()
    {
        BTreeNode* node1 = BuyBTreeNode(1);
        BTreeNode* node2 = BuyBTreeNode(2);
        BTreeNode* node3 = BuyBTreeNode(3);
        BTreeNode* node4 = BuyBTreeNode(4);
    
        CreateBTree(node1, node2, NULL);
        CreateBTree(node2, node3, NULL);
        CreateBTree(node3, node4, NULL);
    
        PrintNode(node1, GetNextNode(node1));
        PrintNode(node2, GetNextNode(node2));
        PrintNode(node3, GetNextNode(node3));
        PrintNode(node4, GetNextNode(node4));
    }
    
    void Test3()
    {
        BTreeNode* node1 = BuyBTreeNode(1);
        BTreeNode* node2 = BuyBTreeNode(2);
        BTreeNode* node3 = BuyBTreeNode(3);
        BTreeNode* node4 = BuyBTreeNode(4);
    
        CreateBTree(node1, NULL, node2);
        CreateBTree(node2, NULL, node3);
        CreateBTree(node3, NULL, node4);
    
        PrintNode(node1, GetNextNode(node1));
        PrintNode(node2, GetNextNode(node2));
        PrintNode(node3, GetNextNode(node3));
        PrintNode(node4, GetNextNode(node4));
    }
    
    void Test4()
    {
        BTreeNode* node1 = BuyBTreeNode(1);
        PrintNode(node1, GetNextNode(node1));
    
    }
    
    int main()
    {
        //Test1();
        //Test2();
        //Test3();
        Test4();
        system("pause");
        return 0;
    }

[offer]: https://blog.csdn.net/w_y_x_y/article/details/79209805
[70]: /images/20220527/052ea7bd5c7441b19c6ffe1af4c1647c.png