組合模式實現二叉樹先序遍歷，中序遍歷和後序遍歷

来源:https://www.cnblogs.com/vaiyanzi/archive/2018/08/21/9509248.html
-Advertisement-
Play Games

二叉樹的基本概念 在電腦中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。 二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根節點之後，每個頂點定義了唯一的父節 ...


二叉樹的基本概念

在電腦中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。

二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根節點之後，每個頂點定義了唯一的父節點，和最多2個子節點。然而，沒有足夠的信息來區分左節點和右節點。

image

從邏輯上講二叉樹有五種形態，如上圖：

  1. 空二叉樹——如圖(a)；
  2. 只有一個根節點的二叉樹——如圖(b)；
  3. 只有左子樹——如圖(c)；
  4. 只有右子樹——如圖(d)；
  5. 完全二叉樹——如圖(e)。

 

二叉樹相關的術語

image

  1. 樹的節點（node）：包含一個數據元素及若幹指向子樹的分支；
  2. 孩子節點（child node）：節點的子樹的根稱為該節點的孩子；
  3. 雙親節點：B 節點是A 節點的孩子，則A結點是B 節點的雙親；
  4. 兄弟節點：同一雙親的孩子節點；
  5. 堂兄結點：同一層上節點；
  6. 祖先節點: 從根到該節點的所經分支上的所有節點
  7. 子孫節點：以某節點為根的子樹中任一節點都稱為該節點的子孫
  8. 節點層：根節點的層定義為1；根的孩子為第2層節點，依此類推；
  9. 樹的深度：樹中最大的節點層
  10. 節點的度：節點子樹的個數
  11. 樹的度： 樹中最大的節點度。
  12. 葉子結點：也叫終端節點，是度為 0 的節點；
  13. 分枝結點：度不為0的節點；
  14. 有序樹：子樹有序的樹，如：家族樹；
  15. 無序樹：不考慮子樹的順序；

二叉樹的特性

  1. 在非空二叉樹中，第i層的節點總數不超過 , i>=1；
  2. 深度為h的二叉樹最多有 個結點(h>=1)，最少有h個節點；
  3. 對於任意一棵二叉樹，如果其葉節點數為N0，而度數為2的節點總數為N2，則N0=N2+1；
  4. 具有n個節點的完全二叉樹的深度為
  5. 有N個節點的完全二叉樹各節點如果用順序方式存儲，則節點之間有如下關係：若I為節點編號則 如果I>1，則其父節點的編號為I/2；如果2*I<=N，則其左兒子（即左子樹的根節點）的編號為2*I；若2*I>N，則無左兒子；如果2*I+1<=N，則其右兒子的節點編號為2*I+1；若2*I+1>N，則無右兒子。
  6. 給定N個節點，能構成h(N)種不同的二叉樹。h(N)為卡特蘭數的第N項。h(n)=C(2*n，n)/(n+1)。
  7. 設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i

二叉樹的遍歷

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有節點，使每一個節點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

設L、D、R分別表示遍歷左子樹、訪問根節點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先序遍歷），LDR（稱為中序遍歷），LRD （稱為後序遍歷）

image

先序遍歷(DLR):

首先訪問根，再先序遍歷左子樹，最後先序遍歷右子樹。如上圖遍歷的結果是：ABCDE

中序遍歷(LDR):

首先中序遍歷左子樹，再訪問根，最後中序遍歷右子樹，如上圖遍歷的結果是：CBDAE

後序遍歷(LRD):

首先後序遍歷左子樹，再後序遍歷右子樹，最後訪問根。如上圖遍歷的結果是：CDBEA

傳統遞歸對二叉樹的遍歷

