數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)與遍歷

定義

一個(gè)有窮的結(jié)點(diǎn)集合，可以為空。若不為空，則它是由根結(jié)點(diǎn)和稱為其左子樹(shù)和右子樹(shù)的兩個(gè)互不相交的二叉樹(shù)組成。

  1. 二叉樹(shù)的五種基本形態(tài)：
tree_state
  1. 二叉樹(shù)的子樹(shù)是有順序之分的，稱為左子樹(shù)和右子樹(shù)
left_right_tree
  1. 幾種特殊的二叉樹(shù)
    • 斜二叉樹(shù)
skew_tree
  • 完美二叉樹(shù)（滿二叉樹(shù)）
full_tree
  • 完全二叉樹(shù)
    有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中結(jié)點(diǎn)按從上之下，從左至右的順序進(jìn)行編號(hào)，編號(hào)為i(1<=1<=n)結(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i結(jié)點(diǎn)在二叉樹(shù)中位置相同

二叉樹(shù)的幾個(gè)重要性質(zhì)：

  1. 在二叉樹(shù)的第i層上最多有2 i-1 個(gè)節(jié)點(diǎn) 。（i>=1）
  2. 二叉樹(shù)中如果深度為k,那么最多有2k-1個(gè)節(jié)點(diǎn)。(k>=1）
  3. 對(duì)任何非空二叉樹(shù)T，若n0表示度數(shù)為0的節(jié)點(diǎn) n2表示度數(shù)為2的節(jié)點(diǎn),那么n0=n2+1;
  4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2 n + 1

這里在補(bǔ)充一下樹(shù)的其他一些性質(zhì)和概念：

  1. 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱為結(jié)點(diǎn)的度；
  2. 樹(shù)的度：樹(shù)中各節(jié)點(diǎn)的度的最大值；因此，二叉樹(shù)的度最大為2；
  3. 結(jié)點(diǎn)的層數(shù)：規(guī)定根節(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)為他的雙親結(jié)點(diǎn)層數(shù)加1
  4. 輸?shù)纳疃龋簶?shù)中所有結(jié)點(diǎn)的最大層數(shù)。

二叉樹(shù)的抽象數(shù)據(jù)類型(ADT)

對(duì)于二叉樹(shù)的元素，主要的操作包括：

  1. 判別二叉樹(shù)是否為空
  2. 遍歷二叉樹(shù)，按特定的順序訪問(wèn)每個(gè)結(jié)點(diǎn)
    • 前序遍歷：根節(jié)點(diǎn)-->左子樹(shù)-->右子樹(shù)
    • 中序遍歷：左子樹(shù)-->根節(jié)點(diǎn)-->右子樹(shù)
    • 后序遍歷：左子樹(shù)-->右子樹(shù)-->根節(jié)點(diǎn)
    • 層序遍歷：從上至下，從左至右。
  3. 創(chuàng)建一個(gè)二叉樹(shù)

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)

linear_tree

使用順序存儲(chǔ)結(jié)構(gòu)，對(duì)完全二叉樹(shù)這種結(jié)構(gòu)是非常合適的?？梢园凑諒纳现?，從左至右順序存儲(chǔ)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)父子關(guān)系。

linear_tree_array

完全二叉樹(shù)的這種存儲(chǔ)結(jié)構(gòu)，有以下特點(diǎn)

  • 非根節(jié)點(diǎn)（序號(hào)i>1)的父節(jié)點(diǎn)序號(hào)（數(shù)組下標(biāo)）是 i/2 (取整）。
  • 結(jié)點(diǎn)（序號(hào)為i）的左孩子結(jié)點(diǎn)的序號(hào)是2i,如果2i>n,則沒(méi)有左孩子；
  • 結(jié)點(diǎn)（序號(hào)為i）的右孩子結(jié)點(diǎn)的序號(hào)是2i+1,如果2i+1>n,則沒(méi)有右孩子。

一般普通的二叉樹(shù)，在其空余位置補(bǔ)充控制，當(dāng)做是完全二叉樹(shù)，采用數(shù)組結(jié)構(gòu)存儲(chǔ)，將導(dǎo)致存儲(chǔ)空間的浪費(fèi)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)包含三個(gè)關(guān)鍵屬性:指向左子樹(shù)的指針，數(shù)據(jù)域，指向右子樹(shù)的指針；根據(jù)這個(gè)敘述，我們可以按如下結(jié)構(gòu)定義結(jié)點(diǎn)。

