java樹的存儲結構以及二叉樹的遍歷實現(xiàn)

本篇內容主要講解“java樹的存儲結構以及二叉樹的遍歷實現(xiàn)”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“java樹的存儲結構以及二叉樹的遍歷實現(xiàn)”吧!

樹的存儲結構

數(shù)據(jù)結構中定義的樹，類似于下圖：

前面我們說過，計算機只能順序或者鏈式存儲數(shù)據(jù)，所以樹這樣的結構是不能直接存儲的，所以要將其轉換為順序或鏈式來存儲。主要有以下三種方式：

雙親表示法

這一方法基于數(shù)組，也基于樹的每個結點（除了根結點）都有且僅有一個父結點。做法是存儲每個結點時，增加一個域指向其父結點的位置。比如上圖，按照雙親表示法存儲在數(shù)組中，結構就是這樣的：

實際操作時，就是從上往下，層序遍歷一棵樹，并為相應的域賦值即可。這種存儲方式，可以快速獲取任意結點的父結點位置，但相反的操作，要獲取一個結點的子結點，就需要遍歷了。

但是以上問題可以通過增加一個域來解決，可以增加一個firstChild域，表示一個結點最左邊的子結點，例如對于以上這棵樹，A的firstChild是B，B的firstChild是D。這樣我們就可以得到任何一個結點的第一個子結點了，而所有的子結點又是連續(xù)的，所以就可以方便的獲取到所有的子結點。

這引發(fā)了我們的思考，是不是通過增加域，我們可以獲取任何想要的關系？比如可以存儲兄弟結點的位置。是的，這是很靈活的，但是也要注意設計合理，過于龐大的數(shù)據(jù)單元，會占用大量內存空間，這就仁者見仁，智者見智了。

孩子表示法

這一方式，是建立多個指針域，指向它所有子結點的地址。也就是任何一個結點，都掌握它所有子結點的信息。我們使用數(shù)組+鏈表的方式來實現(xiàn)。以上這棵樹使用孩子表示法示意結構如下：

這樣對任何一個結點，都可以直接找到它的全部子結點了。我們還可以把它和上述的雙親表示法結合起來，以賦予它更多的能力。

孩子兄弟表示法

這種方式，可以把一棵普通的樹，轉換成二叉樹。它的做法是用兩個指針分別指向它的第一個子結點和它的第一個右兄弟結點。

文章開始處的這棵樹，用孩子兄弟表示法結果如下所示：

滿二叉樹與完全二叉樹

之前的文章里介紹了二叉樹的概念，其實二叉樹中還有幾種特殊的二叉樹，這里介紹兩種。

滿二叉樹

在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹是一棵完美的二叉樹，它的每一棵子樹都是左右對稱的。如下就是一棵滿二叉樹：

完全二叉樹

對一棵具有n個結點的二叉樹按層序編號，如果編號為i (1≤i≤n) 的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。

這句話可能說的不太好理解，簡單來說，完全二叉樹就是滿二叉樹少幾個葉子，而且葉子是從右向左少的。比如下圖就是一棵完全二叉樹，把它和上方的滿二叉樹對比可以發(fā)現(xiàn)，從上往下一層一層數(shù)過去，它們是一模一樣的，僅在最后完全二叉樹缺少幾個葉子。如果中間有任何一個結點對應不上，它就不是一棵完全二叉樹。

二叉樹的存儲

二叉樹也可以順序或鏈式存儲，鏈式存儲和樹的孩子表示法差不多，定義一個lchild和rchild指針分別指向左孩子和右孩子即可。它的順序存儲卻比普通的樹要簡單的多，接下來我們看下二叉樹的順序存儲是如何實現(xiàn)的。

順序存儲

以上述完全二叉樹為例，可以發(fā)現(xiàn)每個結點的位置和它在線性表中的位置是一樣的，所以不需要指針指向它的父結點或者子結點，我們直接按照層序遍歷方式把它存儲在數(shù)組中即可。結果如下：