public class Node
{
    public Node(int i)
    {
        Data = i;
    }
    public int Data { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
    public void Display(string lr)
    {
        Console.Write(lr + ": " + Data);
    }

先序遍歷

public void DLRDisplay(Node theNode)
{
    if (theNode != null)
    {
        theNode.Display("InOrder");
        InOrder(theNode.Left);              
        InOrder(theNode.Right);
    }
}

中序遍歷

public void LDRDisplay(Node theNode)
{
    if (theNode != null)
    {
        InOrder(theNode.Left);         
        theNode.Display("InOrder");            
        InOrder(theNode.Right);
    }
}

後序遍歷

public void LRDDisplay(Node theNode)
{
    if (theNode != null)
    {
       
        InOrder(theNode.Left);  
        InOrder(theNode.Right);       
        theNode.Display("InOrder");  
    }
}

組合模式實現二叉樹的三種遍歷

image

代碼實現

public enum Order
    {
       DLR,//先序遍歷
        LDR,//中序遍歷
        LRD //後序遍歷
    }
    public abstract class AbstractTreeNode
    {
        protected string name;
        public AbstractTreeNode(string name) {
            this.name = name;
        }
        public AbstractTreeNode Left { get; set; }
        public AbstractTreeNode Right { get; set; }
        public abstract void Display(Order order);
    }

    public class TreeNode : AbstractTreeNode
    {
        public TreeNode(string name) : base(name) { }
        public override void Display(Order order)
        {
            switch (order)
            {
                case Order.DLR:// D->L->R
                    DLRDisplay(order);
                    break;
                case Order.LDR://L->D->R
                    LDRDisplay(order);
                    break;
                case Order.LRD://L->R->D
                    LRDDisplay(order);
                    break;
            }
        }

        private void DLRDisplay(Order order)
        {
            Console.Write(name);
            if (Left != null)
            {
                Left.Display(order);
            }
            if (Right != null)
            {
                Right.Display(order);
            }
        }
        private void LDRDisplay(Order order)
        {
            if (Left != null)
            {
                Left.Display(order);
            }
            Console.Write(name);
            if (Right != null)
            {
                Right.Display(order);
            }           
        }
        private void LRDDisplay(Order order)
        {           
            if (Left != null)
            {
                Left.Display(order);
            }
 	    if (Right != null)
            {
                Right.Display(order);
            }
            Console.Write(name);           
        }
    }
    public class LeafNode : AbstractTreeNode
    {
        public LeafNode(string name)
            : base(name) { }
       
        public override void Display(Order order)
        {
            Console.Write(name);
        }
    }

測試：

/// <summary>
///        A
///      /   \
///     B     E
///   /  \
/// C     D
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
    AbstractTreeNode rootA, b, c, d, e;
    rootA = new TreeNode("A");
    b = new TreeNode("B");
    c = new LeafNode("C");
    d = new LeafNode("D");
    e = new LeafNode("E");

    rootA.Left = b;
    rootA.Right = e;
    b.Left = c; 
    b.Right = d;

    rootA.Display(Order.DLR);//output->ABCDE
    Console.WriteLine();
    rootA.Display(Order.LDR);//output->CBDAE
    Console.WriteLine();
    rootA.Display(Order.LRD);//output->CDBEA

    Console.ReadKey();
}

結果：

先序遍歷的結果：ABCDE

中序遍歷的結果：CBDAE

後序遍歷的結果：CDBEA

在這裡其實可以省略掉葉子節點類，只需要一個實現類TreeNode就可以了這樣就變得更簡單了：

image

代碼中可以刪掉LeafNode類，客戶端只針對TreeNode實現就可以了。因為這裡沒有針對複雜的樹枝節點的管理操作。因此不需要分別對待樹枝節點和葉子節點。

public enum Order
{
    DLR,//先序遍歷
    LDR,//中序遍歷
    LRD //後序遍歷
}
public abstract class AbstractTreeNode
{
    protected string name;
    public AbstractTreeNode(string name) {
        this.name = name;
    }
    public AbstractTreeNode Left { get; set; }
    public AbstractTreeNode Right { get; set; }
    public abstract void Display(Order order);
}

public class TreeNode : AbstractTreeNode
{
    public TreeNode(string name) : base(name) { }
    public override void Display(Order order)
    {
        switch (order)
        {
            case Order.DLR:// D->L->R
                DLRDisplay(order);
                break;
            case Order.LDR://L->D->R
                LDRDisplay(order);
                break;
            case Order.LRD://L->R->D
                LRDDisplay(order);
                break;
        }
    }

