数据结构-二叉搜索树的前驱和后继节点

weblog 精帖
2081

什么是二叉树的前驱节点和后继节点?

某节点的前驱节点的val值小于该节点的val值并且值是最大的那个节点。
某节点的后继节点的val值大于该节点的val值并且值是最小的那个节点。

 下面给出一个二叉树节点类,和一个例子来说明。

package com.dzqc.yx.tree;
/**
 * 	节点类
 * @author jiajia
 * @param <T>
 * @param <E>
 */
public class Node<T,E> {
	/**
	 * 用于查找数据时比较的key
	 */
	public Integer key;
	/**
	 * 数据
	 */
	public E e;
	/**
	 * 父节点引用
	 */
	public Node<T,E> parent;
	/**
	 * 左子节点引用
	 */
	public Node<T,E> left;
	/**
	 * 右子节点引用
	 */
	public Node<T,E> right;
	
	public Node(Integer key, E e) {
		super();
		this.key = key;
		this.e = e;
	}
	public Node(Integer key, E e, Node<T, E> parent) {
		super();
		this.key = key;
		this.e = e;
		this.parent = parent;
	}
	public E setValue(E e) {
		return this.e=e;
	}
}

如上图:

1的前驱节点是0,4的前驱节点是3,6的前驱节点是5,3的前驱节点是2.

7的后继节点是8,9的后继节点是10,4的后继节点是5,2的后继节点是3

注意:上述的节点类都有对父节点的引用,如果没有父节点的引用将会用先序遍历的方式求,将会加大时间复杂度。

算法过程

某节点的前驱节点
  1. 若该节点有左子树,那么该节点的前驱节点是其左子树中val值最大的那个节点。
  2. 若该节点没有左子树,则判断该节点和其父节点的关系。
    1. 若该节点是其父节点的右子树,那么该节点的前驱结点就是其父节点。
    2. 若该节点是其父节点的左子树,那么沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的右子树,那么节点Q就是该节点的后继节点。
某节点的后继节点
  1. 若该节点有右子树,那么该节点的后继节点是其右子树中val值最小的那个节点。
  2. 若该节点没有右子树,则判断该节点和其父节点的关系。
    1. 若该节点是其父节点的左子树,那么该节点的后继结点就是其父节点  。
    2. 若该节点是其父节点的右子树,那么沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的左子树,那么节点Q就是该节点的后继节点。

java代码实现

前驱节点代码实现
	/**
	 *	 寻找前驱节点
	 * @param t
	 * @return
	 */
	public Node<Integer,Integer> precursor(Node<Integer,Integer> t){
		if(t!=null) {
			if(t.left!=null) {
				Node<Integer,Integer> p=t.left;
				while(p.right!=null)
					p=p.right;
				return p;
			}else {
				if(t==t.parent.right) {
					return t.parent;
				}else {
					Node<Integer,Integer> p=t.parent;
					while(p!=null&&p!=p.parent.right) {
						p=p.parent;
					}
					return p.parent;
				}
			}
		}else {
			return null;
		}
	}
前驱节点测试
/**
 * 	前驱节点
 */
@Test
public void test24() {
	Node<Integer,Integer> n6=new Node<>(6,6,null);
	Node<Integer,Integer> n1=new Node<>(1,1,n6);
	Node<Integer,Integer> n5=new Node<>(5,5,n1);
	Node<Integer,Integer> n3=new Node<>(3,3,n5);
	Node<Integer,Integer> n2=new Node<>(2,2,n3);
	Node<Integer,Integer> n4=new Node<>(4,4,n3);
	Node<Integer,Integer> n7=new Node<>(7,7,n6);
	Node<Integer,Integer> n9=new Node<>(9,9,n7);
	Node<Integer,Integer> n8=new Node<>(8,8,n9);
	Node<Integer,Integer> n10=new Node<>(10,10,n9);
	
	n6.left=n1;
	n6.right=n7;
	n1.right=n5;
	n5.left=n3;
	n3.left=n2;
	n3.right=n4;
	n7.right=n9;
	n9.left=n8;
	n9.right=n10;
	
	System.out.println(precursor(n10).key);
}
后继节点代码实现

