数据结构之二叉树

数据结构之二叉树

在学习Java集合类的时候，我们学习了树形结构，树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，下面我们简单来介绍下二叉树的抽象数据类型以及二叉排序树的算法。

一 定义：二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树不存在度 大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二 性质：
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
证明：下面用”数学归纳法”进行证明。
(01) 当i=1时，第i层的节点数目为2{i-1}=2{0}=1。因为第1层上只有一个根结点，所以命题成立。
(02) 假设当i>1，第i层的节点数目为2{i-1}。这个是根据(01)推断出来的！
下面根据这个假设，推断出”第(i+1)层的节点数目为2{i}”即可。
由于二叉树的每个结点至多有两个孩子，故”第(i+1)层上的结点数目” 最多是 “第i层的结点数目的2倍”。即，第(i+1)层上的结点数目最大值=2×2{i-1}=2{i}。
故假设成立，原命题得证！

性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用”性质1”可知，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故原命题得证！

性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
证明：根据”性质2”可知，高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。

性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=”0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)”。由此，得到等式一。
(等式一) n=n0+n1+n2
　 另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2n2+1
由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！
三 特点：
（1）树执行查找、删除、插入的时间复杂度都是O(logN)
（2）遍历二叉树的方法包括前序、中序、后序
（3）非平衡树指的是根的左右两边的子节点的数量不一致
（4） 在非空二叉树中，第i层的结点总数不超过 , i>=1；
（5）深度为h的二叉树最多有个结点(h>=1)，最少有h个结点；
（6）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

四 遍历：
1、先序遍历
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树
2、中序遍历
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
3、后序遍历
（1）后序遍历左子树
（2）后续遍历右子树
（3）访问根结点

五 代码实现

先序遍历

 public void printNode()
{   
  if(this.left!=null) 
    { 
    System.out.print(this.data+"->"); 
    this.left.printNode()；
    }
  else 
   {  
   	 System.out.print(this.data+"->");   
   }  
    if(this.right!=null) 
     {   
   	  this.right.printNode();
     }
}

中序遍历

public void printNode()
{
 	if(this.left!=null)
	 {
	  this.left.printNode();
 	}
	 System.out.print(this.data+"->");
	 if(this.right!=null)
 	{
	  this.right.printNode();
	 }
}

后序遍历

public void printNode()
 {   
   	 if(this.left!=null)
 	 { 
  	    this.left.printNode();
 	   } 
    	 if(this.right!=null)
     	   { 
      	    this.right.printNode(); 
       	  }
           System.out.print(this.data+"->");
       } 
  }