C#實現二叉樹的各種遍歷

来源:http://www.cnblogs.com/VectorZhang/archive/2016/06/21/5603358.html
-Advertisement-
Play Games

1. 引言 在實際的項目中,樹還是用的比較多的一種,尤其是對於具有層次結構的數據。相信很多人都學過樹的遍歷,比如先序遍歷,後序遍歷等,利用遞歸還是很容易理解的。 今天給大家介紹下二叉樹的幾種遍歷演算法,包括遞歸和非遞歸的實現。 首先建立一棵二叉樹 如: 一棵簡單的二叉樹 2. 先序遍歷 先序遍歷還是很 ...


1. 引言

在實際的項目中,樹還是用的比較多的一種,尤其是對於具有層次結構的數據。相信很多人都學過樹的遍歷,比如先序遍歷,後序遍歷等,利用遞歸還是很容易理解的。

今天給大家介紹下二叉樹的幾種遍歷演算法,包括遞歸和非遞歸的實現。

首先建立一棵二叉樹 如:

        [DebuggerDisplay("Value={Value}")]
        public class Tree
        {
            public string Value;
            public Tree Left;
            public Tree Right;
        }

        public static Tree CreatFakeTree()
        {
            Tree tree = new Tree() {Value = "A"};
            tree.Left = new Tree()
            {
                Value = "B",
                Left = new Tree() {Value = "D", Left = new Tree() {Value = "G"}},
                Right = new Tree() {Value = "E", Right = new Tree() {Value = "H"}}
            };
            tree.Right = new Tree() {Value = "C", Right = new Tree() {Value = "F"}};

            return tree;
        }

一棵簡單的二叉樹

image

 

2. 先序遍歷

先序遍歷還是很好理解的,一次遍歷根節點,左子樹,右子數

遞歸實現

        public static void PreOrder(Tree tree)
        {
            if (tree == null)
                return;

            System.Console.WriteLine(tree.Value);
            PreOrder(tree.Left);
            PreOrder(tree.Right);
        }

非遞歸實現

        public static void PreOrderNoRecursion(Tree tree)
        {
            if(tree == null)
                return;

            System.Collections.Generic.Stack<Tree> stack = new System.Collections.Generic.Stack<Tree>();
            Tree node = tree;

            while (node != null || stack.Any())
            {
                if (node != null)
                {
                    stack.Push(node);
                    System.Console.WriteLine(node.Value);
                    node = node.Left;
                }
                else
                {
                    var item = stack.Pop();
                    node = item.Right;
                }
            }
        }

輸出結果: image

 

3. 中序遍歷

遞歸實現

        public static void InOrder(Tree tree)
        {
            if(tree == null)
                return;

            InOrder(tree.Left);
            System.Console.WriteLine(tree.Value);
            InOrder(tree.Right);
        }

非遞歸實現

        public static void InOrderNoRecursion(Tree tree)
        {
            if (tree == null)
                return;

            System.Collections.Generic.Stack<Tree> stack = new System.Collections.Generic.Stack<Tree>();
            Tree node = tree;

            while (node != null || stack.Any())
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.Left;
                }
                else
                {
                    var item = stack.Pop();
                    System.Console.WriteLine(item.Value);

                    node = item.Right;
                }
            }
        }

輸出結果:image

 

4. 後序遍歷

遞歸實現

        public static void PostOrder(Tree tree)
        {
            if (tree == null)
                return;

            PostOrder(tree.Left);
            PostOrder(tree.Right);
            System.Console.WriteLine(tree.Value);
        }

非遞歸實現 比前兩種稍微複雜一點。要保證左右節點都被訪問後,才能訪問根節點。這裡給出兩種形式。

        public static void PostOrderNoRecursion(Tree tree)
        {
            if (tree == null)
                return;

            System.Collections.Generic.Stack<Tree> stack = new System.Collections.Generic.Stack<Tree>();
            Tree node = tree;
            Tree pre = null;
            stack.Push(node);

            while (stack.Any())
            {
                node = stack.Peek();
                if ((node.Left == null && node.Right == null) ||
                    (pre != null && (pre == node.Left || pre == node.Right)))
                {
                    System.Console.WriteLine(node.Value);
                    pre = node;

                    stack.Pop();
                }
                else
                {
                    if(node.Right != null)
                        stack.Push(node.Right);

                    if(node.Left != null)
                        stack.Push(node.Left);
                }
            }
        }

        public static void PostOrderNoRecursion2(Tree tree)
        {
            HashSet<Tree> visited = new HashSet<Tree>();
            System.Collections.Generic.Stack<Tree> stack = new System.Collections.Generic.Stack<Tree>();
            Tree node = tree;

            while (node != null || stack.Any())
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.Left;
                }
                else
                {
                    var item = stack.Peek();
                    if (item.Right != null && !visited.Contains(item.Right))
                    {
                        node = item.Right;
                    }
                    else
                    {
                        System.Console.WriteLine(item.Value);
                        visited.Add(item);
                        stack.Pop();
                    }
                }
            }
        }

輸出結果: image

 

5. 層序遍歷

