二叉樹從入門到AC（2）
- 前言
- 一、二叉樹的深度
- 二、層次遍歷
- 相關文章目錄
前言
不知道在上一篇二叉樹從入門到AC（1）構建和前中后序遍歷
有沒有人察覺一個問題，
在一開始的二叉樹構建中，只要輸入前序（葉子結點需加0 0）就可以確定一顆二叉樹，而后半段又說只有前序和后序遍歷無法確定一顆二叉樹，這不是矛盾嗎？
實際上，這里的代碼構建的是滿二叉樹：
而單純的前序和后序確實是無法構建唯一二叉樹的，因為我們可能會遇到一些特殊情況，
我們來看看下圖：
我們來寫一下他的前序遍歷:
A B DE C FG
我們會發現一個尷尬的情況，對比下圖，結構不一樣，前序排列居然，完全一樣，
所以單一的前序，本身不足以作為構建二叉樹的條件，至于為什么前序和后序無法確定唯一二叉樹，理由同上，可以多做幾組不同的實驗很好得出結論，
一、二叉樹的深度
首先，二叉樹的深度的定義，我們沿用leetcode的定義：
說白了就是一個梗：這波你在第幾層，找到在大氣層的選手輸出層數即可，
那么演算法應該很簡單就能構思了，我們既然能遍歷完這棵二叉樹，那么在遞回中使用一個MAX始終保存每個葉子結點的深度的最大值即可，
例題：
假設根恒為1號結點，
輸入：n，然后n行輸入n對兒子結點的編號，葉子結點輸入為0，
輸出：該二叉樹的深度，
例如
Input：
5
2 3
4 5
0 0
0 0
0 0
Output：
4
可以理解為 第i行的兩個數，分別為第i號結點的左右子結點
思路：
題意表明第i點的左右子結點編號分別為f[i][0] ,f[i][1]
結構體加DFS遍歷
運用結構體儲存遍歷的兩個方向
用DFS的演算法思路不停地一插到底，
題解：
#include<stdio.h>
int n, max;
struct node {
int left;
int right;
}BTtree[1000003];//開個足夠大的空間
int Max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void DFS(int id, int deep) {
max = Max(max, deep);//記憶化搜索保留最大值
if (id == 0) return ;//到達葉子結點時停止向下
DFS(BTtree[id].left, deep+1);//向左遍歷
DFS(BTtree[id].right, deep+1);//向右遍歷
}
int main() {
int i=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d %d",&BTtree[i].left,&BTtree[i].right); //輸入該結點的左結點和右結點
}
DFS(1, 1);//從1號結點出發，初始深度為1
printf("%d",max);
return 0;
}
到這里，可以發現，DFS仿佛成為了二叉樹的核心演算法，事實上，面對一個普通的線性表，我們通常可以用回圈處理掉，而二叉樹結構天生便與DFS搭檔，因為線性表通常不需要DFS，更復雜的圖和樹會讓DFS遞回運算時間指數級爆炸，只有二叉樹和DFS搭配使用才看起來一切剛剛好！
那么DFS一招鮮足夠了嗎？其實還有一種遍歷，較之前中后序的遞回演繹更直觀，DFS同時也不再好使：層次遍歷，
二、層次遍歷
二叉樹的層次遍歷即按層次，以從上至下從左至右的順序進行遍歷，
以此二叉樹為例
層次遍歷即：ABCDEFG
這也是最直觀好理解的遍歷方式，
思路：
與前三種遍歷運用的DFS堆疊式思路不同，這種一層層均勻向外拓展的遍歷方式可以讓我們想到一個東西：BFS，而BFS與DFS核心的區別便是，BFS則需要使用一個佇列來進行維護，
所以在層次遍歷中，我們將使用佇列為結構，
這邊先通俗地解釋二者的區別：DFS是堆疊式思路，到了非葉子結點不會先輸出而是往下接著搜索，等到輸出這個點時已經一層層return回來了，滿足first in last out，而BFS是利用佇列先進先出，比如上圖，按照層次遍歷，讀到的就地直接輸出了，
具體演算法：若該點非葉子結點，輸出，將其下一層子結點排入佇列，
我們可以模擬一下上圖的情況：
佇列：1.a入隊 并放入子結點b c
2.b入隊，放入子結點d e
3.c入隊，放入子結點f g
如此反復，按先后順序輸出這個佇列，即可得到層次遍歷結果，
樣例：
輸入輸出范例：
代碼：
#include<stdio.h>
#include<stdlib.h>
typedef struct BTNode
{
int data;
struct BTNode *Left;
struct BTNode *Right;
}Node;
//創建二叉樹，按前序輸入
Node* createBTree()
{
Node *p;
int ch;
//printf("輸入data");
scanf("%d",&ch);
if(ch == 0) //如果到了葉子節點，接下來的左、右子樹分別賦值為0
{
p = NULL;
}
else
{
p = (Node*)malloc(sizeof(Node));
p->data = ch;
p->Left = createBTree(); //遞回創建左子樹
p->Right = createBTree(); //遞回創建右子樹
}
return p;
}
int main()
{
int i=0, ans[101] ,count=0,k=0,n=1;
int Front = 0, Rear = 1;
Node *root = NULL;
Node *q[101],*v;
root = createBTree();
q[0] = root;
while(Front <Rear){
v= q[Front++];
ans[count++] = v->data;
if(v->Left != NULL) q[Rear++] = v->Left; //把左子結點放入佇列
if(v->Right != NULL) q[Rear++] = v->Right;//把右子結點放入佇列
}
for(i = 0; i < count; i++)//輸出層次遍歷
{
k++;
printf("%d ",ans[i]);
if(k==n)//只是美觀
{
printf("\n");
n*=2;
k=0;
}
}
return 0;
}
相關文章目錄
二叉樹從入門到AC（1）構建和前中后序遍歷
DFS與排列組合（C語言描述）#1
DFS與排列組合（C語言描述）#2
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266988.html
標籤：其他
上一篇：知識點清單
下一篇：資料結構基礎練習