/**
 * 	寻找后继节点
 * @param t
 * @return
 */
public Node<Integer,Integer> successor(Node<Integer,Integer> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
    	Node<Integer,Integer> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
    	Node<Integer,Integer> p = t.parent;
    	Node<Integer,Integer> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}
 后继节点测试
/**
 * 后继节点
 */
@Test
public void test23() {
	Node<Integer,Integer> n6=new Node<>(6,6,null);
	Node<Integer,Integer> n1=new Node<>(1,1,n6);
	Node<Integer,Integer> n5=new Node<>(5,5,n1);
	Node<Integer,Integer> n3=new Node<>(3,3,n5);
	Node<Integer,Integer> n2=new Node<>(2,2,n3);
	Node<Integer,Integer> n4=new Node<>(4,4,n3);
	Node<Integer,Integer> n7=new Node<>(7,7,n6);
	Node<Integer,Integer> n9=new Node<>(9,9,n7);
	Node<Integer,Integer> n8=new Node<>(8,8,n9);
	Node<Integer,Integer> n10=new Node<>(10,10,n9);
	
	n6.left=n1;
	n6.right=n7;
	n1.right=n5;
	n5.left=n3;
	n3.left=n2;
	n3.right=n4;
	n7.right=n9;
	n9.left=n8;
	n9.right=n10;
	
	System.out.println(successor(n10));
}

 

猜你喜欢
  • blog 算法-判断单链表是否有环 求环入口地址(java)

    问题:如上图一个链表,如何判断一个链表中是否存在环,以及如何求出环入口以及何如求出链表长度。 方案一:利用hash表         首先准备一个hash表如hashMap等,然从链表头部
  • blog 算法-迷宫问题-广度优先-队列

    问题描述思路: 典型广度优先算法,根字典序大小,可以确定遍历循序, 因为字典序D<L<R<U, 所以对于每一个优先先往下走,然向左走,然向右走,然向上走。则最首先到达出口一条路径就是符合题意最短路径。
  • file 判断单链表是否有环以及求环入口环长度2种方案分析-附java代码

    <pre class="language-java"><code class="line-numbers data-output match-braces rainbow-braces">/**
  • blog 使用双向循环链表解决 约瑟夫环问题-算法

    约瑟夫环问题描述         有m个人,围成一个环,编号为 1、2、3、、、m,从第一个人开始循环报(从1开始),假设到n那个人出局,然从下一个人(从1开始),到n出列,以
  • blog 基本操作 c++

    基本操作 c++class node{public : int data; node * left; node * right; node(); node(int data); node(int data,node * left,no
  • blog avl旋转

    avl:AVL本质上是一颗查找1.avl性质 左子右子高度之差绝对值不超过1 每个左子右子都是AVL 每个都有一个平衡因子(balance factor--
  • blog 程序员必须掌握算法

    原文链接:https://www.zhihu.com/question/23148377?sort=created  算法基础 时间复杂度 空间复杂度  基础 线性表 列表(必学)
  • blog -图着色问题

    -图着色问题问题描述: 图m-着色判定问题——给定无向连通图Gm种不同颜色。用这些颜色为图G各顶着色,每个顶着一种颜色,是否有一种着色法使G中任意相邻2个顶着不同颜色?个人感觉图着色问题类似与八皇
  • blog 左旋右旋

    在关于多种算法中都用到了旋转来使保持相对平衡,比如avl,红黑等...1.左旋(pivot为旋转中心)2.来个动图3.代码演示: /** * 左旋 * p为旋转中心 */ public void
  • blog 最小生成Kruskal算法-算法

    最小生成算法其应用         什么是最小生成:一个有 n 个连通图生成是原图极小连通子图,且包含原图中所有 n 个,并且有保持图连通最少边。最小生成可以用krus