树

树：是由结点（顶点）和边组成，可能是非线性的，且不存在着任何环的一种数据结构；

空树：没有结点的树称为空（null或empty）树；

非空树：一棵非空的树包括一个根结点，还（很可能）有多个附加结点，所有结点构成一个多级分层结构；

结点：使用树结构存储的每一个数据元素都被称为“结点”；图中，数据元素 A 就是一个结点；

父结点（双亲结点）、子结点和兄弟结点：对于图 中的结点 A、B、C、D 来说，A是 B、C、D结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A结点的子结点（也称“孩子结点”）。对于B、C、D来说，它们都有相同的父结点，所以它们互为兄弟结点。

结点的度和层次：对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）；图中，根结点 A下分出了 3个子树，所以，结点 A的度为 3。

深度：定义一棵树的根结点层次为1，其他结点的层次是其父结点层次加1，一棵树中所有结点的层次的最大值称为这棵树的深度。

有序树和无序树：如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。

森林：由 m（m >= 0）个互不相交的树组成的集合被称为森林。

二叉树

二叉树：每个节点最多只能有两个子节点；简单地理解，满足以下两个条件的树就是二叉树：

1、本身是有序树；

2、树中包含的各个节点的度不能超过 2，即只能是 0、1或者 2；

满二叉树：

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

完全二叉树：

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

二叉树的遍历方式：前序遍历，后续遍历，中序遍历；

二叉树的遍历

前序遍历：先遍历父节点，在遍历左子树；然后是右子树；

中序遍历：先遍历左子树，在遍历父点击，在遍历右子树；

后序遍历：先遍历左子树，在遍历右子树，然后是父节点；

二叉树的删除

1、如果删除的叶子节点，删除该节点；

2、如果删除的非叶子节点，删除该子树；

顺序存储二叉树

将二叉树存储在一个数组中，通过存储元素的下标反映元素之间的父子关系；

以数组的方式来存储二叉树，但依然可以前序、中序、后序遍历树；

第N个元素的左子树节点为：2*N+1；

第N个元素的右子树节点为：2*N+2；

第N个元素的父节点为：(N-1)/2；

N表示二叉树中的第几个元素（从0开始编号）

堆排序会用到顺序存储二叉树；

线索化二叉树

N个节点的二叉链表中含有N+1【公式2n-(n-1)=n+1】个空指针域；

利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针（珍重附加的指针称为"线索"）；

这种加了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded BinaryTree）；

根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树；

一个节点的前一个节点，称为前驱；

一个节点的后一个节点，称为后继；

顺序存储二叉树——规则

第N个元素的左子树节点为：2*N+1；

第N个元素的右子树节点为：2*N+2；

第N个元素的父节点为：(N-1)/2；

N表示二叉树中的第几个元素（从0开始编号）

B树

B树，即二叉搜索树：1、所有非叶子结点至多拥有两个儿子（Left和Right）；2、所有结点存储一个关键字；3、非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

B-树

B-树，是一种多路搜索树（并不是二叉的）：1、定义任意非叶子结点最多只有M个儿子；且M>2；2、根结点的儿子数为[2, M]；3、除根结点以外的非叶子结点的儿子数为[M/2, M]；4、每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）；5、非叶子结点的关键字个数=指向儿子的指针个数-1；6、非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；7、非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；8、所有叶子结点位于同一层；

B+树

B+树是应文件系统所需而产生的一种B-树的变形树，一棵m阶的B+树和m 阶的B-。

树的差异在于：1、有n 棵子树的结点中含有n 个关键码；2、所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接；3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。

B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

案例：二叉树实现

public class Element<E> {

	// 存放数据
	private E data;

	// 左子树
	private Element<E> leftElement;

	// 右子树
	private Element<E> rightElement;

	public Element(E data) {
		super();
		this.data = data;
	}

	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

	public Element<E> getLeftElement() {
		return leftElement;
	}

	public void setLeftElement(Element<E> leftElement) {
		this.leftElement = leftElement;
	}

	public Element<E> getRightElement() {
		return rightElement;
	}

	public void setRightElement(Element<E> rightElement) {
		this.rightElement = rightElement;
	}

	@Override
	public String toString() {
		return "BinaryTree [data=" + data + "]";
	}

	// ================================================================================//
	// ===operate
	// ================================================================================//

	// 前序遍历
	public void preOrderTraversal() {
		// 1、输出父节点
		System.out.println(this);
		// 2、递归左子树
		if (this.leftElement != null) {
			this.leftElement.preOrderTraversal();
		}
		// 3、递归右子树
		if (this.rightElement != null) {
			this.rightElement.preOrderTraversal();
		}
	}

	// 中序遍历
	public void infixOrderTraversal() {
		// 1、递归左子树
		if (this.leftElement != null) {
			this.leftElement.infixOrderTraversal();
		}
		// 2、输出父节点
		System.out.println(this);
		// 3、递归右子树
		if (this.rightElement != null) {
			this.rightElement.infixOrderTraversal();
		}
	}

