自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

【數(shù)據(jù)結(jié)構(gòu)之二叉樹】二叉樹的創(chuàng)建及遍歷實(shí)現(xiàn)

作者：行小觀
開發(fā) 前端
我們對(duì)其進(jìn)行了編號(hào)——從 0 到 n 的不中斷順序編號(hào)，而恰好，數(shù)組也有一個(gè)這樣的編號(hào) —— 數(shù)組下標(biāo)，只要我們把二者聯(lián)合起來(lái)，數(shù)組就能存儲(chǔ)二叉樹了。

[[394240]]

0. 前言

前文【二叉樹的概念和原理】主要介紹了樹的相關(guān)概念和原理，本文主要內(nèi)容為二叉樹的創(chuàng)建及遍歷的代碼實(shí)現(xiàn)，其中包括遞歸遍歷和棧遍歷。

1. 二叉樹的實(shí)現(xiàn)思路

1.0. 順序存儲(chǔ)——數(shù)組實(shí)現(xiàn)

前面介紹了滿二叉樹和完全二叉樹，我們對(duì)其進(jìn)行了編號(hào)——從 0 到 n 的不中斷順序編號(hào)，而恰好，數(shù)組也有一個(gè)這樣的編號(hào) —— 數(shù)組下標(biāo)，只要我們把二者聯(lián)合起來(lái)，數(shù)組就能存儲(chǔ)二叉樹了。

那么非滿、非完全二叉樹怎么使用數(shù)組存儲(chǔ)呢?

我們可以在二叉樹中補(bǔ)上一些虛構(gòu)的結(jié)點(diǎn)，構(gòu)造出來(lái)一個(gè)滿/完全二叉樹來(lái)，存儲(chǔ)到數(shù)組中時(shí)，虛構(gòu)的結(jié)點(diǎn)對(duì)應(yīng)的數(shù)組元素不存儲(chǔ)數(shù)據(jù)(# 代表虛構(gòu)的不存在)。如下圖：

 這樣存儲(chǔ)的缺點(diǎn)是，數(shù)組中可能會(huì)有大量空間未用到，造成浪費(fèi)。

1.1. 鏈?zhǔn)酱鎯?chǔ)——鏈表實(shí)現(xiàn)

我們畫樹的圖時(shí)，采用的都是結(jié)點(diǎn)加箭頭的方式，結(jié)點(diǎn)表示數(shù)據(jù)元素，箭頭表示結(jié)點(diǎn)之間的關(guān)系，清晰明了。如果你對(duì)鏈表熟悉，那么肯定能覺察到這是典型的鏈?zhǔn)浇Y(jié)構(gòu)。鏈?zhǔn)浇Y(jié)構(gòu)完美解決了順序結(jié)構(gòu)中可能會(huì)浪費(fèi)空間的缺點(diǎn)，而且也不會(huì)有數(shù)組空間限制。

下面來(lái)分析一下結(jié)點(diǎn)的結(jié)構(gòu)。

樹的結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)元素和若干指向其子樹分支。二叉樹的結(jié)點(diǎn)相對(duì)簡(jiǎn)單，包括：

  • 數(shù)據(jù)元素
  • 左子樹分支(結(jié)點(diǎn)的左孩子)
  • 右子樹分支(結(jié)點(diǎn)的右孩子)

怎么來(lái)實(shí)現(xiàn)呢?單鏈表的結(jié)點(diǎn)是使用一個(gè)指向其后繼結(jié)點(diǎn)的指針來(lái)表示其關(guān)系的。同樣地，我們也可以使用指針來(lái)表示結(jié)點(diǎn)和其左孩子、右孩子的關(guān)系。

分析到這，二叉樹的結(jié)點(diǎn)就清晰了：

  • 一個(gè)存儲(chǔ)數(shù)據(jù)的變量——data
  • 一個(gè)指向其左孩子結(jié)點(diǎn)的指針——left_child
  • 一個(gè)指向其右孩子結(jié)點(diǎn)的指針——right_child

