1 问题
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针
2 分析
比如我现在的二叉树如下
4 2 6 1 3 5 7
这里分3种情况
1) 如果这个节点包含右子树，那么下一个节点就是这个右子树的最左下节点，比如节点4的下一个节点是5.
2) 如果这个节点不包含右子树，如果这个节点的父节点的左子节点是同一个，那么下一个节点就是这个节点的父节点，比如节点6的下一个节点就是7.
3) 如果这个节点不包含右子树，如果这个节点的父节点的右子节点是同一个，这里分2种情况，我们先找到这节点的父结点，然后父节点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点，比如节点3的下一个节点是4，也有可能没有下一个节点，比如节点7的下一个节点就是空。
3 代码实现
typedef struct Tree { int value; struct Tree* left; struct Tree* right; struct Tree* parent; Tree(int value) : value(value), left(NULL), right(NULL), parent(NULL) {} Tree() : value(0), left(NULL), right(NULL), parent(NULL) {} } Tree; Tree* getNext(Tree* node) { if (NULL == node) return NULL; Tree* nextNode = NULL; if (NULL != node->right) { Tree* rightNode = node->right; while (rightNode->left != NULL) { rightNode = rightNode->left; } nextNode = rightNode; } else { Tree* currentNode = node; Tree* parentNode = currentNode->parent; while (NULL != parentNode && parentNode->right == currentNode) { currentNode = parentNode; parentNode = currentNode->parent; } nextNode = parentNode; } return nextNode; }
