二叉樹的入門
- 名詞解釋與性質
- 一、如何構建一顆二叉樹
- 二、二叉樹的前中后序遍歷
- 遍歷的序
- 進階與例題
名詞解釋與性質
首先援引百度百科：
這里補充一張圖了解馬上用到的例子：
一、如何構建一顆二叉樹
#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;
Node *root = NULL;
root = createBTree();
return 0;
}
這是一個按前序輸入用雙指標鏈表構建的二叉樹，我們可以發現，鏈表僅僅只是一種儲存的方式，對二叉樹遍歷的順序（也是輸入的順序）才是真正的重點，
以前序：1245367為例
輸入時為 1 2 4(葉子結點）0 0 5(葉子結點) 0 0 3 6(葉子結點）00 7(葉子結點） 00
二、二叉樹的前中后序遍歷
遍歷的序
遍歷即按一定順序遍歷二叉樹的每一個結點
順序有如下三種：
（1）前（先）序遍歷（根左右）
（2）中序遍歷（左根右）
（3）后序遍歷（左右根）
于是在面對一顆二叉樹時，我們可以根據如上法則遞回寫出前中后序遍歷，
舉個栗子：
前序：ABDECFG
既然是根左右遞回，先寫根A及其左子結點右子結點：
A B C；
然后開始遞回，當B為根時，在B后加上左右子結點D，E：
A B DE C；
當C為根時在C后加上左右子結點 F G：
A B DE C FG；
因為DFEG后再無子結點遞回結束如上為遍歷結果，
中序方法如上：先寫B A C；
按照左根右為B補充：
DBE A C；
為C補充得最終解：
DBEAFCG；
后序如上同理：
B C A ；
D E B C A；
D E B F G C A；
得解，
任意二叉樹都可通過如上遞回寫出前中后序，而這種遞回方法也將不斷運用在之后的演算法中，
進階與例題
如何用代碼求解出一個二叉樹的序呢，
我們可以通過前序和中序來確認一棵二叉樹，并順之求出后序；
也可以通過中序和后序來確認，求其前序
但僅僅是前序和后序是無法構建一棵二叉樹的；
用個例題來說明：
Input：
兩行分別輸入前序和中序
Output：
輸出后序
思路：我們并不需要急于去構建一棵二叉樹，在擁有前序和中序的情況下，樹本身已經按照上述的規則建立好了，雖然是僅僅存在于陣列中，換言之，二叉樹作為一種資料結構，其真正的內涵在于其順序，而不是沒有靈魂的使用指標鏈表來儲存，
那么前序是根左右，中序是左根右，我們先通過前序的找到根（前序的第一個），此根在中序中的左邊為左子樹右邊為右子樹，然后進行上述的遞回，并輸出該結點，
通俗地解釋一下理解誤區：進行遞回再輸出，那么第一個輸出的是DFS最深的結果，最后輸出的才是當前結果，
以前序 A B C為例，中序為 B A C，為求后序，先找到根A，在中序中A的左邊B右邊C，遞回到B，無子樹輸出，遞回到C無子樹輸出，遞回完成輸出A，
代碼：
#include<stdio.h>
#include<string.h>
char a[28],b[28];
void dfs(int w,int x,int y,int z)//深搜
{int i=0,j=0;
if(w>x||y>z)//無法繼續遞回時
return;
for(i=w;i<=x;i++)
if(a[i]==b[y])//在中序中找到根
{dfs(w,i-1,y+1,y+i-w);//遞回左子樹
dfs(i+1,x,y+i-w+1,z);//遞回右子樹
printf("%c",a[i]);//遞回完后輸出，注意，是遞回完
}
}
int main()
{
int i=0,j=0,k=0;
scanf("%s",b);//輸入前序
scanf("%s",a);//輸入中序
j=strlen(a);
k=strlen(b);
dfs(0,j-1,0,k-1);//進入遞回
return 0;
}
關于dfs與二叉樹，在DFS與排列組合
中有提及，但在那時的二叉樹更像一種邏輯判斷結構而不是存盤結構，
有時間再更新，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260527.html
標籤：其他
上一篇：Filter和Listener-學習筆記01【Filter 快速入門】
下一篇：Day6:可靠資料傳輸的原理