树（Tree）介绍

树（Tree）：一种非线性表结构。是由n（n>=1）个有限结点组成一个具有层次关系的集合。

特点

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。

高度（Height）、深 度（Depth）、层（Level）

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

种类

无序树、有序树、二叉树、满二叉树、完全二叉树、平衡二叉树（avl）、二叉查找树（二叉搜索树、BST）、霍夫曼树、红黑树、B树

二叉树（Binary Tree）

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

存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

二叉树的遍历

广度优先（BFS)
层次遍历：先访问离根节点最近的节点。

深度优先（DFS)：前序遍历、中序遍历和后序遍历

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

二叉查找树（Binary Search Tree）

二叉查找树也叫二叉搜索树（BST），是为了实现快 速查找而生的。不仅支持快速查找一个数据，还支持快速插入、删除一个数据。

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

平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。

二叉查找树的查找操作

查找一个节点

  1. 找根节点，等于就返回；
  2. 比根节点小，左子树中递归查找；
  3. 比根节点大，右子树中递归查找。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public class BinarySearchTree { 
    	private Node tree;
    	public Node find(int data) { 
    		Node p = tree; 
    		while (p != null) { 
    			if (data < p.data) p = p.left; 
    			else if (data > p.data) p = p.right; 
    			else return p;
    		} 
    		return null;
    	}

    	public static class Node { 
    		private int data; 
    		private Node left; 
    		private Node right;
    		public Node(int data) { 
    			this.data = data;
    		} 
    	} 
    }

二叉查找树的插入操作

  1. 从根节点开始，依次比较要插入的数据和节点的大小关系;
  2. 插入的数据比节点数值大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；不为空，就再递归遍历右子树，查找插入位置；
  3. 插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；不为空，就再递归遍历左子树，查找插入位置。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public void insert(int data) { 
    	if (tree == null) { 
    		tree = new Node(data); 
    		return;
    	}
    	Node p = tree; 
    	while (p != null) { 
    		if (data > p.data) { 
    			if (p.right == null) { 
    				p.right = new Node(data); 
    				return;
    			} 
    		p = p.right;
    		} else { // data < p.data 
    			if (p.left == null) { 
    				p.left = new Node(data); 
    				return;
    			} 
    			p = p.left;
    		} 
    	} 
    }

二叉查找树的删除操作

要删除节点的子节点个数的不同，分三种情况来处理。

  1. 要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指 针置为 null。
  2. 要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更 新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
  3. 要删除的节点有两个子节点。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上，然后再删除掉这个最小节点。
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
public void delete(int data) { 
	Node p = tree; // p 指向要删除的节点，初始化指向根节点 
	Node pp = null; // pp 记录的是 p 的父节点 
	while (p != null && p.data != data) { 
		pp = p; 
		if (data > p.data) p = p.right; 
		else p = p.left;
	} 
	if (p == null) return; // 没有找到

	// 要删除的节点有两个子节点 
	if (p.left != null && p.right != null) { // 查找右子树中最小节点 
		Node minP = p.right; 
		Node minPP = p; // minPP 表示 minP 的父节点 
		while (minP.left != null) { 
			minPP = minP; 
			minP = minP.left;
		} 
		p.data = minP.data; // 将 minP 的数据替换到 p 中 
		p = minP; // 下面就变成了删除 minP 了 pp = minPP;
	}

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

	if (pp == null) tree = child; // 删除的是根节点 
	else if (pp.left == p) pp.left = child; 
	else pp.right = child;
}

散列表很高效，为什么还要用二叉查找树？

  1. 散列表中的数据是无序存储的；二叉查找树有序；
  2. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定；
  3. 尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，加起来就不一定比平衡二叉查找树的效率高；
  4. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多；
  5. 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散 列表，不然会浪费一定的存储空间。