数据结构与算法树的定义：数据结构和算法
数据结构与算法树的定义：数据结构和算法森林：由 m（m >= 0）个互不相交的树组成的集合被称为森林。有序树和无序树：如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。父结点（双亲结点）、子结点和兄弟结点：对于图 中的结点 A、B、C、D 来说，A是 B、C、D结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A结点的子结点（也称“孩子结点”）。对于B、C、D来说，它们都有相同的父结点，所以它们互为兄弟结点。结点的度和层次：对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）；图中，根结点 A下分出了 3个子树，所以，结点 A的度为 3。深度：定义一棵树的根结点层次为1，其他结点的层次是其父结点层次加1，一棵树中所有结点的层次的最大值称为这棵树的深度。
树树：是由结点（顶点）和边组成，可能是非线性的，且不存在着任何环的一种数据结构；
空树：没有结点的树称为空（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(" ");
}
}
