数据结构之树
- 基本概念
树是n(n>=0)个结点的有限集。n=0的时候称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根结点
(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2.....、Tn，其中么一个集合本身又是一棵树，并且称之为根的子树(SubTree)。
如下图所示
结点的度:结点拥有的子树数称为结点的度。度为0结点称为叶子结点或者终端结点，度不为0的结点称为非终端结点或者分支结点。除根结点外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
层次与深度:结点的层次从根开始定义起，根为第一层，根的子树为第二层。若某结点在第i层，则其子树的根就在第i+1层。其双亲在同一层的结点互为堂兄弟。显然下图中的D、E、F是堂兄弟，G、H、I、J也是。树中结点的最大层次称为树的深度或高度，当前树的深度是4。
种类：
树的存储结构：结合顺序存储和链式存储来实现主要有：
双亲表示法：在每个结点中，附设一个指示器指示其双亲结点到链表中的位置，缺点就是要知道父结点下有哪几个子结点比较麻烦。
孩子表示法：
孩子兄弟表示法：任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
最终方案：把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一维数组中。类似与java1.7中hashmap的数据结构
- 二叉树
二叉树的性质:
性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）。
性质2：深度为k的二叉树至多有2k-1个结点（k>=1）。
性质3：对任何一颗二叉树T，如果其终端结点数为n0,度为2的 结点 数为n2，则n0 = n2+1.
性质4：具有n个结点的完全二叉树深度为[log2n]+1 ([x]表示不 大于 x的最大整数)。
性质5：如果对一颗有n个结点的完全二叉树（其深度为[log2n]+1） 的结点按层序编号（从第1层到第[log2n]+1层，每层从左到 右），对任意一个结点i(1<=i<=n)有：
1）.如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结 点[i/2]
2）.如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩 子是结点2i。
3）.如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。
二叉树的遍历:
前序遍历:规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，在前序遍历右子树。
即 根 左 右
伪代码:
void ProOrderTraverse(Tree T){
if(T == null){
return;
}
printf(“%c”,T-data); //根
ProOrderTraverse(T->lchild);//左
ProOrderTraverse(T->rchild);//右
}中序遍历：规则是若树为空，则空操作返回，否则从根结点开始（注意并不是访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树
即 左 根 右
伪代码
void ProOrderTraverse(Tree T){
if(T == null){
return;
}
ProOrderTraverse(T->lchild); //左
printf(“%c”,T-data); //中
ProOrderTraverse(T->rchild);//右
}后序遍历:规则是若树为空，则空操作返回，否则从左到右先叶子结点的方式遍历左右子树，最后访问根结点
即 左 右 根
伪代码
void ProOrderTraverse(Tree T){
if(T == null){
return;
}
ProOrderTraverse(T->lchild); //左
ProOrderTraverse(T->rchild); //右
printf(“%c”,T-data); //根
}
下面给出Java的实现
public class BinTree<T> {
//建立以下的树的数据结构
// A
// B C
// D E F
//G
Node<T> root;
public BinTree(){
root = new Node(0,"A");
}
//构造数据
public void createTree(){
Node nodeB = new Node(1,"B");
Node nodeC = new Node(2,"C");
Node nodeD = new Node(3,"D");
Node nodeE = new Node(4,"E");
Node nodeF = new Node(5,"F");
Node nodeG = new Node(6,"G");
root.left = nodeB;
root.right = nodeC;
nodeB.left = nodeD;
nodeB.right = nodeE;
nodeC.right = nodeF;
nodeD.left = nodeG;
}
//前序遍历 根 左 右
public void preOrder(Node<T> root){
if(root == null){
return;
}
//获取遍历的数据
System.out.println(root.data);
preOrder(root.left);
preOrder(root.right);
}
//中序遍历 左 根 右
void midOrder(Node<T> root){
if(root == null){
return;
}
//获取遍历的数据
midOrder(root.left);
System.out.println(root.data);
midOrder(root.right);
}
//后续遍历 左 右 根
public void postOrder(Node<T> root){
if(root == null){
return;
}
//获取遍历的数据
postOrder(root.left);
postOrder(root.right);
System.out.println(root.data);
}
//获取结点树
public int size(Node<T> root){
if(root == null){
return 0;
}
return size(root.left) + size(root.right) + 1;
}
//获取深度
public int length(Node<T> root){
if(root == null){
return 0;
}
return length(root.left)>length(root.right)?length(root.left)+1:length(root.right) +1;
}
//数据结构类
private class Node<T>{
Node<T> right;//左结点
Node<T> left;//右结点
T data;//数据
int index;
public Node(int index,T data){
this.data = data;
this.index = index;
}
}
}