二叉树的下一个节点

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

在下图中的二叉树的中序遍历序列是{d, b, h, e, i, a, f, c, g}。我们将以
这棵树为例来分析如何找出二叉树的下一个节点。

image.png

如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。也就是说，从右子节点出发一直沿着指向左子节点的指针，我们就能找到它的下一个节点。例如，节点b的下一个节点是h，节点a的下一个节点是f。

接着我们分析一个节点没有右子树的情形。如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。例如，节点d的下一个节点是b，节点f的下一个节点是c。

如果一个节点既没有右子树，并且它还是它父节点的右子节点，这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。

为了找到节点i的下一个节点，我们沿着指向父节点的指针向上遍历，先到达节点e。由于节点e是它父节点b的右节点，我们继续向上遍历到达节点b。节点b是它父节点a的左子节点，因此节点b的父节点a就是节点i的下一个节点。

找出节点g的下一个节点的步骤类似。我们先沿着指向父节点的指针到达节点c。由于节点c是它父节点a的右子节点，我们继续向上遍历到达节点a。由于节点a是树的根节点，它没有父节点，因此节点g没有下一个节点。

struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
    BinaryTreeNode* m_pParent;
};


BinaryTreeNode* GetNext(BinaryTreeNode* pNode) {
    
    if (pNode == nullptr) {
        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;
        BinaryTreeNode* pParent = pNode->m_pParent;
        while (pParent != nullptr && pCurrent == pParent->m_pRight) {
            pCurrent = pParent;
            pParent = pParent->m_pParent;
        }
        
        pNext = pParent;
    }
    
    return pNext;
}

测试代码

int m[9] = {'d', 'b', 'h', 'e', 'i', 'a', 'f', 'c', 'g'};

BinaryTreeNode *d = new BinaryTreeNode();
BinaryTreeNode *b = new BinaryTreeNode();
BinaryTreeNode *h = new BinaryTreeNode();
BinaryTreeNode *e = new BinaryTreeNode();
BinaryTreeNode *i = new BinaryTreeNode();
BinaryTreeNode *a = new BinaryTreeNode();
BinaryTreeNode *f = new BinaryTreeNode();
BinaryTreeNode *c = new BinaryTreeNode();
BinaryTreeNode *g = new BinaryTreeNode();

d->m_nValue = 'd';
d->m_pLeft = nullptr;
d->m_pRight = nullptr;
d->m_pParent = b;

b->m_nValue = 'b';
b->m_pLeft = d;
b->m_pRight = e;
b->m_pParent = a;

h->m_nValue = 'h';
h->m_pLeft = nullptr;
h->m_pRight = nullptr;
h->m_pParent = e;

e->m_nValue = 'e';
e->m_pLeft = h;
e->m_pRight = i;
e->m_pParent = b;

i->m_nValue = 'i';
i->m_pLeft = nullptr;
i->m_pRight = nullptr;
i->m_pParent = e;

a->m_nValue = 'a';
a->m_pLeft = b;
a->m_pRight = c;
a->m_pParent = nullptr;

f->m_nValue = 'f';
f->m_pLeft = nullptr;
f->m_pRight = nullptr;
f->m_pParent = c;

c->m_nValue = 'c';
c->m_pLeft = f;
c->m_pRight = g;
c->m_pParent = a;

g->m_nValue = 'g';
g->m_pLeft = nullptr;
g->m_pRight = nullptr;
g->m_pParent = c;

BinaryTreeNode *node = GetNext(a);

摘抄资料：《剑指offer》