用 C 語(yǔ)言的結(jié)構(gòu)體實(shí)現(xiàn)二叉樹的結(jié)點(diǎn)（為了方便起見，我們的數(shù)據(jù)全為字符類型）：

  1. /*二叉樹的結(jié)點(diǎn)的結(jié)構(gòu)體*/ 
  2. typedef struct Node { 
  3.     char data; //數(shù)據(jù)域 
  4.     struct Node *left_child; //左孩子指針 
  5.     struct Node *right_child; //右孩子指針 
  6. } TreeNode; 

2. 二叉樹的創(chuàng)造

二叉樹的定義是遞歸的定義，所以如果你想要?jiǎng)?chuàng)造一個(gè)二叉樹，也可以借助遞歸去創(chuàng)造。如何遞歸創(chuàng)造呢?在現(xiàn)實(shí)中，一棵樹先長(zhǎng)根、再長(zhǎng)枝干、最后長(zhǎng)葉子。我們用代碼創(chuàng)造樹時(shí)，也遵守這個(gè)原則，即先創(chuàng)造根結(jié)點(diǎn)，然后左子樹，最后右子樹。整個(gè)過程和先序遍歷相似。

我以前寫過的文章中有二叉樹創(chuàng)建過程的動(dòng)態(tài)圖[1]，這里不再贅述。

這里以創(chuàng)造下圖中的樹為例：

說明：當(dāng)我們看到如左圖的二叉樹時(shí)，要立即能腦補(bǔ)出對(duì)應(yīng)的右圖。#結(jié)點(diǎn)是什么?

前面我們已經(jīng)畫出了類似的圖，當(dāng)時(shí)是 NULL 結(jié)點(diǎn)，它的作用是標(biāo)識(shí)某個(gè)結(jié)點(diǎn)沒有孩子，它是我們虛構(gòu)出來(lái)的。在實(shí)際使用 C 語(yǔ)言創(chuàng)造二叉樹時(shí)，需要使用 #或者什么其他的符號(hào)來(lái)代替 NULL.

上圖的先序遍歷順序?yàn)椋篈BDEGCF，如果加上 # 結(jié)點(diǎn)，則為：ABD##EG###C#F##. 我們按照此順序來(lái)創(chuàng)造二叉樹。

代碼如下：

  1. /** 
  2.  * 創(chuàng)造一個(gè)二叉樹 
  3.  * root: 指向根結(jié)點(diǎn)的指針的指針 
  4.  */ 
  5. void create_binary_tree(TreeNode **root) 
  6. { 
  7.     char elem; 
  8.     scanf("%c", &elem); 
  9.     if (elem == '#') { 
  10.         *root = NULL; 
  11.     } else { 
  12.         *root = create_tree_node(elem); //創(chuàng)造一個(gè)二叉結(jié)點(diǎn) 
  13.         create_binary_tree(&((*root)->left_child)); 
  14.         create_binary_tree(&((*root)->right_child)); 
  15.     } 
  16. } 

請(qǐng)注意，函數(shù) create_binary_tree 接受的是一個(gè)指向根結(jié)點(diǎn)的指針的指針，至于為什么要使用指針的指針，理由在介紹單鏈表的初始化時(shí)已經(jīng)解釋了。

3. 二叉樹的遍歷

在文章【二叉樹的概念和原理】中已經(jīng)介紹了遍歷的原理了，下面使用 C 語(yǔ)言實(shí)現(xiàn)它。

3.0. 遍歷實(shí)質(zhì)

二叉樹的定義是遞歸的定義，即在二叉樹的定義中又用到了二叉樹的定義。所以無(wú)論是在創(chuàng)造二叉樹，還是在遍歷二叉樹，我們要做的只有三件事：訪問根結(jié)點(diǎn)、找左子樹、找右子樹。所謂先序、中序、后序遍歷，無(wú)非是這三件事的順序罷了。

3.1. 遞歸實(shí)現(xiàn)

