二叉树的下一个结点

快来打我* 2023-03-12 07:08 50阅读 0赞

## 一、前言 ##

继续树相关的问题

## 二、题目 ##

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

## 三、思路 ##

中序遍历顺序：左 - 中 - 右

**1、若该节点有右子节点，则下一个节点为右节点集合中的第一个结点。**

例如下面实体：

e 下一个结点是 i；

a 下一个结点是 f；

**2、若该节点无右节点，则需往上查找直到当前节点为父节点的左子结点。**

例如下面实体：

h 是父节点(e)的左子结点，即：h 下一个结点是 e；

i 不是父节点(e)的左子节点，往上查找，e 不是父节点(b)的左子节点，往上查找，b 是父节点(a)的左子节点，即：i 下一个结点是 a；

上面分析的比较抽象，看下面实例：

![20200515225846534.png][]

前序遍历：a b d e h i c f g

中序遍历：d b h e i a f c g

## 四、编码实现 ##

先实现一个有父指针的树结构：

// Common.h
    #pragma once
    
    template<class T>
    struct BinaryTreeNode
    {
        T m_nValue;
        BinaryTreeNode* m_pLeft;
        BinaryTreeNode* m_pRight;
    };
    
    // 除了指向左右孩子节点，新加一个指向父节点
    template<class T>
    struct BinaryTreeNode_ParentNode
    {
        T m_nValue;
        BinaryTreeNode_ParentNode* m_pLeft;
        BinaryTreeNode_ParentNode* m_pRight;
        BinaryTreeNode_ParentNode* m_pParent;      //指向父节点
    };

**构建树**

// ConstructTree.h
    #pragma once
    #include <exception>
    #include "Common.h"
    
    
    // 构造普通树（不含父指针）START
    template<class T>
    BinaryTreeNode<T>* ConstructTreeOperate(T* startPreorder, T* endPreorder, T* startInorder, T* endInorder);
    
    template<class T>
    BinaryTreeNode<T>* ConstructTree(T* preorder, T* inorder, int length)
    {
        if (preorder == nullptr || inorder == nullptr || length <= 0)
            return nullptr;
    
        return ConstructTreeOperate(preorder, preorder + length - 1,
            inorder, inorder + length - 1);
    }
    
    template<class T>
    BinaryTreeNode<T>* ConstructTreeOperate
    (
        T* startPreorder, T* endPreorder,
        T* startInorder, T* endInorder
    )
    {
        // 前序遍历序列的第一个数字是根结点的值
        T rootValue = startPreorder[0];
        BinaryTreeNode<T>* root = new BinaryTreeNode<T>();
        root->m_nValue = rootValue;
        root->m_pLeft = root->m_pRight = nullptr;
    
        if (startPreorder == endPreorder)
        {
            if (startInorder == endInorder && *startPreorder == *startInorder)
                return root;
            else
                throw std::exception("Invalid input.");
        }
    
        // 在中序遍历中找到根结点的值
        T* rootInorder = startInorder;
        while (rootInorder <= endInorder && *rootInorder != rootValue)
            ++rootInorder;
    
        if (rootInorder == endInorder && *rootInorder != rootValue)
            throw std::exception("Invalid input.");
    
        int leftLength = int(rootInorder - startInorder);
        T* leftPreorderEnd = startPreorder + leftLength;
        if (leftLength > 0)
        {
            // 构建左子树
            root->m_pLeft = ConstructTreeOperate(startPreorder + 1, leftPreorderEnd,
                startInorder, rootInorder - 1);
        }
        if (leftLength < endPreorder - startPreorder)
        {
            // 构建右子树
            root->m_pRight = ConstructTreeOperate(leftPreorderEnd + 1, endPreorder,
                rootInorder + 1, endInorder);
        }
    
        return root;
    }
    // 构造普通树（不含父指针）END
    
    
    
    
    // 构造有父指针的树（含父指针）START
    template<class T>
    BinaryTreeNode_ParentNode<T>* ConstructParentNodeTreeOperate(T* startPreorder, T* endPreorder, T* startInorder, T* endInorder, BinaryTreeNode_ParentNode<T>* parentNode);
    
    template<class T>
    BinaryTreeNode_ParentNode<T>* ConstructParentNodeTree(T* preorder, T* inorder, int length)
    {
        if (preorder == nullptr || inorder == nullptr || length <= 0)
            return nullptr;
    
        BinaryTreeNode_ParentNode<T>* pRoot = new BinaryTreeNode_ParentNode<T>();
        return ConstructParentNodeTreeOperate(preorder, preorder + length - 1,
            inorder, inorder + length - 1, pRoot);
    }
    
    template<class T>
    BinaryTreeNode_ParentNode<T>* ConstructParentNodeTreeOperate
    (
        T* startPreorder, T* endPreorder,
        T* startInorder, T* endInorder,
        BinaryTreeNode_ParentNode<T>* parentNode
    )
    {
        // 前序遍历序列的第一个数字是根结点的值
        T rootValue = startPreorder[0];
        BinaryTreeNode_ParentNode<T>* root = new BinaryTreeNode_ParentNode<T>();
        root->m_nValue = rootValue;
        root->m_pLeft = root->m_pRight = nullptr;
        root->m_pParent = parentNode;
        if (startPreorder == endPreorder)
        {
            if (startInorder == endInorder && *startPreorder == *startInorder)
                return root;
            else
                throw std::exception("Invalid input.");
        }
    
        // 在中序遍历中找到根结点的值
        T* rootInorder = startInorder;
        while (rootInorder <= endInorder && *rootInorder != rootValue)
            ++rootInorder;
    
        if (rootInorder == endInorder && *rootInorder != rootValue)
            throw std::exception("Invalid input.");
    
        int leftLength = int(rootInorder - startInorder);
        T* leftPreorderEnd = startPreorder + leftLength;
        if (leftLength > 0)
        {
            // 构建左子树
            root->m_pLeft = ConstructParentNodeTreeOperate(startPreorder + 1, leftPreorderEnd,
                startInorder, rootInorder - 1, root);
        }
        if (leftLength < endPreorder - startPreorder)
        {
            // 构建右子树
            root->m_pRight = ConstructParentNodeTreeOperate(leftPreorderEnd + 1, endPreorder,
                rootInorder + 1, endInorder, root);
        }
    
        return root;
    }
    // 构造有父指针的树（含父指针）END

