Android版數據結構與算法(六):樹與二叉樹

版權聲明:本文出自汪磊的博客,未經作者允許禁止轉載。

 之前的篇章主要講解了數據結構中的線性結構,所謂線性結構就是數據與數據之間是一對一的關係,接下來我們就要進入非線性結構的世界了,主要是樹與圖,好了接下來我們將會了解到樹以及二叉樹,二叉平衡樹,赫夫曼樹等原理以及java代碼的實現,先從最基礎的開始學習吧。

一、樹

樹的定義:

樹是n(n>=0)個結點的有限集合。

當n=0時,集合為空,稱為空樹。

在任意一顆非空樹中,有且僅有一個特定的結點稱為根。

當n>1時,除根結點以外的其餘結點可分成m(m>=0)個不相交的有限結點集合T1,T2….Tm.其中每個集合本身也是一棵樹,稱為根的子樹。

如下圖就是一棵樹:

可以看到,樹這種數據結構數據之間是一對一或者一對多關係,不再是一對一的關係

在上圖中節點A叫做整棵樹的根節點,一棵樹中只有一個根節點。

根節點可以生出多個孩子節點,孩子節點又可以生出多個孩子節點。比如A的孩子節點為B和C,D的孩子節點為G,H,I。

每個孩子節點只有一個父節點,比如D的父節點為B,E的父節點為C。

好了,關於樹的定義介紹到這,很簡單。

二、樹的相關術語

 

節點的度

節點含有的子樹個數,叫做節點的度。度為0的節點成為葉子結點或終端結點。比如上圖中D的度為3,E的度為1.

G,H,I,J的度為0,叫做葉子結點。

樹的度

 一棵樹中 最大節點的度樹的度。比如上圖中樹的度為3

結點的層次

從根結點算起,為第一層,其餘依次類推如上圖。B,C的層次為2,G,H的層次為4。

樹中節點的最大層次稱為樹的高度或深度。上圖中樹的高度或深度為4

三、樹的存儲結構

簡單的順序存儲不能滿足樹的實現,需要結合順序存儲和鏈式存儲來解決。

樹的存儲方式主要有三種:

雙親表示法:每個節點不僅保存自己數據還附帶一個指示器指示其父節點的角標,這種方式可以用數組來存儲。

如圖:

這種存儲方式特點是:查找一個節點的孩子節點會很麻煩但是查找其父節點很簡單。

孩子表示法:每個節點不僅保存自己數據信息還附帶指示其孩子的指示器,這種方式用鏈表來存儲比較合適。

如圖:

這種存儲方式特點是:查找一個節點的父親節點會很麻煩但是查找其孩子節點很簡單。

理想表示法:數組+鏈表的存儲方式,把每個結點的孩子結點排列起來,以單鏈表方式連接起來,則n個孩子有n個孩子鏈表,如果是葉子結點則此鏈表為空,然後n個頭指針又組成線性表,採用順序存儲方式,存儲在一個一維數組中。

如圖:

這種方式查找父節點與孩子結點都比較簡便。

以上主要介紹了樹的一些概念以及存儲方式介紹,實際我們用的更多的是二叉樹,接下來我們看下二叉樹。

四、二叉樹的概念

二叉樹定義:二叉樹是n(n>=0)個結點的有限集合,該集合或者為空,或者由一個根結點和兩課互不相交的,分別稱為根結點左子樹和右子樹的二叉樹組成。

用人話説,二叉樹是每個節點至多有兩個子樹的樹。

如圖就是一顆二叉樹:

 

 

五、特殊二叉樹

斜樹:所有結點只有左子樹的二叉樹叫做左斜樹,所有結點只有右子樹的二叉樹叫做右斜樹。

如圖:

滿二叉樹:在一棵二叉樹中,所有分支結點都有左子樹與右子樹,並且所有葉子結點都在同一層則為滿二叉樹。

如圖:

完全二叉樹:所有葉子節點都出現在 k 或者 k-1 層,而且從 1 到 k-1 層必須達到最大節點數,第 k 層可是不是慢的,但是第 k 層的所有節點必須集中在最左邊。

如圖:

 

 六、二叉樹的遍歷

二叉樹的遍歷主要有三種:先序遍歷,中序遍歷,後續遍歷,接下來我們挨個瞭解一下。

先序遍歷:先訪問根結點,再先序遍歷左子樹,再先序遍歷右子樹。

如圖所示:

 

先序遍歷結果為:ABDGHCEIF

中序遍歷:先中序遍歷左子樹,再訪問根結點,再中序遍歷右子樹。

如圖:

中序遍歷結果為:GDHBAEICF

後序遍歷:先後序遍歷左子樹,再後序遍歷右子樹,再訪問根結點。

如圖:

後序遍歷結果:GHDBIEFCA

七、java實現二叉樹

先來看看每個結點類:

 1     public class TreeNode{
 2         private String data;//自己結點數據
 3         private TreeNode leftChild;//左孩子
 4         private TreeNode rightChild;//右孩子
 5         
 6         public String getData() {
 7             return data;
 8         }
 9         
10         public void setData(String data) {
11             this.data = data;
12         }
13         
14         public TreeNode(String data){
15             this.data = data;
16             this.leftChild = null;
17             this.rightChild = null;
18         }
19     }