link_tree
結(jié)點(diǎn)定義
/**
 * Created by engineer on 2017/10/23.
 * <p>
 * 二叉樹(shù)結(jié)點(diǎn)定義
 */

public class TreeNode<T> {

    // 數(shù)據(jù)域
    private T data;
    // 左子樹(shù)
    private TreeNode<T> leftChild;
    // 右子樹(shù)
    private TreeNode<T> rightChild;

    public TreeNode(T data) {
        this(null, data, null);
    }

    public TreeNode(TreeNode<T> leftChild, T data, TreeNode<T> rightChild) {
        this.leftChild = leftChild;
        this.data = data;
        this.rightChild = rightChild;
    }

    public T getData() {
        return data;
    }

    public TreeNode<T> getLeftChild() {
        return leftChild;
    }

    public TreeNode<T> getRightChild() {
        return rightChild;
    }
}
二叉樹(shù)初始化

我們就以下圖為例，構(gòu)造一顆二叉樹(shù)。

/**
     * 構(gòu)建二叉樹(shù)
     *
     * @return 樹(shù)根
     */
    TreeNode CreateTree() {
        TreeNode<String> nodeH = new TreeNode<>("H");
        TreeNode<String> nodeG = new TreeNode<>("G");

        TreeNode<String> nodeF = new TreeNode<>(nodeH, "F", null);
        TreeNode<String> nodeE = new TreeNode<>(nodeG, "E", null);
        TreeNode<String> nodeD = new TreeNode<>("D");

        TreeNode<String> nodeC = new TreeNode<>(null, "C", nodeF);
        TreeNode<String> nodeB = new TreeNode<>(nodeD, "B", nodeE);
        TreeNode<String> nodeA = new TreeNode<>(nodeB, "A", nodeC);
        return nodeA;
    }

這樣，我們就按上圖所示構(gòu)建了一顆二叉樹(shù)，返回二叉樹(shù)的根結(jié)點(diǎn)。

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷是二叉樹(shù)最要的操作，也是二叉樹(shù)的核心。從二叉樹(shù)的定義我們可以得知，二叉樹(shù)是一種遞歸形式的數(shù)據(jù)結(jié)構(gòu)，根結(jié)點(diǎn)下的左右子樹(shù)又分別是二叉樹(shù)；因此這使得二叉樹(shù)的遍歷離不開(kāi)遞歸這種思想。

很顯然，對(duì)于二叉樹(shù)的三種遍歷，我們就可以借助其自身的特性，通過(guò)遞歸實(shí)現(xiàn)。

  • 二叉樹(shù)的遞歸遍歷實(shí)現(xiàn)
/**
     * 訪問(wèn)每個(gè)結(jié)點(diǎn)
     *
     * @param node
     */
    private void visitNode(TreeNode node) {
        System.out.print(node.getData().toString());
        System.out.print(" ");
    }

    /**
     * 前序遍歷-遞歸實(shí)現(xiàn)
     *
     * @param node
     */
    void preTraversal(TreeNode node) {
        if (node != null) {
            visitNode(node);
            preTraversal(node.getLeftChild());
            preTraversal(node.getRightChild());
        }
    }

    /**
     * 中序遍歷-遞歸實(shí)現(xiàn)
     *
     * @param node
     */
    void traversal(TreeNode node) {
        if (node != null) {
            traversal(node.getLeftChild());
            visitNode(node);
            traversal(node.getRightChild());
        }
    }

    /**
     * 后序遍歷-遞歸實(shí)現(xiàn)
     * @param node
     */
    void postTraversal(TreeNode node) {
        if (node != null) {
            postTraversal(node.getLeftChild());
            postTraversal(node.getRightChild());
            visitNode(node);
        }
    }