以上是針對完全二叉樹而言，那如果不是一棵完全二叉樹呢？比如以下這棵樹：

從第三行開始，數(shù)據(jù)的位置和存儲在數(shù)組中的位置不再一樣了，比如5在數(shù)組中的下標是4。這時我們需要用空位補充，把這棵二叉樹和一棵完全二叉樹對比，缺少的部分在數(shù)組中以空或者特定的字符補充。以此二叉樹為例，它對應的完全二叉樹如下，其中虛線連接的部分實際不存在。

然后按照完全二叉樹的方式，在數(shù)組中存儲時遇到實際不存在的元素就以空表示，結果如下：

這樣數(shù)組就可以正確的對應原二叉樹了。這種方式的可行性在于，對一棵一般的二叉樹而言，可以構造的最小的完全二叉樹是唯一的，這里最小指不在完全二叉樹結尾增加無用的葉子結點。

順序存儲的問題也就由此暴露了，相對于完全二叉樹而言，更多的樹都是這種一般結構，也就意味著數(shù)組中會有大量的空位，這大大的浪費了內存。

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

二叉樹的遍歷分為前序、中序、后序三種，還有一種叫做層序遍歷，就是從上往下一層一層進行遍歷。之前介紹了這幾種遍歷的概念，接下來我們以上述的一般二叉樹為樣例來演示這幾種遍歷。

1. 構造二叉樹

我們以鏈式存儲方式進行演示，結點的結構如下：

class TreeNode{
    Integer data;
    TreeNode lChild;
    TreeNode rChild;

    public TreeNode(Integer data){
        this.data = data;
    }
}

2. 層序遍歷

層序遍歷的特點是先獲取根結點的值，然后獲取它的左孩子，再獲取它的右孩子，如上方這棵樹中，獲取順序1->2->3，這部分非常簡單。但下一步卻要從3回到2，獲取到5后再回到3，這樣在2和3之間來回跳躍，便不那么好處理了。我們可以借助隊列來完成。

為了便于演示，我們用黑色代表當前結點，藍色代表它的左孩子，紅色代表它的右孩子，建立如下模型：

以上述樹為例，借助Queue實現(xiàn)的原理如下：

首先根結點入隊，入隊時，剪掉它的兩個孩子，并按照左右順序把兩個孩子都入隊，然后根結點丟棄：

然后對結點2進行同樣的處理：

接下來處理結點3：

到這里相信大家已經(jīng)發(fā)現(xiàn)了，獲取到2之后下一步獲取的是3，而獲取5被巧妙的放在了3之后，這樣我們就可以一層層的遍歷二叉樹了。Java代碼如下所示：

private void levelTraverse(TreeNode tree){
    if(tree == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(tree);
    TreeNode node;
    while (!queue.isEmpty()) {
        node = queue.poll();
        System.out.println("Node is " + node.data);

        if(node.lChild!=null){
            queue.offer(node.lChild);
        }
        if(node.rChild!=null){
            queue.offer(node.rChild);
        }
    }
}

3. 前序遍歷

前序遍歷可以簡單的使用遞歸實現(xiàn)，代碼一目了然，如下：

private void preOrderTraverse(TreeNode tree){
    if (tree == null) {
        return;
    }
    System.out.println("Node is " + tree.data);

    preOrderTraverse(tree.lChild);
    preOrderTraverse(tree.rChild);
}

4. 中序遍歷

private void inOrderTraverse(TreeNode tree){
    if (tree == null) {
        return;
    }
    inOrderTraverse(tree.lChild);

    System.out.println("Node is " + tree.data);

    inOrderTraverse(tree.rChild);
}

5. 后續(xù)遍歷

private void postOrderTraverse(TreeNode tree){
    if (tree == null) {
        return;
    }
    postOrderTraverse(tree.lChild);
    postOrderTraverse(tree.rChild);
    System.out.println("Node is " + tree.data);
}

到此，相信大家對“java樹的存儲結構以及二叉樹的遍歷實現(xiàn)”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！