創作內容

18 GP

C# Binary Search Tree traversal

作者：貓貓風 ฅ●ω●ฅ│2017-12-21 22:25:46│巴幣：36│人氣：2930
.




















二元搜尋樹(Binary Search Tree）指一棵空樹或者具有下列性質的二元樹：

1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值
2.若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值
3.任意節點的左、右子樹也分別為二元搜尋樹
4.沒有鍵值相等的節點

二元搜尋樹的功能不外乎基本的新增、搜尋、刪除

不過此篇主要介紹的為 二元搜尋樹的尋訪( Binary Search Tree traversal)

尋訪方式主要分為三種，前序(preorder)  中序(inprder)  後序(postorder)

前序(Pre-order)

訪問根節點
訪問左子樹
訪問右子樹

中序(In-order)

訪問左子樹
訪問根節點
訪問右子樹

後序(Post-order)

訪問左子樹
訪問右子樹
訪問根節點

可用下圖來概括說明




而此篇用到的搜尋為 Depth-first search(DFS)  深度優先搜索

是一種用來遍尋一個樹(tree)或圖(graph)的演算法

由樹的根(或圖的某一點當成 根)來開始探尋

先探尋邊(edge)上未搜尋的一節點(vertex or node)，並儘可能深的搜索

直到該節點的所有邊上節點都已探尋

就回溯(backtracking)到前一個節點，重覆探尋未搜尋的節點

直到找到目的節點或遍尋全部節點



最後為實作程式碼

使用下圖的樹來進行尋訪



Main:


  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.ComponentModel;  
  4. using System.Data;  
  5. using System.Drawing;  
  6. using System.Linq;  
  7. using System.Text;  
  8. using System.Windows.Forms;  
  9.   
  10. namespace TreeSearch  
  11. {  
  12.     public partial class Form1 : Form  
  13.     {  
  14.         public Form1()  
  15.         {  
  16.             InitializeComponent();  
  17.         }  
  18.   
  19.         private void Form1_Load(object sender, EventArgs e)  
  20.         {  
  21.             Tree BST = new Tree();  
  22.             BST.Insert(50);  
  23.             BST.Insert(17);  
  24.             BST.Insert(23);  
  25.             BST.Insert(12);  
  26.             BST.Insert(19);  
  27.             BST.Insert(54);  
  28.             BST.Insert(9);  
  29.             BST.Insert(14);  
  30.             BST.Insert(67);  
  31.             BST.Insert(76);  
  32.             BST.Insert(72);  
  33.             //Console.WriteLine("Inorder Traversal : ");  
  34.             textBox1.Text = BST.Inorder(BST.ReturnRoot());  
  35.             //Console.WriteLine("Preorder Traversal : ");  
  36.             textBox2.Text = BST.Preorder(BST.ReturnRoot());  
  37.             //Console.WriteLine("Postorder Traversal : ");  
  38.             textBox3.Text = BST.Postorder(BST.ReturnRoot());  
  39.         }  
  40.     }  
  41. }  

Class Node


  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5.   
  6. namespace TreeSearch  
  7. {  
  8.     class Node  
  9.     {  
  10.         public int item;  
  11.         public Node left;  
  12.         public Node right;  
  13.     }  
  14. }  

Class Tree


  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5.   
  6. namespace TreeSearch  
  7. {  
  8.     class Tree  
  9.     {  
  10.         private String preorder_path = "", inorder_path = "", postorder_path = "";  
  11.         public Node root;  
  12.         public Tree()  
  13.         {  
  14.             root = null;  
  15.         }  
  16.         public Node ReturnRoot()  
  17.         {  
  18.             return root;  
  19.         }  
  20.         public void Insert(int id)  
  21.         {  
  22.             Node newNode = new Node();  
  23.             newNode.item = id;  
  24.             if (root == null)  //如果跟是空，則新加入的點為根  
  25.                 root = newNode;  
  26.             else  
  27.             {  
  28.                 Node current = root; //如果根不為空，則當前的點設成根  
  29.                 Node parent; //宣告父節點  
  30.                 while (true)  
  31.                 {  
  32.                     parent = current; //設定父節點為根  
  33.                     if (id < current.item) //如果當前值小於父節點  
  34.                     {  
  35.                         current = current.left; //把當前節點歸為左子樹  
  36.                         if (current == null) //如果左子樹為空  
  37.                         {  
  38.                             parent.left = newNode; //新增一個節點  
  39.                             return;  
  40.                         }  
  41.                     }  
  42.                     else  
  43.                     {  
  44.                         current = current.right; //如果當前值大於父節點，將其歸右子樹  
  45.                         if (current == null) //如果右子樹為空  
  46.                         {  
  47.                             parent.right = newNode; // 新增一個節點  
  48.                             return;  
  49.                         }  
  50.                     }  
  51.                 }  
  52.             }  
  53.         }  
  54.         public String Preorder(Node Root)  
  55.         {  
  56.               
  57.             if (Root != null)  
  58.             {  
  59.                 preorder_path += Root.item + " ";  
  60.                 Preorder(Root.left);  
  61.                 Preorder(Root.right);  
  62.                   
  63.             }  
  64.             return preorder_path;  
  65.         }  
  66.         public String Inorder(Node Root)  
  67.         {  
  68.             if (Root != null)  
  69.             {  
  70.                 Inorder(Root.left);  
  71.                 inorder_path += Root.item + " ";  
  72.                 Inorder(Root.right);  
  73.             }  
  74.             return inorder_path;  
  75.         }  
  76.         public String Postorder(Node Root)  
  77.         {  
  78.             if (Root != null)  
  79.             {  
  80.                 Postorder(Root.left);  
  81.                 Postorder(Root.right);  
  82.                 postorder_path += Root.item + " ";  
  83.             }  
  84.             return postorder_path;  
  85.         }  
  86.     }  
  87. }  

執行結果


喜歡18 收藏 1 引用 留言 推上首頁 檢舉
引用網址：https://home.gamer.com.tw/TrackBack.php?sn=3827862
All rights reserved. 版權所有，保留一切權利

相關創作

同標籤作品搜尋：C#

C# MongoDB Atlas 雲端資料庫建置與教學
碧藍航線 自動戰鬥腳本 v2.2.6杰諾瓦的焰火
Tiefsee 4.2.1 ( 支援AVIF動圖、編譯成Native提升啟動速度
[C#] Windows 系統螢幕鎖定小程式
Tiefsee 4.1.6 (可查看 ComfyUI 圖片使用了哪些 LoRA

留言共 9 篇留言

芯玥兒：
又眼花了XD

12-21 22:40

貓貓風 ฅ●ω●ฅ：
這次是樹 葉子很多XDDD12-21 23:31
莫莉安：
完全不懂… 會程式的感覺很厲害( ･ิω･ิ)

12-21 22:53

貓貓風 ฅ●ω●ฅ：
很燒腦( ･ิω･ิ)12-21 23:32
彩゛天空゜：
你這樣用腦廠商不保固ㄛ

12-22 05:00

貓貓風 ฅ●ω●ฅ：
[e26]12-22 23:01
小魚：
感謝分享,
有空研究看看,
我之前還說要找時間研究2元樹,
我覺得最難的地方是不平衡改成平衡的部份...

12-22 11:56

貓貓風 ฅ●ω●ฅ：
是的12-22 23:01
小刀：
厲害～[e19]

12-22 14:52

貓貓風 ฅ●ω●ฅ：
[e35]12-22 23:01
無名氏：
試著修改了Tree類別，程式碼→https://gist.github.com/anonymous/f84ab86a2be2596a13fb6409a25023d9

12-22 20:08

貓貓風 ฅ●ω●ฅ：
[e19]12-22 23:00
貓貓風 ฅ●ω●ฅ：
不錯呀12-23 13:06
Fuwawa：
終於稍微看懂一點ㄌ... 嗚嗚 剛豪有學到 製作程式的東西

12-22 22:43

貓貓風 ฅ●ω●ฅ：
好唷>W<12-22 23:00
珀伽索斯(Ama)：
這個我還記得，當時真的把我搞得要死，
不過脫離學生時期之後，我就忘了差不多了[e19]

12-22 22:49

貓貓風 ฅ●ω●ฅ：
這確實不好裡解XD12-22 23:00
納蘭映雪：
https://truth.bahamut.com.tw/s01/201212/f968669ffe3fc1ab322d60bcd9ea9858.GIF

12-28 00:11

貓貓風 ฅ●ω●ฅ：
[e35]12-31 01:28
我要留言提醒：您尚未登入，請先登入再留言

18喜歡★s1234567 可決定是否刪除您的留言，請勿發表違反站規文字。

前一篇：Arduino Watc... 後一篇：歡樂的包容者 火狂 攻...

追蹤私訊切換新版閱覽

作品資料夾

繪圖區 (0)
└動物朋友 (3)
└魔界戰記 (15)
└勇造繪 (8)
└鋼彈系列 (23)
└百萬亞瑟王 (20)
└東方系列 (17)
└花樣練習 (3)
└自創人物 (15)
└火影忍者 (2)
└魔塔大陸 (3)
└女王之刃 (5)
└織田信奈的野望 (11)
└ＣＬＡＮＮＡＤ (4)
└里番 (13)
└魔法少女 - 小圓 (5)
└Night狼Mare (4)
└水星領航員 (0)
└約會大作戰 (3)
└時空幻境 (5)
└其他 (44)

文章區 (0)
└自然描寫 (71)
└心情日記 (117)
└閒情逸致 (19)
└情感抒發 (43)
└幻 (64)

點點文 (16)

類小說 (9)

神魔之塔 (12)
└地獄級關卡 (86)
└單雙週關卡 (81)
└無限迴廊 (11)
└特殊關卡 (25)
└主線任務 (6)
└黃道十二宮ＥＸ (11)

勇造文 (41)

黑歷史 (11)

程式設計 (0)
└android (8)
└Web (2)
└arduino (32)
└C# (88)
└algorithm (2)
└python (4)

電腦系統相關 (33)

電路設計 (4)

貓咪大戰爭 (140)

闇影詩章 (15)

遊戲相關 (66)

動漫相關 (6)

公主連結 (51)

各種家電 / 電器 周邊 (19)

原神 (93)

崩壞：星穹鐵道 (35)

PVC模型收集 (4)

碧藍航線 (24)

未分類 (110)

sakata21 給 大家：
來看看胖孑孓吧~~看更多我要大聲說1小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準，可能無法使用新的應用程式來呈現網站內容，在瀏覽器支援度及網站安全性的雙重考量下，為了讓巴友們有更好的使用體驗，巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特：
。Google Chrome（推薦）
。Mozilla Firefox
。Microsoft Edge（Windows10以上的作業系統版本才可使用）

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營，請將 gamer.com.tw 加入廣告阻擋工具的白名單中，謝謝 !【教學】