數據結構與算法——二叉樹（上）

xeblog 發布于2019-08-16 16:13 / 1320人閱讀

摘要：什么是樹前面說到的幾種數據結構都是線性的，例如鏈表棧隊列等，今天就來學習一種非線性的數據結構樹。在上圖中的幾種二叉樹中，有兩個是比較特殊的，分別是滿二叉樹和完全二叉樹。除了使用數組存儲二叉樹外，最常用的便是使用鏈表法來儲存二叉樹了。

1. 什么是樹？

前面說到的幾種數據結構都是線性的，例如鏈表、棧、隊列等，今天就來學習一種非線性的數據結構——樹。先來看看幾種樹的結構：

有沒有發現，其實樹這種結構跟我們現實生活中的“樹”非常的相似，像上圖中的這棵“樹”，節點 A 稱作 B 和 C 的父節點，節點 B 和 C 在同一級，叫做兄弟節點。沒有父節點的 A 節點叫做根節點，沒有子節點的節點叫做葉子節點或葉節點，例如圖中的 D E F G。

樹的節點還涉及到三個概念，分別是高度、深度、層。

節點高度：節點到葉子節點的最長路徑

節點深度：根節點到這個節點所經歷的邊的個數

節點的層：節點深度 + 1

樹的高度：根節點的高度

結合下面的圖你就能夠理解了，高度是從下到上數的，深度是從上到下數的：

2. 二叉樹

樹的形態多種多樣，但是我們平常最常用的還是二叉樹，顧名思義，二叉樹就是每個節點最多只有兩個子節點的樹。

在上圖中的幾種二叉樹中，有兩個是比較特殊的，分別是滿二叉樹和完全二叉樹。

滿二叉樹：樹的葉子節點全在最底層，并且除了葉子節點，每個節點都有左右兩個子節點，例如上圖中的樹 2。

完全二叉樹：葉子節點都在最底下兩層，最底層的節點全都靠左排列，并且除了最后一層，其他層的節點都必須有左右兩個節點，例如上圖中的樹 3。

完全二叉樹的概念有點不太好理解，你可以多思考一下，其實滿二叉樹就是完全二叉樹的一種特殊情況。完全二叉樹的這種特性是為了方便其在數組中的存儲，不至于浪費太多的內存空間，等后面說到堆的時候你就更能理解了。
除了使用數組存儲二叉樹外，最常用的便是使用鏈表法來儲存二叉樹了。下面說到的二叉樹的遍歷便是這種存儲方法。

3. 二叉樹的遍歷

二叉樹的一種常見操作就是需要遍歷得到樹種的全部數據，最常用的遍歷方式有三種：前序遍歷、中序遍歷、后序遍歷。

前序遍歷：對于樹中的任意節點來說，先遍歷這個節點，然后遍歷這個節點的左子節點，最后遍歷這個節點的右子節點。（父左右）

中序遍歷：對于樹中的任意節點來說，先遍歷這個節點的左子節點，然后遍歷這個節點本身，最后遍歷這個節點的右子節點。（左父右）

后序遍歷：對于樹中的任意節點來說，先遍歷這個節點的左子節點，然后遍歷這個節點的右子節點，最后遍歷這個節點本身。（左右父）

其實樹的遍歷是一種很典型的遞歸操作，代碼也可以使用遞歸來實現，你可以看看我實現的代碼。

    //1.前序遍歷
    public void preOrder(Node head){
        if (head == null) return;
        System.out.print(head.getData() + "  ");
        preOrder(head.left);
        preOrder(head.right);
    }

    //2.中序遍歷
    public void midOrder(Node head){
        if (head == null) return;
        midOrder(head.left);
        System.out.print(head.getData() + "  ");
        midOrder(head.right);
    }

    //3.后序遍歷
    public void postOrder(Node head){
        if (head == null) return;
        postOrder(head.left);
        postOrder(head.right);
        System.out.print(head.getData() + "  ");
    }

云服務器 GPU云服務器二叉樹算法最優二叉樹算法圖二叉樹的存儲結構 c語言二叉樹輸入數據

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/73977.html

數據結構與算法:二叉樹算法

摘要：因此，根據題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數據結構與算法描述實現二叉樹算法淺談數據結構二叉樹慕課網實現二叉樹算法前端樹控件騰訊軟件開發面試題內容銜接上一章數據結構與算法:常見排序算法內容提要什么是樹　　- 為什么使用樹二叉樹二叉查找樹紅黑樹Ｂ、Ｂ＋樹堆伸展樹樹可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

Little_XM 2019-08-22 11:09 評論0 收藏0
Java數據結構與算法——二叉樹及操作(包括二叉樹遍歷)

摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...

muddyway 2019-08-16 11:15 評論0 收藏0
Javascript 數據結構與算法——二叉樹

摘要：一個節點可以有多個子節點二叉樹二叉樹是一種特殊的樹，子節點數不超過個。以某種特定的順序訪問樹中所有的節點稱為樹的遍歷樹的層數稱為樹的深度一個父節點的兩個子節點分別稱為左節點和右節點二叉查找樹又稱二叉排序樹是一種特殊的二叉樹。原文地址：http://www.brandhuang.com/article/1564967352592 1、樹一棵樹最上面的節點：根結點一個節點下面連接多個...

shengguo 2019-08-26 10:33 評論0 收藏0
數據結構與算法——二叉樹(下)

摘要：所以，如果中序遍歷二叉搜索樹，會得到一個有序的數據，時間復雜度是，所以二叉搜索樹又叫做二叉排序樹。所以，我們需要一種方式來維持二叉樹的平衡，最好是將其維持為滿二叉樹或者完全二叉樹，這就是后面會說到的平衡二叉查找樹，常見的有樹，紅黑樹。 1. 概述前面的文章說到了二叉樹，其實今天講的二叉搜索(查找)樹就是二叉樹最常用的一種形式，它支持高效的查找、插入、刪除操作，它的定義是這樣的：對于樹...

Awbeci 2019-08-16 16:17 評論0 收藏0