二叉树【汇总】

1 二叉树的基本概念

1.1 结点的度

结点所拥有的子树的个数
就是结点有几个儿子

1.2 叶结点

度为0的结点称为叶结点，或者终端结点

1.3 分枝结点/终端结点

度不为0的结点，除了叶结点，都是分支结点

1.4 左孩子、右孩子、双亲

具有同一个双亲的孩子互称为兄弟

1.5 路径、路径长度

一棵树的一串结点n1、n2、n3…nk有如下关系：ni是ni+1的父结点，称一条n1到nk的路径。路径的长度为k-1。

1.6 祖先、子孙

在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙

1.7 结点的层数

1.8 树的深度

树中所有结点的最大层数

1.9 树的度

各节点度的最大值

1.10 满二叉树、完全二叉树

1.11 大顶堆和小顶堆

大顶堆：所有父节点的值大于自己两个子节点的值。
小顶堆：所有父节点的值小于自己两个子节点的值。

2 二叉树的性质

• 完全二叉树中，假设父节点的序号为n，则其左结点的序号为2n+1，其右结点的序号为2n+2
• 一个完全二叉树，倒数第一个非叶子结点的序号为（所有结点数/2-1），这里是整除。
• 所有结点的度数之和 + 1 = 结点总数
• 度为0的结点（即叶子结点）总是比度为2的结点多一个，n0 = n2 + 1
  （证明：n0+n1+n2=n1+2*n2=n）
• 在完全二叉树中，度为1的结点的个数为0或者1
• 一棵深度为k的二叉树中，最多具有2^k-1个结点，最少有k个结点

3 二叉树的遍历

3.1 先序遍历

根→左→右

3.2 中序遍历

左→根→右

3.3 后序遍历

左→右→根

3.4 层序遍历

从第一层开始，从上至下逐层遍历，在同一层，按从左到右的顺序逐个访问
代码实现：
用队列来实现二叉树的层序遍历。先将根节点放入队列中，然后每次从队列中取出一个结点打印改结点的值，若这个结点有子结点，则将其子结点放入队列尾，直到队列为空。

3.5 四种遍历具体举例

先序遍历：ABDHIEJCFG
中序遍历：HDIBJEAFCG
后序遍历：HIDJEBFGCA
层序遍历：ABCDEFGHIJ

4 二叉排序树/二叉查找树

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。

定义结点：

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int data) {
		this.data = data;
		left = null;
		right = null;
	}
}

BinaryTree类，可以构建二叉排序树/二叉查找树，可以先序遍历、中序遍历、后序遍历此二叉查找树。

public class BinaryTree {
	private Node root;

	public BinaryTree() {
		root = null;
	}

	// 将data插入到排序二叉树中
	public void insert(int data) {
		Node newNode = new Node(data);// 建立新的node
		if (root == null) {// 如果树为空的，将新建立的结点当作根节点
			root = newNode;
		} else {// 树不空
			Node current = root;
			Node parent;
			while (true) {// 寻找插入的位置
				parent = current;
				if (data < current.data) {
					current = current.left;
					if (current == null) {
						parent.left = newNode;
						return;
					}
				} else {
					current = current.right;
					if (current == null) {
						parent.right = newNode;
						return;
					}
				}
			}
		}
	}

	// 将数值输入构建二叉树
	public void buildTree(int[] data) {
		for (int i = 0; i < data.length; i++) {
			insert(data[i]);
		}
	}

	// 中序遍历方法递归实现
	public void inOrder(Node localRoot) {
		if (localRoot != null) {
			inOrder(localRoot.left);
			System.out.print(localRoot.data + " ");
			inOrder(localRoot.right);
		}
	}

	public void inOrder() {
		this.inOrder(this.root);
	}

	// 先序遍历法递归实现
	public void preOrder(Node localRoot) {
		if (localRoot != null) {
			System.out.print(localRoot.data + " ");
			preOrder(localRoot.left);
			preOrder(localRoot.right);
		}
	}

	public void preOrder() {
		this.preOrder(this.root);
	}

	// 后序遍历方法递归实现
	public void postOrder(Node localRoot) {
		if (localRoot != null) {
			postOrder(localRoot.left);
			postOrder(localRoot.right);
			System.out.print(localRoot.data + " ");
		}
	}

	public void postOrder() {
		this.postOrder(this.root);
	}

	public static void main(String[] args) {
		BinaryTree biTree = new BinaryTree();
		int[] data = { 2, 8, 7, 4, 9, 3, 1, 6, 7, 5 };
		biTree.buildTree(data);
		biTree.inOrder();// 中序排列 1 2 3 4 5 6 7 7 8 9
		System.out.println();
		biTree.preOrder();// 先序排列 2 1 8 7 4 3 6 5 7 9
		System.out.println();
		biTree.postOrder();// 后序排列 1 3 5 6 4 7 7 9 8 2
	}
}