二叉樹的遍歷

二叉樹的遍歷分為三種：前序遍歷 中序遍歷 后序遍歷

特殊的二叉樹：

      （1）斜樹：顧名思義，斜樹一定是要斜的；所有的結(jié)點(diǎn)都只有左子樹的二叉樹叫左斜樹，所有的結(jié)點(diǎn)都只有右子樹的二叉樹叫右斜樹；其實(shí)，線性表就可以理解為樹的一種特殊的表現(xiàn)形式；

       （2）滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹;如圖：

         （3）完全二叉樹：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中位置完全相同，那么這棵二叉樹稱為完全二叉樹；或者這樣理解：在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)，則稱此樹為完全二叉樹；

所以我們可以這樣判斷完全二叉樹：那就是看著樹的示意圖，心中默默給每個(gè)結(jié)點(diǎn)按照滿二叉樹的結(jié)構(gòu)逐層順序編號(hào)，如果編號(hào)出現(xiàn)空檔，就說明不是完全二叉樹，否則就是；

二叉樹的實(shí)現(xiàn)：同樣，二叉樹也可以通過順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)來實(shí)現(xiàn)；

          二叉樹的順序存儲(chǔ)就是用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置，也就是數(shù)組的下標(biāo)要能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系，比如父結(jié)點(diǎn)與子結(jié)點(diǎn)的邏輯關(guān)系，子結(jié)點(diǎn) 與子結(jié)點(diǎn)之間的關(guān)系；但順序存儲(chǔ)的實(shí)用性不強(qiáng)；

          所以一般采用鏈?zhǔn)酱鎯?chǔ)；

二叉樹的遍歷：是指從根結(jié)點(diǎn)出發(fā)，按照某種次序，依次訪問二叉樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次；

 二叉樹的遍歷方式有好多種，如果我們限制了從左到右的習(xí)慣方式，那么主要就有以下幾種：

         （1）前序遍歷：先訪問子結(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹；如下圖，遍歷順序是：ABDGHCEIF

         （2）中序遍歷：從根結(jié)點(diǎn)開始（但并不是先訪問根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹，然后方式根結(jié)點(diǎn)，最后中序遍歷右樹，如圖，遍歷的順序是：GDHBAEICF

           （3）后序遍歷：從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問左右子樹，最后是訪問根結(jié)點(diǎn)；如圖，遍歷的順序是：GHDBIEFCA

          （4）層序遍歷：從樹的第一層，也就是根結(jié)點(diǎn)開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)進(jìn)行逐個(gè)訪問；如圖，遍歷順序?yàn)椋篈BCDEFGHI

二叉樹遍歷的java實(shí)現(xiàn)

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)");  	    }  	      	    /** 	     * 創(chuàng)建一棵二叉樹 	     * <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);  	    }  	      	    //節(jié)點(diǎn)個(gè)數(shù)  	    public int size(){  	        return size(root);  	    }  	      	      	    private int height(TreeNode subTree){  	        if(subTree==null)  	            return 0;//遞歸結(jié)束：空樹高度為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);  	        }  	    }  	      	    //返回雙親結(jié)點(diǎn)  	    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)  	            //返回父結(jié)點(diǎn)地址  	            return subTree;  	        TreeNode p;  	        //現(xiàn)在左子樹中找，如果左子樹中沒有找到，才到右子樹去找  	        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;  	    }  	      	    //在釋放某個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)的左右子樹都已經(jīng)釋放，  	    //所以應(yīng)該采用后續(xù)遍歷，當(dāng)訪問某個(gè)結(jié)點(diǎn)時(shí)將該結(jié)點(diǎn)的存儲(chǔ)空間釋放  	    public void destroy(TreeNode subTree){  	        //刪除根為subTree的子樹  	        if(subTree!=null){  	            //刪除左子樹  	            destroy(subTree.leftChild);  	            //刪除右子樹  	            destroy(subTree.rightChild);  	            //刪除根結(jié)點(diǎn)  	            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);  	        }  	    }  	      	    //后續(xù)遍歷  	    public void postOrder(TreeNode subTree) {  	        if (subTree != null) {  	            postOrder(subTree.leftChild);  	            postOrder(subTree.rightChild);  	            visted(subTree);  	        }  	    }  	      	    //前序遍歷的非遞歸實(shí)現(xiàn)  	    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;  	            }   	        }  	    }  	      	    //中序遍歷的非遞歸實(shí)現(xiàn)  	    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;  	            }  	        }  	    }  	      	    //后序遍歷的非遞歸實(shí)現(xiàn)  	    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);  	            }  	            //當(dāng)前結(jié)點(diǎn)無右子樹或右子樹已經(jīng)輸出  	            while(p!=null&&(p.rightChild==null||p.rightChild==node)){  	                visted(p);  	                //紀(jì)錄上一個(gè)已輸出結(jié)點(diǎn)  	                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);;  	    }  	    	    	    //測(cè)試  	    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("***非遞歸實(shí)現(xiàn)****(前序遍歷)[ABDECF]遍歷*****************");  	        bt.nonRecPreOrder(bt.root);  	          	        System.out.println("***非遞歸實(shí)現(xiàn)****(中序遍歷)[DBEACF]遍歷*****************");  	        bt.nonRecInOrder(bt.root);  	          	        System.out.println("***非遞歸實(shí)現(xiàn)****(后序遍歷)[DEBFCA]遍歷*****************");  	        bt.noRecPostOrder(bt.root);  	    	    } 	    	    }