数据结构与算法---树---二叉树的前驱节点、后继节点

前驱节点

何为前驱节点？
前驱节点，指的是以中序遍历，遍历二叉树，某一个节点的前一个节点，被称为其前驱节点。
也就是，某一节点的左子树的右子节点的右子节点的右节点。。。

特殊情况，如果是二叉搜索树，则前驱节点是按从小到大的顺序，比其前面一个节点。

思路：

如果node.left != null;
则循环，node.left.right.right.right…直至为空，则找到了其前驱节点。

如果node.left == null;
如果node.parent == null;则没有前驱
如果node.parent != null;则前驱节点为node.parent.parent.parent…;
终止条件：node在parent的右子树中

public static TreeNode preNode(TreeNode root){if(root == null) return null;TreeNode node = root.left;if(node != null) {while(node.right != null) {node = node.right;}return node;}else {while(node.parent != null && node == node.parent.left) {node = node.parent;}//来到这里包含两种情况：//node.parent == null//node = node.parent.rightreturn node.parent;}}

后继节点

中序遍历的某一节点的后一个节点，被称为后继节点
参照前驱节点，不难写成后继节点

思路：

如果node.right != null;
则循环，node.right.left.left.left…直至为空，则找到了其后继节点。

如果node.right == null;
如果node.parent == null;则没有后继
如果node.parent != null;则后继节点为node.parent.parent.parent…;
终止条件：node在parent的左子树中

public static TreeNode postNode(TreeNode root) {if(root == null) return null;TreeNode node = root.right;if(node != null) {while(node.left != null){node = node.left;}return node;}else {while(node.parent != null && node == node.parent.right){node = node.parent;}return node.parent;}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！