可以看到，使用遞歸實(shí)現(xiàn)二叉樹(shù)的遍歷十分簡(jiǎn)單，但我們也可以考慮使用非遞歸的形式，使用棧。

嚴(yán)格來(lái)說(shuō)，使用棧實(shí)現(xiàn)二叉樹(shù)的遍歷，其實(shí)還是遞歸思想，只不過(guò)是我們自己用棧完成了遞歸實(shí)現(xiàn)中系統(tǒng)幫我們完成的工作。

本質(zhì)上來(lái)說(shuō)，二叉樹(shù)這種遞歸的數(shù)據(jù)結(jié)構(gòu)，他的遍歷是離不開(kāi)遞歸思想的，只不過(guò)看我們?cè)趺慈ダ斫膺f歸的實(shí)現(xiàn)了。

  • 二叉樹(shù)的非遞歸實(shí)現(xiàn)
/**
     * 前序遍歷-迭代實(shí)現(xiàn)
     * @param node
     */
    void preTraversalIteration(TreeNode node) {
        // 創(chuàng)建一個(gè)棧
        Stack<TreeNode> mStack = new Stack<>();
        while (true) {
            while (node != null) { // 非葉子結(jié)點(diǎn)的子樹(shù)
                // 前序遍歷，先訪問(wèn)根結(jié)點(diǎn)
                visitNode(node);
                // 將當(dāng)前結(jié)點(diǎn)壓入棧
                mStack.push(node);
                // 對(duì)左子樹(shù)繼續(xù)進(jìn)行前序遍歷
                node=node.getLeftChild();
            }

            if (mStack.isEmpty()) {
                //所有元素已遍歷完成
                break;
            }
            // 彈出棧頂結(jié)點(diǎn)
            node=mStack.pop();
            // 右子樹(shù)前序遍歷
            node=node.getRightChild();
        }
    }

    /**
     * 中序遍歷-迭代實(shí)現(xiàn)
     * @param node
     */
    void TraversalIteration(TreeNode node) {
        // 創(chuàng)建一個(gè)棧
        Stack<TreeNode> mStack = new Stack<>();
        while (true) {
            while (node != null) { // 非葉子結(jié)點(diǎn)的子樹(shù)
                // 將當(dāng)前結(jié)點(diǎn)壓入棧
                mStack.push(node);
                // 對(duì)左子樹(shù)繼續(xù)進(jìn)行中序遍歷
                node=node.getLeftChild();
            }

            if (mStack.isEmpty()) {
                //所有元素已遍歷完成
                break;
            }
            // 彈出棧頂結(jié)點(diǎn)
            node=mStack.pop();
            // 中序遍歷，訪問(wèn)根結(jié)點(diǎn)
            visitNode(node);
            // 右子樹(shù)中序遍歷
            node=node.getRightChild();
        }
    }

    /**
     * 后序遍歷-迭代實(shí)現(xiàn)
     * @param node
     */
    void postTraversalIteration(TreeNode node) {
        // 創(chuàng)建一個(gè)棧
        Stack<TreeNode> mStack = new Stack<>();
        while (true) {
            if (node != null) {
                //當(dāng)前結(jié)點(diǎn)非空，壓入棧
                mStack.push(node);
                // 左子樹(shù)繼續(xù)遍歷
                node=node.getLeftChild();
            }else {
                // 左子樹(shù)為空

                if(mStack.isEmpty()){
                    return;
                }

                if (mStack.lastElement().getRightChild() == null) {
                    // 棧頂元素右子樹(shù)為空，則當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)，輸出
                    node=mStack.pop();
                    visitNode(node);
                    while (node == mStack.lastElement().getRightChild()) {
                        visitNode(mStack.lastElement());
                        node=mStack.pop();
                        if (mStack.isEmpty()) {
                            break;
                        }
                    }
                }

                if (!mStack.isEmpty()) {
                    node=mStack.lastElement().getRightChild();
                }else {
                    node=null;
                }
            }
        }
    }