	// 后序遍历
	public void postOrderTraversal() {
		// 1、递归左子树
		if (this.leftElement != null) {
			this.leftElement.postOrderTraversal();
		}
		// 2、递归右子树
		if (this.rightElement != null) {
			this.rightElement.postOrderTraversal();
		}
		// 3、输出父节点
		System.out.println(this);
	}

}

/**
 * 二叉树节点
 * 
 * @param <E>
 */
public class BinaryTree<E> {

	private Element<E> root;

	public void setRoot(Element<E> root) {
		this.root = root;
	}

	// ================================================================================//
	// ===operate
	// ================================================================================//

	// 前序遍历
	public void preOrderTraversal() {
		if (this.root != null) {
			this.root.preOrderTraversal();
		} else {
			System.out.println("二叉树为空");
		}
	}

	// 中序遍历
	public void infixOrderTraversal() {
		if (this.root != null) {
			this.root.infixOrderTraversal();
		} else {
			System.out.println("二叉树为空");
		}
	}

	// 后续遍历
	public void postOrderTraversal() {
		if (this.root != null) {
			this.root.postOrderTraversal();
		} else {
			System.out.println("二叉树为空");
		}
	}

}

public class BinaryTreeDemo {

	public static void main(String[] args) {
		BinaryTree<String> binaryTree = new BinaryTree<String>();
		// 手动创建二叉树
		Element<String> element1 = new Element<String>("1");
		Element<String> element2 = new Element<String>("2");
		Element<String> element3 = new Element<String>("3");
		Element<String> element4 = new Element<String>("4");
		Element<String> element5 = new Element<String>("5");
		Element<String> element6 = new Element<String>("6");
		Element<String> element7 = new Element<String>("7");
		// 1 的子节点：2 和 3
		element1.setLeftElement(element2);
		element1.setRightElement(element3);
		// 2的子节点: 4和5
		element2.setLeftElement(element4);
		element2.setRightElement(element5);
		// 3的子节点: 6和7
		element3.setLeftElement(element6);
		element3.setRightElement(element7);
		binaryTree.setRoot(element1);

		System.out.println("前序遍历：");
		binaryTree.preOrderTraversal();
		System.out.println("中序遍历：");
		binaryTree.infixOrderTraversal();
		System.out.println("后序遍历：");
		binaryTree.postOrderTraversal();
	}

}

案例：顺序存储二叉树

/**
 * 顺序存储二叉树
 */
public class ArrayBinaryTree {

	private int[] array;

	public ArrayBinaryTree(int[] array) {
		this.array = array;
	}

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

	/**
	 * 前序遍历
	 * 
	 * @param index 数组的下标
	 */
	public void preOrder(int index) {
		// 数组为空
		if (array == null || array.length <= 0) {
			System.out.println("数组为空，不能按照前序遍历.");
			return;
		}
		System.out.println(array[index]);
		// 向左递归
		if ((2 * index + 1) < array.length) {
			preOrder(2 * index + 1);
		}
		// 向右递归
		if ((2 * index + 2) < array.length) {
			preOrder(2 * index + 2);
		}
	}

	public void infixOrder() {
		this.infixOrder(0);
	}

	/**
	 * 中序遍历
	 * 
	 * @param index 数组的下标
	 */
	public void infixOrder(int index) {
		// 数组为空
		if (array == null || array.length <= 0) {
			System.out.println("数组为空，不能按照前序遍历.");
			return;
		}
		// 向左递归
		if ((2 * index + 1) < array.length) {
			infixOrder(2 * index + 1);
		}
		System.out.println(array[index]);
		// 向右递归
		if ((2 * index + 2) < array.length) {
			infixOrder(2 * index + 2);
		}
	}

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

	/**
	 * 后序遍历
	 * 
	 * @param index 数组的下标
	 */
	public void postOrder(int index) {
		// 数组为空
		if (array == null || array.length <= 0) {
			System.out.println("数组为空，不能按照前序遍历.");
			return;
		}
		// 向左递归
		if ((2 * index + 1) < array.length) {
			postOrder(2 * index + 1);
		}
		// 向右递归
		if ((2 * index + 2) < array.length) {
			postOrder(2 * index + 2);
		}
		System.out.println(array[index]);
	}

}

public class ArrayBinaryTreeDemo01 {

	public static void main(String[] args) {
		int[] array = { 1, 2, 3, 4, 5, 6, 7 };
		ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		arrayBinaryTree.preOrder(); // 1,2,3,4,3,6,7
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		arrayBinaryTree.infixOrder(); // 4,2,5,1,6,3,7
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		arrayBinaryTree.postOrder(); // 4,5,2,6,7,3,1
		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++");
	}

}