我們?nèi)绻褂眠f歸代碼，很容易就能實(shí)現(xiàn)遍歷，而且代碼非常簡(jiǎn)潔。

【先序遍歷】

  1. /** 
  2.  * 先序遍歷 
  3.  * root: 指向根結(jié)點(diǎn)的指針 
  4.  */ 
  5. void preorder_traversal(TreeNode *root) 
  6. { 
  7.     if (root == NULL) { //若二叉樹為空，做空操作 
  8.         return; 
  9.     } 
  10.     printf("%c ", root->data); //訪問根結(jié)點(diǎn) 
  11.     preorder_traversal(root->left_child); //遞歸遍歷左子樹 
  12.     preorder_traversal(root->right_child); //遞歸遍歷右子樹 
  13. } 

【中序遍歷】

  1. /** 
  2.  * 中序遍歷 
  3.  * root: 指向根結(jié)點(diǎn)的指針 
  4.  */ 
  5. void inorder_traversal(TreeNode *root) 
  6. { 
  7.     if (root == NULL) { //若二叉樹為空，做空操作 
  8.         return; 
  9.     } 
  10.     inorder_traversal(root->left_child); //遞歸遍歷左子樹 
  11.     printf("%c ", root->data); //訪問根結(jié)點(diǎn) 
  12.     inorder_traversal(root->right_child); //遞歸遍歷右子樹 
  13. } 

【后序遍歷】

  1. /** 
  2.  * 后序遍歷 
  3.  * root: 指向根結(jié)點(diǎn)的指針 
  4.  */ 
  5. void postorder_traversal(TreeNode *root) 
  6. { 
  7.     if (root == NULL) { //若二叉樹為空，做空操作 
  8.         return; 
  9.     } 
  10.     postorder_traversal(root->left_child); //遞歸遍歷左子樹 
  11.     postorder_traversal(root->right_child); //遞歸遍歷右子樹 
  12.     printf("%c ", root->data); //訪問根結(jié)點(diǎn) 
  13. } 

事實(shí)上，大部分使用遞歸做的事，使用棧也可以做到。下面介紹遍歷的棧實(shí)現(xiàn)。

3.2. 棧實(shí)現(xiàn)

我們利用了棧的后進(jìn)先出的特性，

棧實(shí)現(xiàn)的代碼較復(fù)雜，受篇幅限制，這里只介紹先序遍歷和后序遍歷，詳細(xì)代碼請(qǐng)移步至代碼倉(cāng)庫(kù)查看。

【先序遍歷】

使用棧的先序遍歷

我們的樹的結(jié)點(diǎn)是要全部都入棧的(暫不管順序如何)，那么入棧的條件是什么?就是該結(jié)點(diǎn)可以被看作某棵樹(子樹)的根結(jié)點(diǎn)的時(shí)候。即，curr 指針指向的結(jié)點(diǎn)一定為某顆樹(子樹)的根結(jié)點(diǎn)。

在【二叉樹的概念和原理】中，我們已經(jīng)看到了，遍歷完某個(gè)子樹時(shí)，一定要回到其雙親結(jié)點(diǎn)。這種回溯如何實(shí)現(xiàn)?可以利用棧的先進(jìn)后出、后進(jìn)先出的特點(diǎn)，這個(gè)特點(diǎn)能在棧中完美保存結(jié)點(diǎn)在樹中父子關(guān)系，棧頂元素即為當(dāng)前子樹的雙親結(jié)點(diǎn)。

  1. /** 
  2.  * 使用棧實(shí)現(xiàn)的先序遍歷 
  3.  */ 
  4. void preorder_traversal_by_stack(TreeNode *root) 
  5. { 
  6.     //創(chuàng)造并初始化棧 
  7.     Stack stack; 
  8.     init_stack(&stack); 
  9.      
  10.     TreeNode *curr = root; //輔助指針curr 
  11.  
  12.     while (curr != NULL || !stack_is_empty(&stack)) { 
  13.         while (curr != NULL) { 
  14.             printf("%c", curr->data); //打印根結(jié)點(diǎn) 
  15.             push(&stack, curr); //根結(jié)點(diǎn)入棧 
  16.             curr = curr->left_child; //進(jìn)入左子樹 
  17.         } 
  18.         if (!stack_is_empty(&stack)) { 
  19.             pop(&stack, &curr); //出棧，回到上一個(gè)根結(jié)點(diǎn) 
  20.             curr = curr->right_child; //進(jìn)入右子樹 
  21.         } 
  22.     } 
  23. } 

