系列文章目錄
第八話 資料結構之二叉樹
文章目錄
- 1、前言
- 2、非遞歸周遊路線
- 3、建立二叉樹
- 先序周遊非遞歸實作
- 中序周遊非遞歸實作
- 後續周遊非遞歸實作
- 4、總結
前言
對于同一個二叉樹來說，其先序、中序、後序周遊都是從根節點開始的，且在周遊過程中經過節點的路線也是一樣的，隻是通路的時機不同而已。
一、非遞歸周遊的路線
路線圖如下：
沿着該路線：
按 ▲ 标記的節點讀得的序列為先序序列
按 * 标記的節點讀得的序列為中序序列
按 # 标記的節點讀得的序列為後序序列
1、首先建立一個二叉樹:
#include <stdio.h>
#include <stdlib.h>
#define maxsize 100
//先序周遊非遞歸實作
typedef char Elemtype;
typedef struct node{
Elemtype date;
struct node *lchild,*rchild;
}bitree;
bitree *createtree()
{
bitree *pA = (bitree*)malloc(sizeof(bitree));
bitree *pB = (bitree*)malloc(sizeof(bitree));
bitree *pC = (bitree*)malloc(sizeof(bitree));
bitree *pD = (bitree*)malloc(sizeof(bitree));
bitree *pE = (bitree*)malloc(sizeof(bitree));
bitree *pF = (bitree*)malloc(sizeof(bitree));
bitree *pG = (bitree*)malloc(sizeof(bitree));
pA->date = 'A';
pB->date = 'B';
pC->date = 'C';
pD->date = 'D';
pE->date = 'E';
pF->date = 'F';
pG->date = 'G';
pA->lchild = pB;
pA->rchild = pC;
pB->lchild = NULL;
pB->rchild = pD;
pC->lchild = NULL;
pC->rchild = pE;
pD->lchild = pF;
pD->rchild = pG;
pE->lchild = NULL;
pE->rchild = NULL;
pF->lchild = NULL;
pF->rchild = NULL;
pG->lchild = NULL;
pG->rchild = NULL;
return pA;
}
二、先序周遊的非遞歸實作
1、實作方法如下：
在沿左子樹搜尋時，當搜尋的節點不為空時，先通路節點，然後再進棧，在搜尋左節點，不為空時繼續通路并且入棧，繼續以此規律搜尋
當搜尋的節點為空時，讓一個節點出棧，然後搜尋節點的右節點，再為空時再出棧一個節點，并且繼續搜尋右子樹
2、實作代碼如下：
//先序周遊非遞歸實作
void preorder(bitree *t)
{
bitree *Stack[maxsize];
int top = -1;
bitree *p;
if(t==NULL){
printf("樹為空\n");
}
p = t;
while(p!=NULL||top!=-1){
while(p!=NULL){
printf("%c ",p->date);//通路節點的資料域
if(top<maxsize-1){
top++;
Stack[top] = p;//入棧
}else{
printf("錯誤\n");
}
p = p->lchild;//指向左孩子
}
if(top==-1){
printf("空");
}else{
p = Stack[top];//出棧
top--;
p = p->rchild;//指向右孩子
}
}
}
3、在主函數中實作如下：
int main()
{
bitree *t;
t = createtree();
printf("先序周遊非遞歸實作：");
preorder(t);
printf("\n");
return 0;
}
三、中序周遊的非遞歸實作
1、實作方法如下：
在沿左子樹搜尋時，當搜尋的節點不為空時，先進棧，在搜尋左節點，不為空時繼續入棧，繼續以此規律搜尋
當搜尋的節點為空時，讓一個節點出棧，并且通路該節點，然後搜尋節點的右節點，再為空時再出棧一個節點并通路該節點，且繼續搜尋右子樹
2、實作代碼如下：
//中序周遊非遞歸實作
void inorder(bitree *t)
{
bitree *Stack[maxsize];
int top = -1;
bitree *p;
if(t==NULL){
printf("樹為空\n");
}
p = t;
while(p!=NULL||top!=-1){
while(p!=NULL){
if(top<maxsize-1){
top++;
Stack[top] = p;//入棧
}else{
printf("錯誤\n");
}
p = p->lchild;//指向左孩子
}
if(top==-1){
printf("空\n");
}else{
p = Stack[top];//出棧
printf("%c ",p->date);//通路節點的資料域
top--;
p = p->rchild;//指向右孩子
}
}
}
四、後序周遊的非遞歸實作
1、實作方法如下
在沿左子樹搜尋時，當搜尋的節點不為空時，先進棧，在搜尋左節點，不為空時繼續入棧，繼續以此規律搜尋
當搜尋的節點為空時，讓一個節點出棧，節點标記為1，第一次出棧，節點不能通路，繼續讓該節點入棧,然後搜尋節點的右節點，再為空時再出棧一個節點，且繼續搜尋右子樹,
當節點第二次出棧時，該節點标記為2，此時通路該節點，第二次出棧,節點可以通路,然後搜尋節點的右節點，再為空時再出棧一個節點，且繼續搜尋右子樹
該樹的先序周遊結果為：ABDFGCE
_代表空格
在輸入時應該輸入成:AB_DF_ _G_ _C_E_ _
2、實作代碼如下
#include<stdio.h>
#include<stdlib.h>
#define MAX 100 // 棧中最後存儲的結點數
typedef char ElemType; // 為結點資料類型起别名
typedef struct node // 二叉樹中結點存儲結構
{
ElemType data; // 存儲結點資料
struct node * lchild; // 指向結點左孩子指針
struct node * rchild; // 指向結點右孩子指針
}BSTree; //為二叉樹中結點存儲結構起别名
typedef struct //二叉樹結點順序棧結構體定義
{
BSTree* data[MAX]; //數組存儲二叉樹各個結點
int top; //用于訓示棧頂
}Stack; //二叉樹順序棧結構體類型的别名
int flag[MAX]; //用于辨別每個結點是第幾次入棧
//初始化順序棧
Stack * Init()
{
Stack * S;
//為通訊錄順序棧配置設定記憶體
S=(Stack *)malloc(sizeof(Stack ));
if(S==NULL) //判斷記憶體配置設定是否成功
{
printf("記憶體配置設定失敗，結束程式\n");
exit(0);
}
else
{
S->top=-1; //當棧為空時，順序棧的棧頂位置設定為-1
return S; //傳回順序棧的位址
}
}
//順序棧的入棧
void Push(Stack *S, BSTree* x)
{
if(S->top<MAX) //判斷順序棧中是否已滿
{
S->top ++; //将棧頂位置加1，為入棧元素做好準備
//将入棧的元素的資料放置在棧頂位置
S->data[S->top ]=x;
}
else
printf("棧已滿，無法入棧！\n");
}
//順序棧出棧
void Pop(Stack *S, BSTree **x)
{
if(S->top!=-1) //判斷棧是否為空
{
//将棧頂元素的資料指派給x指針所指向的變量
(*x)=S->data[S->top];
S->top--; //将棧頂位置減1
}
else
printf("棧為空，無法出棧!\n");
}
//建立二叉樹
BSTree * Create()
{
ElemType ch;
BSTree * root;
scanf("%c",&ch); // 輸入要建立二叉樹的根結點資料
if(ch==' ') // 判斷二叉樹是否為空的二叉樹
root=NULL; // 如果是空的二叉樹則二叉樹的根結點指針為空
else // 如果不是則建立二叉樹的根結點
{
//為二叉樹的根結點配置設定存儲空間
root=(BSTree*)malloc(sizeof(BSTree));
root->data=ch; // 将輸入的資料存儲在根結點的資料域中
//通過遞歸調用建立根結點的左孩子結點，并使根結點左孩子指針指向該結點
root->lchild=Create();
//通過遞歸調用建立根結點的右孩子結點，并使根結點右孩子指針指向該結點
root->rchild=Create();
}
return root;
}
//非遞歸後序周遊二叉樹
void Postorder(BSTree *root)
{
Stack *s1; //定義一個指向棧的指針
s1=Init(); //初始化棧
//判斷二叉樹是否周遊完了，當二叉樹結點指針為空并且棧為空時表示
//二叉樹周遊完了
while(root!=NULL || s1->top>-1)
{
if(root!=NULL) //當結點不為空時
{
Push(s1,root); // 将周遊中遇到的結點入棧
flag[s1->top]=1; //辨別該結點第1次入棧
root=root->lchild; // 得到該結點的左孩子結點
}
else //當結點為空時，
{
Pop(s1,&root); //從棧中出棧得到一個結點
if(flag[s1->top+1]==1)//判斷出棧的結點是不是第1次入棧
{
Push(s1,root);//如果是第1次入棧則再次入棧
flag[s1->top]=2; //辨別該結點第2次入棧
root=root->rchild; // 得到該結點的左孩子結點
}
//如果出棧的結點是2次入棧，則輸出該結點資料，并設定指向結點指針為空
else
{
printf("%3c",root->data); //輸出結點資料
root=NULL; // 設定指針為空
}
}
}
}
int main()
{
BSTree *t;
printf("輸入要建立的樹的根節點資料：\n");
t =Create();
printf("後序周遊非遞歸實作：");
Postorder(t);
printf("\n");
return 0;
}
3、實作如下
五、總結
無論是遞歸還是非遞歸周遊二叉樹，由于每個節點僅被通路一次，則無論按哪一種次序進行周遊，對含n個節點的二叉樹，其時間複雜性均為O（n）。所需輔助空間為周遊過程中棧的最大容量，即樹的深度，最壞情況下為n，即空間複雜度也為O（n）。