阅读大话数据结构（5）

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解树，代码均为自己实现。

树

树（Tree）是n（n>=0）个结点的有限集。 n=0又称为空树。在任意一课非空的树中：有且仅有一个特定的称为跟（Root）的结点；当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树是一种一对多的数据结构。

需要注意的是：当n>0时根结点是惟一的，不可能存在多个根结点。 m>0时，子树的个数没有限制，但它们一定是互不相交的。如果相交，就不符合树的定义。

结点拥有的子树称为结点的度。度为0的结点称为叶结点或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

树中结点最大的层次称为树的深度或高度。

树的存储结构

树有两种实现方式：数组和链表；

树有三种不同表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

二叉树

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点

每个结点最多有两棵子树，所以二叉树中不存在大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。左子树和右子树是有顺序的，次序不能颠倒。就像人的左右手。即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树有5种基本形态

空二叉树。

只有一个根结点。

根结点只有左子树。

根结点只有右子树。

根结点既有左子树又有右子树。

特殊二叉树

斜树：只有左子树或者只有右子树。线性表是一种特殊的树。

满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。

满二叉树的特点有：

叶子只能在最下一层。出现在其他层就不可能达到平衡。

非叶子结点的度一定是2。否则就是“缺胳膊少腿了”。

在同样深度的二叉树中，满二叉树的结点个数越多，叶子树越多。

完全二叉树：

叶子结点只能在最下两层。

最下层的叶子一定集中在左部连续的位置。

倒数第二层，若有叶子结点，一定都在右部连续位置。

如果结点度为1，则该结点只有左孩子，即不存在右子树的情况。

同样结点数从二叉树，完全二叉树的深度最小。

判断一棵树是否是完全二叉树，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，就不是完全二叉树，否则就是。

满二叉树是特殊的完全二叉树。

完全二叉树必须先满足左后满足右，缺的元素只能是满二叉树最下一层的，高度差小于或等于1。

二叉树的性质

性质1：在二叉树的第i层上至多有2^(i-1)个结点（i≥1）。
性质2：深度为k的二叉树至多有2^k-1个结点（k≥1）。
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为|log2n+1|（|x|表示不大于x的最大整数）。
性质5：如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：
1．如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
2．如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3．如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

二叉树的存储结构

二叉树有两种存储结构：顺序存储结构和二叉链表。

顺序存储结构：一般只有完全二叉树才考虑顺序存储结构，因为完全二叉树的严格性，可以充分利用顺序存储空间。其他二叉树都会造成空间的浪费，特别是右斜树。

二叉链表：

public class TreeNode<E> {
	public E val;
	public TreeNode left,right;
	public TreeNode(E val){
		this.val = val;
		this.left = null;
		this.right = null;
	}
}

遍历二叉树

定义树

public class TreeNode {
	public int val;
	public TreeNode left,right;
	public TreeNode(int val){
		this.val = val;
		this.left = null;
		this.right = null;
	}
	
	@Override
	public String toString(){
		return this.val+"";
	}
}

前序遍历

实现一：递归方式

public ArrayList<Integer> preorderTraversal(TreeNode root) {
	        // write your code here
	        ArrayList<Integer> preorder = new ArrayList<Integer>();
	        traverse(root,preorder);
	        return preorder;
	    }
private void traverse(TreeNode root ,List<Integer> preorder) {
	        if ( root == null ) {
	            return;
	        }
	        preorder.add(root.val);
	        traverse (root.left , preorder);
	        traverse (root.right ,preorder);
	    }

实现二：分治思想

public ArrayList<Integer> preorderTraversal3(TreeNode root) {
	        // write your code here
	        ArrayList<Integer> preorder = new ArrayList<Integer>();
	        if ( root == null) {
	            return preorder;
	        }
	        
	        ArrayList<Integer> left = preorderTraversal(root.left);
	        ArrayList<Integer> right = preorderTraversal(root.right);
	        
	        preorder.add(root.val);
	        preorder.addAll(left);
	        preorder.addAll(right);
	        return preorder;
	    }

中序遍历

实现一：递归方式

public ArrayList<Integer> inorderTraversal(TreeNode root) {
       ArrayList<Integer> inorder = new ArrayList<Integer>();
        traverse(root,inorder);
        return inorder;
    }
    
 private void traverse(TreeNode root ,List<Integer> inorder) {
        if ( root == null ) {
            return;
        }
        traverse (root.left , inorder);
        inorder.add(root.val);
        traverse (root.right ,inorder);        
    }

实现二：分治思想

public ArrayList<Integer> inorderTraversal(TreeNode root) {
	        // write your code here
	        ArrayList<Integer> inorder = new ArrayList<Integer>();
	        if ( root == null) {
	            return inorder;
	        }
	        
	        ArrayList<Integer> left = inorderTraversal(root.left);
	        ArrayList<Integer> right = inorderTraversal(root.right);
	        
	        inorder.addAll(left);
	        inorder.add(root.val);
	        inorder.addAll(right); 
	        return inorder;
	    }

后序遍历

实现一：递归方式

public ArrayList<Integer> preorderTraversal(TreeNode root) {
	        // write your code here
	        ArrayList<Integer> preorder = new ArrayList<Integer>();
	        traverse(root,preorder);
	        return preorder;
	    }
private void traverse(TreeNode root ,List<Integer> preorder) {
	        if ( root == null ) {
	            return;
	        }
	        traverse (root.left , preorder);
	        traverse (root.right ,preorder);
	        preorder.add(root.val);

实现二：分治思想

public ArrayList<Integer> postorderTraversal(TreeNode root) {
       // write your code here
       ArrayList<Integer> postorder = new ArrayList<Integer>();
       if ( root == null) {
           return postorder;
       }
       
       ArrayList<Integer> left = postorderTraversal(root.left);
       ArrayList<Integer> right = postorderTraversal(root.right);
       
       postorder.addAll(left);
       postorder.addAll(right);
       postorder.add(root.val);
       
       return postorder;
       
   }

层序遍历

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result =new ArrayList<ArrayList<Integer>>();
        // write your code here
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while ( !queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            int size = queue.size();
            for ( int i =0;i < size ; i++) {
                TreeNode tmp = queue.poll();
                list.add(tmp.val);
                if(tmp.left !=null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right !=null) {
                    queue.offer(tmp.right);
                }
            }
            result.add(list);
        }
        return result;
    }

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树。

线索二叉树

为了充分利用二叉链表的空指针，把空指针指向前驱和后继，这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，

相应的二叉树就称为线索二叉树。

对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。线索化的过程就是在遍历的过程中修改空指针的过程。

为了判别某一结点的lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，引入ltag和rtag两个标志域。

1	lchild ltag data rtag rchild

其中，ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

树、森林与二叉树的转换

略

赫夫曼树

赫夫曼树：带全路径长度WPL最小的二叉树。
先取最小权值的结点作为叶子结点，逐级递增就能构造出哈夫曼树。把左结点标为0，右结点标为1，就能构造出赫夫曼编码。

树相关算法题

以下是涉及到树我的github的算法题集合

https://github.com/Luckylau/my-algorithm-training/tree/master/java/N-Series/BinaryTree%26DivideConquer%26DFS%26BFS