二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成. 從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5中表現形式 特殊的二叉樹：
（1）斜樹：顧名思義，斜樹一定是要斜的；所有的結點都只有左子樹的二叉樹叫左斜樹，所有的結點都只有右子樹的二叉樹叫右斜樹；其實，線性表就可以理解為樹的一種特殊的表現形式；
（2）滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹;如圖：
（3）完全二叉樹：對一棵具有n個結點的二叉樹按層序編號，如果編號為i的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，那么這棵二叉樹稱為完全二叉樹；或者這樣理解：在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是右邊缺少連續若干個結點，則稱此樹為完全二叉樹；
所以我們可以這樣判斷完全二叉樹：那就是看著樹的示意圖，心中默默給每個結點按照滿二叉樹的結構逐層順序編號，如果編號出現空檔，就說明不是完全二叉樹，否則就是；
二叉樹的實現：同樣，二叉樹也可以通過順序存儲和鏈式存儲來實現；
二叉樹的順序存儲就是用一維數組存儲二叉樹中的結點，并且結點的存儲位置，也就是數組的下標要能體現結點之間的邏輯關系，比如父結點與子結點的邏輯關系，子結點 與子結點之間的關系；但順序存儲的實用性不強；
所以一般采用鏈式存儲；
二叉樹的遍歷：是指從根結點出發，按照某種次序，依次訪問二叉樹中所有結點，使得每個結點被訪問一次且僅被訪問一次；
二叉樹的遍歷方式有好多種，如果我們限制了從左到右的習慣方式，那么主要就有以下幾種：
（1）前序遍歷：先訪問子結點，然后前序遍歷左子樹，再前序遍歷右子樹；如下圖，遍歷順序是：ABDGHCEIF
（2）中序遍歷：從根結點開始（但并不是先訪問根結點），中序遍歷根結點的左子樹，然后方式根結點，最后中序遍歷右樹，如圖，遍歷的順序是：GDHBAEICF
（3）后序遍歷：從左到右先葉子后結點的方式遍歷訪問左右子樹，最后是訪問根結點；如圖，遍歷的順序是：GHDBIEFCA
（4）層序遍歷：從樹的第一層，也就是根結點開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序對結點進行逐個訪問；如圖，遍歷順序為：ABCDEFGHI
package test.tree;public class TreeNode { public int key; public String data; public TreeNode leftChild; public TreeNode rightChild; public boolean isVisted=false; public TreeNode() { } public TreeNode(int key, String data) { this.key = key; this.data = data; } public TreeNode(int key, String data, TreeNode leftChild, TreeNode rightChild) { this.key = key; this.data = data; this.leftChild = leftChild; this.rightChild = rightChild; }}二叉樹處理遍歷 package test.tree;import java.util.Stack;public class BinaryTree { PRivate TreeNode root=null; public BinaryTree(){ root=new TreeNode(1,"rootNode(A)"); } /** * 創建一棵二叉樹 * <pre> * A * B C * D E F * </pre> * @param root */ public void createBinTree(TreeNode root){ TreeNode newNodeB = new TreeNode(2,"B"); TreeNode newNodeC = new TreeNode(3,"C"); TreeNode newNodeD = new TreeNode(4,"D"); TreeNode newNodeE = new TreeNode(5,"E"); TreeNode newNodeF = new TreeNode(6,"F"); root.leftChild=newNodeB; root.rightChild=newNodeC; root.leftChild.leftChild=newNodeD; root.leftChild.rightChild=newNodeE; root.rightChild.rightChild=newNodeF; } public boolean isEmpty(){ return root==null; } //樹的高度 public int height(){ return height(root); } //節點個數 public int size(){ return size(root); } private int height(TreeNode subTree){ if(subTree==null) return 0;//遞歸結束：空樹高度為0 else{ int i=height(subTree.leftChild); int j=height(subTree.rightChild); return (i<j)?(j+1):(i+1); } } private int size(TreeNode subTree){ if(subTree==null){ return 0; }else{ return 1+size(subTree.leftChild) +size(subTree.rightChild); } } //返回雙親結點 public TreeNode parent(TreeNode element){ return (root==null|| root==element)?null:parent(root, element); } public TreeNode parent(TreeNode subTree,TreeNode element){ if(subTree==null) return null; if(subTree.leftChild==element||subTree.rightChild==element) //返回父結點地址 return subTree; TreeNode p; //現在左子樹中找，如果左子樹中沒有找到，才到右子樹去找 if((p=parent(subTree.leftChild, element))!=null) //遞歸在左子樹中搜索 return p; else //遞歸在右子樹中搜索 return parent(subTree.rightChild, element); } public TreeNode getLeftChildNode(TreeNode element){ return (element!=null)?element.leftChild:null; } public TreeNode getRightChildNode(TreeNode element){ return (element!=null)?element.rightChild:null; } public TreeNode getRoot(){ return root; } //在釋放某個結點時，該結點的左右子樹都已經釋放， //所以應該采用后續遍歷，當訪問某個結點時將該結點的存儲空間釋放 public void destroy(TreeNode subTree){ //刪除根為subTree的子樹 if(subTree!=null){ //刪除左子樹 destroy(subTree.leftChild); //刪除右子樹 destroy(subTree.rightChild); //刪除根結點 subTree=null; } } public void traverse(TreeNode subTree){ System.out.println("key:"+subTree.key+"--name:"+subTree.data);; traverse(subTree.leftChild); traverse(subTree.rightChild); } //前序遍歷 public void preOrder(TreeNode subTree){ if(subTree!=null){ visted(subTree); preOrder(subTree.leftChild); preOrder(subTree.rightChild); } } //中序遍歷 public void inOrder(TreeNode subTree){ if(subTree!=null){ inOrder(subTree.leftChild); visted(subTree); inOrder(subTree.rightChild); } } //后續遍歷 public void postOrder(TreeNode subTree) { if (subTree != null) { postOrder(subTree.leftChild); postOrder(subTree.rightChild); visted(subTree); } } //前序遍歷的非遞歸實現 public void nonRecPreOrder(TreeNode p){ Stack<TreeNode> stack=new Stack<TreeNode>(); TreeNode node=p; while(node!=null||stack.size()>0){ while(node!=null){ visted(node); stack.push(node); node=node.leftChild; } while(stack.size()>0){ node=stack.pop(); node=node.rightChild; } } } //中序遍歷的非遞歸實現 public void nonRecInOrder(TreeNode p){ Stack<TreeNode> stack =new Stack<TreeNode>(); TreeNode node =p; while(node!=null||stack.size()>0){ //存在左子樹 while(node!=null){ stack.push(node); node=node.leftChild; } //棧非空 if(stack.size()>0){ node=stack.pop(); visted(node); node=node.rightChild; } } } //后序遍歷的非遞歸實現 public void noRecPostOrder(TreeNode p){ Stack<TreeNode> stack=new Stack<TreeNode>(); TreeNode node =p; while(p!=null){ //左子樹入棧 for(;p.leftChild!=null;p=p.leftChild){ stack.push(p); } //當前結點無右子樹或右子樹已經輸出 while(p!=null&&(p.rightChild==null||p.rightChild==node)){ visted(p); //紀錄上一個已輸出結點 node =p; if(stack.empty()) return; p=stack.pop(); } //處理右子樹 stack.push(p); p=p.rightChild; } } public void visted(TreeNode subTree){ subTree.isVisted=true; System.out.println("key:"+subTree.key+"--name:"+subTree.data);; } //測試 public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.createBinTree(bt.root); System.out.println("the size of the tree is " + bt.size()); System.out.println("the height of the tree is " + bt.height()); System.out.println("*******(前序遍歷)[ABDECF]遍歷*****************"); bt.preOrder(bt.root); System.out.println("*******(中序遍歷)[DBEACF]遍歷*****************"); bt.inOrder(bt.root); System.out.println("*******(后序遍歷)[DEBFCA]遍歷*****************"); bt.postOrder(bt.root); System.out.println("***非遞歸實現****(前序遍歷)[ABDECF]遍歷*****************"); bt.nonRecPreOrder(bt.root); System.out.println("***非遞歸實現****(中序遍歷)[DBEACF]遍歷*****************"); bt.nonRecInOrder(bt.root); System.out.println("***非遞歸實現****(后序遍歷)[DEBFCA]遍歷*****************"); bt.noRecPostOrder(bt.root); } }
新聞熱點
疑難解答
