二叉树的下一个结点

2019-11-08 03:04:23

字体：大中小

来源：转载

供稿：网友

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

算法解析：如果当前结点的右子节点不为空，那么下一个结点一定出现在当前结点的右子树上，转换为寻找当前右子树中序遍历的第一个结点。如果当前结点的父节点不为空，且当前结点是父节点的左子节点，则下一个结点一定是父节点，如果当前结点是父节点的右子节点，那么将当前结点和父节点视为一个子树，直到找到一个父节点，以之为左子树。

代码如下：

public TreeLinkNode GetNext(TreeLinkNode pNode) { if (pNode == null){ return null; } TreeLinkNode pNext = null; if (pNode.right != null){ TreeLinkNode PRight = pNode.right; while (pRight.left != null){ pRight = pRight.left; } pNext = pRight; }else if (pNode.next != null){ TreeLinkNode pCurrent = pNode; TreeLinkNode pParent = pNode.next; while (pParent != null && pCurrent == pParent.right){ pCurrent = pParent; pParent = pParent.next; } pNext = pParent; } return pNext; }

上一篇：类的静态成员学习

下一篇：[HDU]1205 吃糖果 [抽屉原理]