【后序遍歷】

后序遍歷相較于前序和中序較為麻煩，不像前序和中序遍歷那樣。因?yàn)榍靶蚝椭行虻母Y(jié)點(diǎn)在右子樹之前，所以我們可以在出棧的時(shí)候同時(shí)進(jìn)行打印根結(jié)點(diǎn)和進(jìn)入右子樹。

后序遍歷的根結(jié)點(diǎn)在右子樹之后，這就要求我們?cè)俦闅v完左子樹后，先返回到根結(jié)點(diǎn)，然后進(jìn)入右子樹，遍歷完右子樹之后，再回到根結(jié)點(diǎn)，才能打印它。

關(guān)鍵之處還在于左子樹、右子樹、根結(jié)點(diǎn)的順序。

所以當(dāng) curr 指針遍歷完左子樹后，我們不能直接將根結(jié)點(diǎn)出棧，而是先從棧頂讀取到根結(jié)點(diǎn)，然后 curr 指針返回到根結(jié)點(diǎn)，然后 curr 指針進(jìn)入右子樹進(jìn)行遍歷，當(dāng)右子樹遍歷完成后，將根結(jié)點(diǎn)出棧，才能打印根結(jié)點(diǎn)。

這樣一來(lái)，后序遍歷就有兩次回到根結(jié)點(diǎn)的動(dòng)作，且這兩次的后續(xù)動(dòng)作不一樣。第一次通過讀取棧頂回到根結(jié)點(diǎn)，然后進(jìn)入右子樹;第二次通過出?；氐礁Y(jié)點(diǎn)，然后打印根結(jié)點(diǎn)。

這樣看似解決了后序遍歷的順序問題，但其實(shí)又得到了一個(gè)新的問題，即，我們?nèi)绾沃烙易訕浔槐闅v完了?

我們有兩次回到根結(jié)點(diǎn)的動(dòng)作，對(duì)于寫代碼的人來(lái)說，我們知道兩次回到根結(jié)點(diǎn)之后該干什么，知道右子樹是否被遍歷完了。但是對(duì)于 curr 指針來(lái)說，它不知道，兩次回到根結(jié)點(diǎn)，它都不知道右子樹是否被遍歷完成了。

此時(shí)，對(duì)于curr 指針來(lái)說，就像有兩條路擺在它面前讓它選擇其中一條，它難以抉擇。如果當(dāng)其中一條有過它的腳印，那么它就很容易選擇那條沒走過的路了。

所以我們現(xiàn)在還需要一個(gè)“腳印”指針——prev，prev指針用來(lái)記錄 curr訪問過的結(jié)點(diǎn)。