層序遍歷就是按照層次由左向右輸出

        public static void LevelOrder(Tree tree)
        {
            if(tree == null)
                return;

            Queue<Tree> queue = new Queue<Tree>();
            queue.Enqueue(tree);

            while (queue.Any())
            {
                var item = queue.Dequeue();
                System.Console.Write(item.Value);

                if (item.Left != null)
                {
                    queue.Enqueue(item.Left);
                }

                if (item.Right != null)
                {
                    queue.Enqueue(item.Right);
                }
            }
        }

輸出結果:image

 

6. Z-型層序遍歷

Z-層序遍歷就是奇數層按照由左向右輸出,偶數層按照由右向左輸出,這裡定義了幾個輔助函數,比如計算節點所在的層次。演算法思想是按照層次保存樹形節點,應該是有更加優化的演算法,希望大家指出。

        public static int GetDepth(Tree tree, Tree node)
        {
            if (tree == null)
                return 0;

            if (tree == node)
                return 1;

            if (tree.Left == node || tree.Right == node)
                return 2;

            int lDepth = GetDepth(tree.Left, node);
            lDepth = lDepth == 0 ? 0 : lDepth + 1;

            int rDepth = GetDepth(tree.Right, node);
            rDepth = rDepth == 0 ? 0 : rDepth + 1;

            return lDepth >= rDepth ? lDepth : rDepth;
        }

        public static void Z_LevelOrder(Tree tree, Dictionary<int, List<Tree>> dictionary)
        {
            if (tree == null)
                return;

            Queue<Tree> queue = new Queue<Tree>();
            queue.Enqueue(tree);

            while (queue.Any())
            {
                var item = queue.Dequeue();
                var depth = GetDepth(tree, item);

                List<Tree> list;
                if (!dictionary.TryGetValue(depth, out list))
                {
                    list = new List<Tree>();
                    dictionary.Add(depth, list);
                }
                list.Add(item);

                if (item.Left != null)
                {
                    queue.Enqueue(item.Left);
                }
                
                if (item.Right != null)
                {
                    queue.Enqueue(item.Right);
                }
            }
        }

        public static void Z_LevelOrder(Tree tree)
        {
            if (tree == null)
                return;

            Dictionary<int, List<Tree>> dictionary = new Dictionary<int, List<Tree>>();
            Z_LevelOrder(tree, dictionary);

            foreach (KeyValuePair<int, List<Tree>> pair in dictionary)
            {
                if (pair.Key%2 == 0)
                {
                    pair.Value.Reverse();
                }

                pair.Value.ForEach(t=> { System.Console.Write(t.Value); });
            }
        }

輸出結果:image


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

-Advertisement-
Play Games
更多相關文章
  • 1.上傳zookeeper-3.4.6.tar.gz安裝包 2.解壓tar -xzf zookeeper-3.4.6.tar.gz 3.配置(先在一臺節點上配置) 3.1添加一個zoo.cfg配置文件 $ZOOKEEPER/conf mv zoo_sample.cfg zoo.cfg 3.2修改配置 ...
  • <html> <head> <meta name="viewport" content="width=device-width" /> <title>創建二維碼</title> <script src="~/Content/uploadify/jquery-2.1.1.min.js"></scrip ...
  • Winform中Treeview控制項失去焦點,將選擇的節點設置為高亮顯示 (2012-07-16 13:47:07)轉載▼標簽: winform treeview drawnode Treeview控制項--Name:tVtypeList將tVtypeList的HideSelection屬性設置為Fa ...
  • 前言 繼之前發的帖子【ORM-Dapper+DapperExtensions】,對Dapper的擴展代碼也進行了改進,同時加入Dapper 對Lambda表達式的支持。 由於之前缺乏對Lambda的知識,還是使用了拿來主義。研究了些案例,總歸有些問題: 1、只能生成sql、不能將值進行參數化。 2、 ...
  • 天創恆達UB530高清視頻採集卡USB游戲PS4視頻翻錄電影網路直播錄播會議HDMI採集盒 http://item.jd.com/1567495458.html 天創恆達UB5A0 USB採集卡HDMI 分量 網路會議ps4游戲視頻高清採集盒1080p http://item.jd.com/1542 ...
  • 我們在前面章節中講了寄宿,在前面的實例中也用到了配置文件,這一篇主要講講如何在應用配置文件,提高WCF程式的靈活性。在編寫WCF服務應用程式時,編寫配置項也是其中一項主要工作,在前面的幾個示例中我也使用過配置文件,通過配置文件來簡化代碼。WCF通過公開終結點,向客戶端公開服務,包括服務的地址、服務用... ...
  • 原文: "Adding Validation" 作者: "Rick Anderson" 翻譯: "謝煬(Kiler)" 校對: "孟帥洋(書緣)" 、 "婁宇(Lyrics)" 、 "許登洋(Seay)" 在本章節中你將為 模型類添加驗證邏輯,以確保在用戶試圖創建或編輯影片數據時強制執行驗證規則。 ...
  • “廠長,上一次我們講過了工作流的整體規劃,今天我要動手做啦!我想先把工作流的自定義表單做出來。” “好的,以前我做這方面的東西,我給你設計了一份表結構,你先拿去看看。” “廠長,是不是沒發完,怎麼就一個表?” “我就知道你會這麼問,我現在給你解釋一下重點欄位的含義。” 數據表:將表單上的內容保存到哪 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 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 ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...