二叉樹
- 前言
- 一、二叉樹的結構介紹
- 二、二叉樹的遍歷（遞回）（易）
- 1.前序遍歷
- 2.中序遍歷
- 3.后序遍歷
- 三、二叉樹的遍歷（迭代）（偏難）
- 1.利用佇列進行迭代 (易)
- 2.非遞回實作前中后序（難）
- 2.1前序遍歷
- 2.2中序遍歷
- 2.3后序遍歷
- 總結
前言
首先我們這里所講述的二叉樹是最為常見的，本章主要帶大家了解這種二叉樹，并且學會它常見的遍歷方式（遞回，迭代），由于普通的二叉樹沒有插入洗掉的意義，到了AVL，紅黑樹這種平衡二叉搜索樹才有插入洗掉的意義，所以我們在本章節主要是帶大家先簡要理解這種結構，對于二叉樹有一個初步的認識，
一、二叉樹的結構介紹
// 對int typedef 是因為二叉樹的節點可以存放任意的值，這里是為了方便后續有需要方便調整
typedef int BTDataType;
// 二叉樹
typedef struct BinaryTreeNode
{
//二叉樹的每一個節點都有一個值
BTDataType val;
//二叉樹的每一個節點都有指向左孩子（右孩子）的指標
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
這就是一個常見的二叉樹
二、二叉樹的遍歷（遞回）（易）
1.前序遍歷
對于一棵樹，樹的本身性質讓他非常適合遞回，當我們想要遞回一顆樹的時候，我們可以訪問它的根，左子樹，右子樹，注意是左子樹不是左孩子，左子樹又可以分成根，左子樹，右子樹
前序遍歷也是標準的深度優先搜索模式：遍歷當前節點，再往深處走，走到底就回來嘗試新的方法????????
??????接下來我們嘗試創建這樣上圖所示的樹
// 創建節點并進行初始化
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->left = NULL;
newnode->right = NULL;
newnode->val = x;
return newnode;
}
//手動創建一棵樹
BTNode* CreateTree()
{
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
BTNode* nodeG = BuyNode('G');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeB->right = nodeE;
nodeC->left = nodeF;
nodeC->right = nodeG;
nodeD->left = NULL;
nodeD->right = NULL;
nodeE->left = NULL;
nodeE->right = NULL;
nodeF->left = NULL;
nodeF->right = NULL;
nodeG->left = NULL;
nodeG->right = NULL;
return nodeA;
}
??????我們可以先預測結果，如果將NULL也列印出來的話，上面得到的前序遍歷的結果應該是
A B D NULL NULL E NULL NULL C F NULL NULL G NULL NULL
void PreOrder(BTNode* root)
{
//我們這里用列印的方式表示遍歷這個節點的值
if (root == NULL)
{
//如果這棵樹本身是空，或者遞回到空的位置我們列印NULL
//再回傳上一層
printf("NULL ");
return;
}
//訪問當前節點
printf("%c ", root->val);
//訪問當前節點的左子樹
PreOrder(root->left);
//訪問當前節點的右子樹
PreOrder(root->right);
}
看不懂的同學可以按照上面來那張圖片想一想
2.中序遍歷
??????
對于中序遍歷我們先走左子樹，根，右子樹
例子：ABCDEFG（層序）
我們也可以預測中序遍歷的結果：
NULL D NULL B NULL E NULL A NULL F NULL C NULL G NULL
void Inorder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
//訪問左子樹
Inorder(root->left);
//根
printf("%c ", root->val);
//右子樹
Inorder(root->right);
}
3.后序遍歷
??????
后序遍歷：左右根
例子：ABCDEFG（層序）
我們也可以預測中序遍歷的結果：
NULL NULL D NULL NULL E B NULL NULL F NULL NULL G C A
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
//左子樹
PostOrder(root->left);
//右子樹
PostOrder(root->right);
//根
printf("%c ", root->val);
}
其實到這里大家應該都差不多會了，我們接下來講講迭代方式走二叉樹
三、二叉樹的遍歷（迭代）（偏難）
1.利用佇列進行迭代 (易)
????????????
建議不會佇列的同學看看這一篇：【資料結構】堆疊和佇列，看完這一篇就夠了（萬字配動圖配習題）
佇列的代碼：有需要的自取
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
struct BinaryTreeNode;
// 鏈式結構：表示佇列
typedef struct BinaryTreeNode* QDataType;
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;//佇列中結點的結構
// 佇列的結構
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
// 初始化佇列
void QueueInit(Queue* q);
// 隊尾入佇列
void QueuePush(Queue* q, QDataType data);
// 隊頭出佇列
void QueuePop(Queue* q);
// 獲取佇列頭部元素
QDataType QueueFront(Queue* q);
// 獲取佇列隊尾元素
QDataType QueueBack(Queue* q);
// 獲取佇列中有效元素個數
int QueueSize(Queue* q);
// 檢測佇列是否為空，如果為慷訓傳非零結果，如果非慷訓傳0
int QueueEmpty(Queue* q);
// 銷毀佇列
void QueueDestroy(Queue* q);
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
}
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* tmp = (QNode*)malloc(sizeof(QNode));
tmp->_next = NULL;
tmp->_data = data;
if (q->_rear == NULL)
{
q->_front = q->_rear = tmp;
}
else
{
q->_rear->_next = tmp;
q->_rear = tmp;
}
}
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
QNode* first = q->_front->_next;
if (first == NULL)
q->_rear = NULL;//處理這一步
free(q->_front);
q->_front = first;
}
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_front->_data;
}
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_rear->_data;
}
int QueueSize(Queue* q)
{
assert(q);
int n = 0;
QNode* cur = q->_front;
while (cur)
{
n++;
cur = cur->_next;
}
return n;
}
int QueueEmpty(Queue* q)
{
assert(q);
return q->_front == NULL;
}
void QueueDestroy(Queue* q)
{
assert(q);
while (!QueueEmpty(q))
{
QNode* tmp = q->_front->_next;
free(q->_front);
q->_front = tmp;
}
q->_front = q->_rear = NULL;
}
我們走層序遍歷需要怎么做呢？其實很簡單，我們先入頭結點入佇列，然后每次在出隊頭元素之前把他的左孩子和右孩子帶入節點，遍歷佇列直到佇列為空，????????
//層序遍歷
void LevelOrder(BTNode* root)
{
//我們借用之前寫過的佇列
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* first = QueueFront(&q);
//訪問元素
if (first)
printf("%c ", first->val);
else
printf("NULL ");
//入下一個元素
if (first)
{
QueuePush(&q, first->left);
QueuePush(&q, first->right);
}
QueuePop(&q);
}
}
2.非遞回實作前中后序（難）
????????????????????????????????
其實這三道題是非常類似的，我們先給大家講最簡單的前序遍歷！！
2.1前序遍歷
leetcode. 二叉樹的前序遍歷
前提提示：
一.這里的NULL我們不用訪問，訪問在這里相當于入一個陣列（vector），不懂的同學先把他當成陣列！
二. 以及這里所說的最左列為當前節點一直遞回它的左子樹，即上圖的1 , 2，4
分析：我們想要利用堆疊對我們的二叉樹進行前序遍歷，我們可以觀察前序遍歷的時候會先遍歷
1–>2–>4，我們一邊遍歷一邊將遍歷的值放入堆疊中看看，發現這棵樹的話只剩下4，2，1的右子樹就可以走完了！！！！
如何遍歷右子樹呢？ 實際上我們觀察**（3）這顆子樹我們可以發現什么，我們沒有辦法通過一次操作遍歷完右子樹，但是我們可以把3這顆子樹進行拆分，我們入它的最左列節點訪問再進行入堆疊**，就相當于遍歷了（3）的左子樹與每個節點的根（細品），這個時候我們遍歷（7）是不是就是一次操作就能解決了？其實還可以再分一次，分到像（5）的時候，當節點的右子樹為空樹的時候，我們就訪問他！！！
重要：
一棵樹一定能分到沒有右子樹的時候，這時訪問當前節點相當于訪問上一個根節點的右子樹
一棵樹一定能分到沒有右子樹的時候，這時訪問當前節點相當于訪問上一個根節點的右子樹
一棵樹一定能分到沒有右子樹的時候，這時訪問當前節點相當于訪問上一個根節點的右子樹
就像訪問5的時候是不是相當于訪問了2的右子樹？是的！
💖💖💖💖💖💖
上面沒看懂，沒關系，帶大家再走一下每一個步驟
💖💖💖💖💖💖
這里再拆分一下每一個步驟
剛開始
第一步：我們就訪問每一個節點并且入堆疊（將1,2，4入堆疊并且放入陣列），這時候我們要拿出堆疊頂的4，將它的右子樹的最左列入堆疊（NULL不入堆疊），我們重復此操作，到2的時候，我們將它的右子樹（5）及其最左列入堆疊并且訪問，并且把2出堆疊，這時候的堆疊只有（5,1）
重復上述操作，取堆疊頂資料，將堆疊頂資料的右子樹的最左列入堆疊之后將原堆疊頂資料出堆疊，這里5右子樹為NULL不用入堆疊，我們堆疊里就只剩下1，接著入1的右子樹的最左列，即3,6入堆疊
重復上述操作，取堆疊頂資料，將堆疊頂資料的右子樹的最左列入堆疊之后將原堆疊頂資料出堆疊，6無右子樹，就彈出了，到3的時候把3的右子樹最左列帶入（7），最后堆疊里面還有一個7
重復上述操作，取堆疊頂資料，將堆疊頂資料的右子樹的最左列入堆疊之后將原堆疊頂資料出堆疊，把7出掉，結束！！！！
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
//利用堆疊進行迭代遍歷
//思路：每次遍歷當前節點（cur）的左子樹，再進行入堆疊，最后從堆疊中依次取出以相同的方式遍歷右子樹
//可以先入最左的樹
TreeNode* cur =root;
vector<int> retArr;//用來回傳的答案
stack<TreeNode*> s;//利用堆疊進行迭代遍歷
while(cur)
{
retArr.push_back(cur->val);
s.push(cur);
cur = cur->left;
}
//現在只要遍歷堆疊當中的所有的右子樹就遍歷完所有樹
//當然遍歷每個右子樹也不是一次就能搞定的，我們分解成遍歷每個右子樹和他的左子樹，...在遍歷他的右子樹，就類似我們的遞回遍歷
while(!s.empty())
{
//我們可以對于堆疊當中的右子樹一個一個處理
cur = s.top();
s.pop();
cur = cur->right;
//將右子樹的最左列也都入堆疊
while(cur)
{
//每個右子樹又會帶出更多的右子樹....
retArr.push_back(cur->val);
s.push(cur);
cur =cur->left;
}
}
return retArr;
}
};
//分析子程序，這里是第一步，將root即右子樹的最左列入堆疊
while(cur)
{
//每個右子樹又會帶出更多的右子樹....
retArr.push_back(cur->val);
s.push(cur);
cur =cur->left;
}
總結，我們面對這種題都可以先入該節點及它的最左列節點，然后我們上面這一段代碼再去帶出右子樹當中的最左列，當我們帶出來的時候相當于所有的根與左子樹已經遍歷完了，我們只用對右子樹處理，右子樹又可以被繼續拆分！！！
while(!s.empty())
{
//我們可以對于堆疊當中的右子樹一個一個處理
cur = s.top();
s.pop();
//取出當前節點所有的右子樹，沒有就在后面的回圈中拿出這個值（相當于訪問上一個根的右子樹）
cur = cur->right;
//將右子樹的最左列也都入堆疊
while(cur)
{
//每個右子樹又會帶出更多的右子樹....
retArr.push_back(cur->val);
s.push(cur);
cur =cur->left;
}
}
2.2中序遍歷
leetcode.中序遍歷
中序遍歷的邏輯類似，就是我們訪問順序左子樹，根，右子樹，
還是用這個例子來：訪問堆疊頂的元素之后帶出該元素的右子樹的最左列，再洗掉原來的堆疊頂元素
我們一開始就可以訪問4（左子樹相當于訪問了NULL），我們走到4訪問再入右子樹的最左列（這里沒有），再將4出堆疊，然后我們2的左子樹訪問完了，我們就直接將2入到陣列，將2的右子樹帶進去（即帶2的最左一列），再將2出堆疊，如下圖
這時候對5進行重復操作（即訪問堆疊頂的元素之后帶出該元素的右子樹的最左列，再洗掉原來的堆疊頂元素），即像4的時候5的左子樹也是NULL（5的左子樹訪問了），我們訪問5，帶入右子樹（這里沒有），出堆疊，這時候堆疊里只剩下1，我們訪問1，再拿出它的右子樹的最左列（3,6）
然后我們再訪問6，同理上面（左子樹訪問過了），然后帶出它的右子樹（這里沒有），將6出堆疊，帶出6的右子樹，(這里沒有)，
這時候堆疊里面只剩下3，我們訪問3，把他的右子樹的最左列帶進去，并且把3出掉，這時候堆疊里面就剩下一個7
最后訪問7，然后入它的右子樹（NULL不訪問），把7出堆疊，
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
//類似前序遍歷的迭代，只不過中序遍歷是左根右
//所以我們我們入完最左列之后從里面取得時候在放入結果的vector就可以啦
TreeNode* cur =root;
stack<TreeNode*> s;
vector<int> retArr;
//先入最左列
while(cur)
{
s.push(cur);
cur=cur->left;
}
while(!s.empty())
{
//訪問當前節點并且訪問它的右子樹
cur = s.top();
s.pop();
retArr.push_back(cur->val);
cur=cur->right;
while(cur)
{
s.push(cur);
cur=cur->left;
}
}
return retArr;
}
};
2.3后序遍歷
leetcode.后序遍歷
后序遍歷會稍微難一些，我們在按照上面的邏輯去寫的時候會出現一點問題，我們用畫圖的方式來剖析，
我們一開始還是將根以及它的最左列入堆疊，根據后序遍歷的左右根，
觀察4是可以訪問的，訪問完并且可以出堆疊，那么1.它的條件就是當前節點的右子樹為空，
現在對于2來說，我們訪問它的右子樹，并且不能把2出掉，因為要訪問完右子樹才可以出，所以我們現在將2的右子樹的最左列入堆疊
這個時候堆疊頂元素5的右子樹為NULL，所以我們訪問5，到了現在堆疊頂元素就是2了，我們人為肯定知道它的右子樹已經遍歷了，但是程式要識別就必須要有條件，我們只有一個條件就是當前節點的右子樹為空才訪問堆疊頂元素，
結論：第二個條件應該是什么呢，我們訪問當前堆疊頂元素（2）的時候，我們可以設定一個前驅指標，指向我們上一個訪問的節點，那么我們2的上一個訪問的節點是誰呢？（5）！！！，我們就可以讓 cur->right == prev 即當前節點的右子樹是不是指向前驅指標，若是，則該cur（2）的右子樹5已經訪問完了，這樣就能辨別當前堆疊頂元素的右節點是否有訪問過，
那么這個是不是巧合呢，其實不是的，想一想，我們遍歷（5）這顆子樹的也是遵循后序遍歷的原則，最后遍歷的就是子樹的根（5），所以前驅指標是指向右子樹的根的，
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> retArr;
if(root ==NULL)
return vector<int>();
stack<TreeNode*> s;
TreeNode* cur =root;
TreeNode* prev =root;
while(cur)
{
s.push(cur);
cur =cur->left;
}
//接下來遍歷每棵樹的右子樹
while(!s.empty())
{
cur =s.top();
if(cur->right ==NULL || cur->right == prev)
{
retArr.push_back(cur->val);
prev =cur;
//表示當前節點的右子樹訪問完了，就更新prev然后pop掉
s.pop();
}
else
{
cur = cur->right;
while(cur)
{
s.push(cur);
cur =cur->left;
}
}
}
return retArr;
}
};
總結
💓💓💓
二叉樹的初階就在這里告一段落啦，大家覺得有幫助可以給博主一鍵三連，這對我真的很重要，謝謝啦，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298949.html
標籤：其他