很簡單,每個結點信息包含自己結點數據以及指向左右孩子的指針(為了方便,我這裏就叫指針了)。

二叉樹的創建

我們創建如下二叉樹:

代碼實現:

public class BinaryTree {
    private TreeNode  root = null;

    public TreeNode getRoot() {
        return root;
    }

    public BinaryTree(){
        root = new TreeNode("A");
    }
    
    /**
     * 構建二叉樹
     *          A
     *     B        C
     *  D    E    F   G
     */
    public void createBinaryTree(){
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");
        TreeNode nodeG = new TreeNode("G");
        root.leftChild = nodeB;
        root.rightChild = nodeC;
        nodeB.leftChild = nodeD;
        nodeB.rightChild = nodeE;
        nodeC.leftChild = nodeF;
        nodeC.rightChild = nodeG;
    }
        。。。。。。。
}

創建BinaryTree的時候就已經創建根結點A,createBinaryTree()方法中創建其餘結點並且創建相應關係。

獲得二叉樹的高度

樹中節點的最大層次稱為樹的高度,因此獲得樹的高度需要遞歸獲取所有節點的高度,取最大值。

     /**
     * 求二叉樹的高度
     * @author Administrator
     *
     */
    public int getHeight(){
        return getHeight(root);
    }
    
    private int getHeight(TreeNode node) {
        if(node == null){
            return 0;
        }else{
            int i = getHeight(node.leftChild);
            int j = getHeight(node.rightChild);
            return (i<j)?j+1:i+1;
        }
    }        

獲取二叉樹的結點數

獲取二叉樹結點總數,需要遍歷左右子樹然後相加

 1     /**
 2      * 獲取二叉樹的結點數
 3      * @author Administrator
 4      *
 5      */
 6     public int getSize(){
 7         return getSize(root);
 8     }
 9     
10     private int getSize(TreeNode node) {
11         if(node == null){
12             return 0;
13         }else{
14             return 1+getSize(node.leftChild)+getSize(node.rightChild);
15         }
16     }

二叉樹的遍歷

二叉樹遍歷分為前序遍歷,中序遍歷,後續遍歷,主要也是遞歸思想,下面直接給出代碼

    /**
     * 前序遍歷——迭代
     * @author Administrator
     *
     */
    public void preOrder(TreeNode node){
        if(node == null){
            return;
        }else{
            System.out.println("preOrder data:"+node.getData());
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }

    /**
     * 中序遍歷——迭代
     * @author Administrator
     *
     */
    public void midOrder(TreeNode node){
        if(node == null){
            return;
        }else{
            midOrder(node.leftChild);
            System.out.println("midOrder data:"+node.getData());
            midOrder(node.rightChild);
        }
    }
    
    /**
     * 後序遍歷——迭代
     * @author Administrator
     *
     */
    public void postOrder(TreeNode node){
        if(node == null){
            return;
        }else{
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.println("postOrder data:"+node.getData());
        }
    }

獲取某一結點的父結點

獲取結點的父節點也是遞歸思想,先判斷當前節點左右孩子是否與給定節點信息相等,相等則當前結點即為給定結點的父節點,否則繼續遞歸左子樹,右子樹。

 1 /**
 2      * 查找某一結點的父結點
 3      * @param data
 4      * @return
 5      */
 6     public TreeNode getParent(String data){
 7         //封裝為內部結點信息
 8         TreeNode node = new TreeNode(data);
 9         //
10         if (root == null || node.data.equals(root.data)){
11             //根結點為null或者要查找的結點就為根結點,則直接返回null,根結點沒有父結點
12             return null;
13         }
14         return getParent(root, node);//遞歸查找
15     }
16 
17     public TreeNode getParent(TreeNode subTree, TreeNode node) {
18 
19         if (null == subTree){//子樹為null,直接返回null
20             return null;
21         }
22         //判斷左或者右結點是否與給定結點相等,相等則此結點即為給定結點的父結點
23         if(subTree.leftChild.data.equals(node.data) || subTree.rightChild.data.equals(node.data)){
24             return subTree;
25         }
26         //以上都不符合,則遞歸查找
27         if (getParent(subTree.leftChild,node)!=null){//先查找左子樹,左子樹找不到查詢右子樹
28             return getParent(subTree.leftChild,node);
29         }else {
30             return getParent(subTree.rightChild,node);
31         }
32     }

八、總結

以上總結了樹與二叉樹的一些概念,重點就是二叉樹的遍歷以及java代碼實現,比較簡單,沒什麼多餘解釋,下一篇瞭解一下赫夫曼樹以及二叉排序樹。

關鍵詞:結點 節點 二叉 二叉樹 node treenode 遍歷 子樹 data return

相關推薦:

Android版數據結構與算法(八):二叉排序樹

常見數據結構-二叉樹(BinaryTree)

平衡二叉樹的java實現

二叉樹

【數據結構】-----二叉樹

數據結構-平衡二叉樹 旋轉過程平衡因子分析 c和java代碼實現對比

數據結構(一)二叉樹 & avl樹 & 紅黑樹 & B樹 & B+樹

Java數據結構和算法(十)——二叉樹