當(dāng) curr 指針第二次回到根結(jié)點(diǎn)的時(shí)候，一看，哦!我的腳印留在那呢!(prev指針指在右子樹那里)curr 指針就直接放心打印根結(jié)點(diǎn)了。

  1. /** 
  2.  * 使用棧實(shí)現(xiàn)的后序遍歷 
  3.  */ 
  4. void postorder_traversal_by_stack(TreeNode *root) 
  5. { 
  6.     Stack stack; 
  7.     init_stack(&stack); 
  8.  
  9.     TreeNode *curr = root; //輔助指針curr，記錄當(dāng)前訪問結(jié)點(diǎn) 
  10.     TreeNode *prev = NULL; //腳印指針prev，記錄上一個(gè)訪問過的結(jié)點(diǎn) 
  11.  
  12.     while (curr != NULL || !stack_is_empty(&stack)) { 
  13.         if (curr != NULL) { 
  14.             push(&stack, curr); //根結(jié)點(diǎn)入棧 
  15.             curr = curr->left_child; //進(jìn)入左子樹 
  16.         } else { 
  17.             get_top(&stack, &curr); //讀棧頂元素，不是出棧 
  18.             //右子樹不為空，且右子樹沒被遍歷 
  19.             if (curr->right_child != NULL && curr->right_child != prev) {  
  20.                 curr = curr->right_child; //進(jìn)入右子樹 
  21.                 push(&stack, curr); //根結(jié)點(diǎn)入棧 
  22.                 curr = curr->left_child; //進(jìn)入左子樹 
  23.             } else { //右子樹已被遍歷或者右子樹為空，可以打印根結(jié)點(diǎn)了 
  24.                 pop(&stack, &curr); //根結(jié)點(diǎn)出棧 
  25.                 printf("%c", curr->data); //打印根結(jié)點(diǎn) 
  26.                 prev = curr; //記錄 
  27.                 curr = NULL; //置空，進(jìn)入下一輪循環(huán) 
  28.             } 
  29.         } 
  30.     } 
  31. } 

以上代碼中用到的棧的相關(guān)函數(shù)這里不再給出，詳細(xì)代碼請(qǐng)移步至代碼倉(cāng)庫(kù)(文末獲取)。

4. 總結(jié)

遞歸的代碼雖然簡(jiǎn)潔，但是對(duì)新手來(lái)說卻有點(diǎn)難以理解，這是因?yàn)榻佑|的太少。棧的代碼相對(duì)來(lái)說容易理解一些，但代碼比較復(fù)雜，特別是后序遍歷的代碼。

不過當(dāng)你真正理解了二叉樹的定義、概念、原理之后，代碼相關(guān)的問題就不再是問題了，最終只落在六個(gè)字上——無(wú)他，惟手熟爾。

以上就是二叉樹的創(chuàng)建和遍歷的實(shí)現(xiàn)。

 參考資料

[1]二叉樹創(chuàng)建過程的動(dòng)態(tài)圖: https://blog.csdn.net/m0_47335900/article/details/106856321

[2]GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo

[3]Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo

 

責(zé)任編輯：姜華 來(lái)源： 二十二畫程序員
數(shù)據(jù)結(jié)構(gòu)二叉樹樹
相關(guān)推薦

2021-04-19 07:47:42

數(shù)據(jù)結(jié)構(gòu)二叉樹Tree

2021-04-28 20:12:27

數(shù)據(jù)結(jié)構(gòu)創(chuàng)建

2020-04-27 07:05:58

二叉樹左子樹右子樹

2021-03-17 08:19:22

二叉樹LeetCode樹

2022-10-26 23:58:02

二叉樹數(shù)組算法

2013-01-30 10:34:02

數(shù)據(jù)結(jié)構(gòu)

2023-05-08 15:57:16

二叉樹數(shù)據(jù)結(jié)構(gòu)

2020-09-23 18:25:40

算法二叉樹多叉樹

2021-01-07 08:12:47

數(shù)據(jù)結(jié)構(gòu)二叉樹樹

2020-11-02 09:15:47

算法與數(shù)據(jù)結(jié)構(gòu)

2021-09-15 07:56:32

二叉樹層次遍歷

2009-08-11 13:29:57

C#二叉樹遍歷

2018-03-15 08:31:57

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

2013-07-15 16:35:55

二叉樹迭代器

2021-09-29 10:19:00

算法平衡二叉樹

2024-01-23 12:54:00

C++編程語(yǔ)言代碼

2021-08-27 11:36:44

二叉樹回溯節(jié)點(diǎn)

2021-04-01 10:34:18

Java編程數(shù)據(jù)結(jié)構(gòu)算法

2021-05-06 17:46:30

二叉樹數(shù)據(jù)結(jié)構(gòu)

2021-03-19 10:25:12

Java數(shù)據(jù)結(jié)構(gòu)算法
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)