数据结构与算法(12)_二叉树

发表于 | 分类于

先了解树

“树”这种数据结构类似生活中的”树”,里面的每个元素叫做”节点”;用来连线相邻两个节点之间的关系,我们叫作”父子关系”.

在如下图中,A节点就是B节点的父节点,B节点是A节点的子节点.B,C,D这三个节点的父节点是同一个节点,所以称它们为兄弟节点.我们把没有父节点的节点叫作根节点,也就是图中的E.我们把没有子节点的节点叫作叶子节点或叶结点,比如图中的H,G,I,J,K,L都是叶子节点.

//TODO 图13

高度,深度和层

  • 节点的高度=节点到叶子节点的最长路径(边数).
  • 节点的深度=根节点到这个节点所经历的边的个数.
  • 节点的层数=节点的深度+1
  • 树的高度=根节点的高度

如图:

//TODO 图14

二叉树

二叉树,每个节点最多有两个子节点,分别是左子节点和右子节点.

//TODO 图15

编号2的二叉树,叶子节点全部在对底层,除了叶子节点外,每个节点都有左右两个子节点,这种二叉树叫作满二叉树.

编号3的二叉树,叶子节点都在最底下两层,除了最后一层其它层的节点个数都要达到最大.如果最后一层节点个数不满,必须靠左排列,这样的二叉树叫作完全二叉树.

二叉树的存储

存储二叉树有两种方法,一种是基于指针或者引用的二叉链式存储法.一种是基于数组的顺序存储法.

链式存储法

从图中可以看到,每个节点有三个字段,其中一个存储数据,另外两个分别指向左右子节点的指针.

//TODO 图16

顺序存储法

我们把跟节点存储在下标i=1的位置,左子节点存储在下标2 i = 2的位置,右子节点存储在2 i + 1 = 3的位置,以此类推,如图.

//TODO 图17

总结,如果节点X存储在数组下标为i的位置,下标2 i的位置存储的就是左子节点,下标2 i + 1的位置存储的就是右子节点.反过来下标i/2的位置存储的就是其父节点

二叉树的遍历

经典的方法有三种,前序遍历,中序遍历和后序遍历.

  • 前序遍历是指,对于树中任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树.
  • 中序遍历是指,对于树种任意节点来说,先打印它的左子树,然后打印它本身,再最后打印右子树.
  • 后序遍历是指,对于树中任意节点来说,先打印它的左子树,然后打印它的右子树,最后打印本身.

实际上,二叉树的前,中,后序遍历就是一个递归的过程.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//前序遍历
public static void preOrder(TreeNode root){
	if(root == null) return;
	System.out.println(root.data);
	preOrder(root.left);
	preOrder(root.right);
}

//中序遍历
public static void inOrder(TreeNode root){
	if(root == null) return;
	inOrder(root.left);
	System.out.println(root.data);
	inOrder(root.right);
}

//后序遍历
public static void postOrder(TreeNode root){
	if (root == null) return;
	postOrder(root.left);
	postOrder(root.right);
	System.out.println(root.data);
}

二叉查找树

二叉查找树也叫二叉搜索树.二叉查找树是为了实现快速查找而产生的,还支持快速的插入,删除一个数据.

二叉查找树的要求,在树种任意一个节点,其左子树的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值.

//TODO 图18

二叉查找树的查找操作

我们先取根节点,如果等于要查找的值就返回.如果查找的数据比根节点小,那就在左子树中递归查找;如果比根节点值大,那就在右子树中递归查找.

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode find(int value,TreeNode root){
	TreeNode p = root;
	while(p != null){
		if(value == p.value) return p;
		if(value < p.value){
			p = p.left;
		}
		if(value > p.value){
			p = p.right;
		}
	}
	return null;
}

插入操作

新插入的数据一般都是在叶子节点上,所以我们需要从根节点开始依次比较插入的数据和节点的大小关系.

如果插入的数据比节点大,并且右节点的右子树为空,则就将新数据插入到右子节点的位置;如果不为空,就遍历右子树,查找插入位置.同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就插入到左子节点的位置;不为空,则遍历左子树,查找插入位置.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//插入操作,不存在相同数据
public static void insert(int value, TreeNode root){
	if(null == root){
		root = new TreedNode();l
		root.value = value;
		return;
	}
	TreeNode newNode = new TreeNode();
	newNode.value = value;

	TreeeNode p = root;
	while(null != p){
		if(value < p.value){
			if(null == p.left){
				p.left = newNode;
				return;
			}
			p = p.left;
		}
		if(value > p.value){
			if(null == p.right){
				p.right = newNode;
				return;
			}
			p = p.right;
		}
	}
}

删除操作

删除操作比较复杂,需要分三种情况处理

第一种情况,如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为null.

第二种情况,如果要删除的节点,只有一个子节点(只有左子节点或右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了.

第三种情况,如果要删除的节点有两个子节点,我们需要找到这个节点右子树中的最小节点,把它替换到要删除的节点上.然后再删除这个最小节点,因为最小节点肯定没有左子节点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void delete(int value, TreeNode root){
	Node p = root;
	Node pp = null; //记录的是p节点的父节点.
	while(null != p && p.value != value){
		pp = p;
		if(value > p.data) 
			p = p.right;
		else
			p = p.left;
	}
	if(p == null) return; //没有找到
	//要删除的节点有两个子节点的
	if(p.left != null && p.right != null){
		//查找右子树中的最小节点
		TreeNode minP = p.right;
		TreeNode minPP = p; //minP的父节点
		while(null != minP.left){
			minPP = minP;
			minP = minP.left;
		}
		p.value = minP.value;
		p = minP;
		pp = minPP;
	}

	//删除的节点是叶子节点或者仅有一个子节点
	TreeNode child; //p的子节点
	if(p.left != null) child = p.left;
	else if(p.right != null) child = p.right;
	else child = null;
	
	if(pp == null) root = child; //要删除的是根节点
	else if(pp.left == p) pp.left = child;
	else pp.right = child;
}

其他操作

二叉查找树还可以支持快速的查找最大节点和最小节点,前驱节点和后继节点.

还有一个重要特性中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是O(n),非常高效.

支持重复数据的二叉查找树

如果存储两个相同数据要如何处理?

第一种方法比较容易.二叉查找树中每一个节点不仅会存储一个数据,因此我们通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上.

第二种,每个节点仍然只存一个数据.在查找插入位置的过程中,如果碰到一个节点与要插入数据的值相同,我们就将这个值放在这个节点的右子树,也就是说,把这个新插入的数据当做大于这个节点的值来处理.

当要查找的数据的时候,遇到值相同的节点,我们并不停止查找操作,而是继续右子树查找,直到遇到叶子节点,才停止.这样就可以把键值等于查找值的所有数据都找出来.

对于删除操作,我们也需要先查找到每个要删除的节点,然后按照前面讲的删除操作的方法,依次删除.

二叉查找树的时间复杂度分析

二叉查找树的形态格式各样.比如图中,对于同一种数据,我们构造了三种二叉查找树.它们的查找,插入,删除操作的执行效率都是不一样的.图中第一种二叉查找树,根节点的左右树极度不平衡,已经退化成了链表.查找的时间复杂度是O(n).

//todo 图19

理想情况下,二叉查找树是一个满二叉树或者完全二叉树.这个时候的时间复杂度其实都跟树的高度成正比,也就是O(height).
现在问题就变成了如何求一棵包含n个节点的完全二叉树的高度?

树的高度就等于最大层数减一.