可以看到，雖說(shuō)是非遞歸實(shí)現(xiàn)，但本質(zhì)上還是依靠棧先進(jìn)后出的特性，實(shí)現(xiàn)了遞歸訪問(wèn)每個(gè)結(jié)點(diǎn)的操作，無(wú)非就是在前、中、后三種順序下，訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同而已。這里，前序和中序遍歷的實(shí)現(xiàn)其實(shí)很容易理解，后續(xù)遍歷的實(shí)現(xiàn)很考究對(duì)棧的使用理解。

  • 層序遍歷

最后，再來(lái)說(shuō)一說(shuō)層序遍歷。顧名思義，層序遍歷就是從上到下按層，從左至右依次訪問(wèn)每個(gè)結(jié)點(diǎn)。這種遍歷非常用規(guī)律，就是從根節(jié)點(diǎn)下一層開(kāi)始，優(yōu)先訪問(wèn)每一層所有的雙親結(jié)點(diǎn)，然后依次訪問(wèn)每個(gè)結(jié)點(diǎn)的左右兒子。也就是說(shuō)，從上到下，先遇見(jiàn)到結(jié)點(diǎn)先訪問(wèn)，后遇到的結(jié)點(diǎn)后訪問(wèn)，這典型的就是隊(duì)列的思想，因此我們可以使用隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層序遍歷。

/**
     * 層序遍歷
     * @param node
     */
    void levelTraversal(TreeNode node) {
        //創(chuàng)建隊(duì)列
        Queue<TreeNode> mNodeQueue = new LinkedList<>();
        // 根結(jié)點(diǎn)加入隊(duì)列
        mNodeQueue.add(node);

        TreeNode temp;

        while (!mNodeQueue.isEmpty()) {
            //元素出隊(duì)列
            temp=mNodeQueue.poll();
            //輸出
            visitNode(temp);
            if (temp.getLeftChild() != null) {
                // 左子樹(shù)入隊(duì)列
                mNodeQueue.add(temp.getLeftChild());
            }

            if (temp.getRightChild() != null) {
                //右子樹(shù)入隊(duì)列
                mNodeQueue.add(temp.getRightChild());
            }
        }
    }

測(cè)試二叉樹(shù)的實(shí)現(xiàn)

最后，用一個(gè)測(cè)試類測(cè)試一下我們對(duì)二叉樹(shù)的實(shí)現(xiàn)。

/**
 * Created by engineer on 2017/10/24.
 */

public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTree mBinaryTree = new BinaryTree();

        TreeNode root = mBinaryTree.CreateTree();

        System.out.print("前序遍歷-遞歸實(shí)現(xiàn):");
        mBinaryTree.preTraversal(root);
        System.out.print("\n中序遍歷-遞歸實(shí)現(xiàn):");
        mBinaryTree.traversal(root);
        System.out.print("\n后序遍歷-遞歸實(shí)現(xiàn):");
        mBinaryTree.postTraversal(root);
        System.out.println();
        System.out.print("\n前序遍歷-迭代實(shí)現(xiàn):");
        mBinaryTree.preTraversalIteration(root);
        System.out.print("\n中序遍歷-迭代實(shí)現(xiàn):");
        mBinaryTree.TraversalIteration(root);
        System.out.print("\n后序遍歷-迭代實(shí)現(xiàn):");
        mBinaryTree.postTraversalIteration(root);
        System.out.println();
        System.out.print("\n層序遍歷:");
        mBinaryTree.levelTraversal(root);

    }
}

得到輸出：

前序遍歷-遞歸實(shí)現(xiàn):A B D E G C F H 
中序遍歷-遞歸實(shí)現(xiàn):D B G E A C H F 
后序遍歷-遞歸實(shí)現(xiàn):D G E B H F C A 

前序遍歷-迭代實(shí)現(xiàn):A B D E G C F H 
中序遍歷-迭代實(shí)現(xiàn):D B G E A C H F 
后序遍歷-迭代實(shí)現(xiàn):D G E B H F C A 

層序遍歷:A B C D E F G H

嗯，和預(yù)期想象的一致。

好了，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷就到這里了。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容