**获取二叉树的下一个结点**

// GetNextTreeNode.h
    
    #pragma once
    #include <exception>
    #include <iostream>
    #include "Common.h"
    #include "ConstructTree.h"
    using namespace std;
    
    #define NAMESPACE_GETNEXTNODE namespace NAME_GETNEXTNODE {
    #define NAMESPACE_GETNEXTNODEEND }
    
    //二叉树的下一个节点
    template<class T>
    BinaryTreeNode_ParentNode<T>* GetNext(BinaryTreeNode_ParentNode<T>* pNode)
    {
        if (pNode == nullptr)
            return nullptr;
    
        BinaryTreeNode_ParentNode<T>* pNext = nullptr;
        if (pNode->m_pRight != nullptr)
        {
            BinaryTreeNode_ParentNode<T>* pRight = pNode->m_pRight;
            while (pRight->m_pLeft != nullptr)
                pRight = pRight->m_pLeft;
    
            pNext = pRight;
        }
        else if (pNode->m_pParent != nullptr)
        {
            BinaryTreeNode_ParentNode<T>* pCurrent = pNode;
            BinaryTreeNode_ParentNode<T>* pParent = pNode->m_pParent;
            while (pParent != nullptr)
            {
                if (pCurrent == pParent->m_pLeft)
                {
                    break;
                }
                pCurrent = pParent;
                pParent = pParent->m_pParent;
            }
    
            pNext = pParent;
        }
    
        return pNext;
    }
    
    
    //
    // 测试开始
    NAMESPACE_GETNEXTNODE
    
    template<class T>
    BinaryTreeNode_ParentNode<T>* GetNote(BinaryTreeNode_ParentNode<T>* pRoot, T noteValue)
    {
        if (pRoot == nullptr)
        {
            return nullptr;
        }
    
        if (pRoot->m_nValue == noteValue)
        {
            return pRoot;
        }
    
        BinaryTreeNode_ParentNode<T>* pLeft = GetNote(pRoot->m_pLeft, noteValue);
        if (pLeft != nullptr)
        {
            return pLeft;
        }
    
        BinaryTreeNode_ParentNode<T>* pRight = GetNote(pRoot->m_pRight, noteValue);
        if (pRight != nullptr)
        {
            return pRight;
        }
    
        return nullptr;
    }
    
    template<class T>
    void test(const char* testName, T* preorder, T* inorder, int length, T noteValue, const T* expectNext)
    {
        BinaryTreeNode_ParentNode<T>* pRoot = ConstructParentNodeTree(preorder, inorder, length);
        if (pRoot == nullptr)
        {
            cout << testName << " input error.1" << endl;
        }
    
        BinaryTreeNode_ParentNode<T>* pNote = GetNote(pRoot, noteValue);
        if (pNote == nullptr)
        {
            cout << testName << " input error.2" << endl;
        }
    
        BinaryTreeNode_ParentNode<T>* pNext = GetNext(pNote);
        if (pNext == nullptr)
        {
            if (expectNext == nullptr)
            {
                cout << testName << " solution passed." << endl;
            }
            else
            {
                cout << testName << " solution failed." << endl;
            }
        }
        else if (expectNext == nullptr)
        {
            cout << testName << " solution failed." << endl;
        }
        else
        {
            if (pNext->m_nValue == *expectNext)
            {
                cout << testName << " solution passed." << endl;
            }
            else
            {
                cout << testName << " solution failed." << endl;
            }
        }
    }
    
    // 普通二叉树
    //                a
    //            /       \
    //           b         c  
    //         /   \      / \
    //        d     e    f   g
    //             / \     
    //            h   i  
    const int gLength = 9;
    char gPreorder[gLength + 1] = "abdehicfg";
    char gInorder[gLength + 1] = "dbheiafcg";
    
    // 测试用例 1
    void Test1()
    {
        char noteValue = 'd';
        const char* expectNext = "b";
        test("Test1", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 2
    void Test2()
    {
        char noteValue = 'b';
        const char* expectNext = "h";
        test("Test2", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 3
    void Test3()
    {
        char noteValue = 'h';
        const char* expectNext = "e";
        test("Test3", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 4
    void Test4()
    {
        char noteValue = 'e';
        const char* expectNext = "i";
        test("Test4", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 5
    void Test5()
    {
        char noteValue = 'i';
        const char* expectNext = "a";
        test("Test5", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 6
    void Test6()
    {
        char noteValue = 'a';
        const char* expectNext = "f";
        test("Test6", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 7
    void Test7()
    {
        char noteValue = 'f';
        const char* expectNext = "c";
        test("Test7", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 8
    void Test8()
    {
        char noteValue = 'c';
        const char* expectNext = "g";
        test("Test8", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    // 测试用例 9
    void Test9()
    {
        char noteValue = 'g';
        const char* expectNext = nullptr;
        test("Test9", gPreorder, gInorder, gLength, noteValue, expectNext);
    }
    
    NAMESPACE_GETNEXTNODEEND
    // 测试结束
    //
    
    void GetNextTreeNode_Test()
    {
        NAME_GETNEXTNODE::Test1();
        NAME_GETNEXTNODE::Test2();
        NAME_GETNEXTNODE::Test3();
        NAME_GETNEXTNODE::Test4();
        NAME_GETNEXTNODE::Test5();
        NAME_GETNEXTNODE::Test6();
        NAME_GETNEXTNODE::Test7();
        NAME_GETNEXTNODE::Test8();
        NAME_GETNEXTNODE::Test9();
    }

**执行结果：**

![20200515230229603.png][]

[20200515225846534.png]: /images/20230312/9583a363b2cb404f99d2b7c88981c25a.png
[20200515230229603.png]: /images/20230312/d539606d7444477ca9565cac449df8b1.png