    private void DLRDisplay(Order order)
    {
        Console.Write(name);
        if (Left != null)
        {
            Left.Display(order);
        }
        if (Right != null)
        {
            Right.Display(order);
        }
    }
    private void LDRDisplay(Order order)
    {
         
            
        if (Left != null)
        {
            Left.Display(order);
        }
        Console.Write(name);
        if (Right != null)
        {
            Right.Display(order);
        }           
    }
    private void LRDDisplay(Order order)
    {
        if (Left != null)
        {
            Left.Display(order);
        }
        if (Right != null)
        {
            Right.Display(order);
        }
        Console.Write(name);           
    }
}

測試：

/// <summary>
///        A
///      /   \
///     B     E
///   /  \
/// C     D
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
    AbstractTreeNode rootA, b, c, d, e;
    rootA = new TreeNode("A");
    b = new TreeNode("B");
    c = new TreeNode("C");
    d = new TreeNode("D");
    e = new TreeNode("E");

    rootA.Left = b;
    rootA.Right = e;
    b.Left = c; 
    b.Right = d;

    rootA.Display(Order.DLR);//output->ABCDE
    Console.WriteLine();
    rootA.Display(Order.LDR);//output->CBDAE
    Console.WriteLine();
    rootA.Display(Order.LRD);//output->CDBEA

    Console.ReadKey();
}

結果：

先序遍歷的結果：ABCDE

中序遍歷的結果：CBDAE

後序遍歷的結果：CDBEA

兩次測試的結果是一樣的。

image


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Redux與它的中間件：redux-thunk，redux-actions，redux-promise，redux-sage
    序言 這裡要講的就是一個Redux在React中的應用問題，講一講Redux，react redux，redux thunk，redux actions，redux promise，redux sage這些包的作用和他們解決的問題。 因為不想把篇幅拉得太長，所以沒有太多源碼分析和語法講解，能怎麼簡單 ...
  • react-native使用redux 存在的坑
    前幾天安卓真機測試的時候，突然發現一個嚴重的問題。 後退兩次退出應用，再開啟白屏。而殺掉進程後再開啟就是好的。 這個重大bug我跟了好久，以為是splash-screen的問題。 後來一點一點打console，才找出問題————redux在後退兩次退出時，未重置，而保留了退出前的狀態值。 我不知道為 ...
  • 解決IE下select option不支持display none樣式
    萬惡的IE，option竟然不支持display樣式，想到的解決思路有二個： 1、ajax聯動查詢 2、jQuery的remove()、after()方法 方法1的不好之處是初始頁面，需要顯示全部IP，本來已經從後臺查詢了一次，如果再利用ajax，會給伺服器造成壓力，所以採用方法2。 後臺code ...
  • 排序演算法-（7）堆排序
    堆排序 堆排序是利用堆這種數據結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞，最好，平均時間複雜度均為O(nlogn)，它也是不穩定排序。首先簡單瞭解下堆結構。 堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點 ...
  • canvas實現驗證碼
    在通常的登錄界面我們都可以看到驗證碼，驗證碼的作用是檢測是不是人在操作，防止機器等非人操作，防止資料庫被輕而易舉的攻破。 驗證碼一般用PHP和java等後端語言編寫。 但是在前端，用canva或者SVG也可以繪製驗證碼。 繪製驗證碼不能是簡單的隨機字元串，而應該在繪製界面有一些干擾項： 如：干擾線段 ...
  • react-native開發總結
    項目地址：http://liu12fei08fei.github.io/blog/41react native.html 說明 • 項目總結代碼地址 • 從項目開始啟動（2018 07 02）到項目進入測試（2018 08 20） • 從我基本沒用過react，到直接上手react native • ...
  • js-完整輪播圖
    js-完整輪播圖 今天寫一個完整的輪播圖，首先它需要實現三個功能：1.滑鼠放在小圓點上實現輪播。2.點擊焦點按鈕實現輪播。3.無縫自動輪播。 輪播圖的原理： 一系列的大小相等的圖片平鋪，利用CSS佈局只顯示一張圖片，其餘隱藏。通過計算偏移量（封裝一個動畫函數）自動播放，或通過手動點擊事件切換圖片。 ...
  • Web應用架構入門之11個基本要素
    讀完這篇博客，你就可以回答一個經典的面試題：當你訪問Google時，到底發生了什麼？ ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類