1:首先讀者要了解二叉樹BinaryTree基本概念,其次區分左子樹與左孩子節點,右子樹與右孩子節點。(在資料結構中 一個節點可以成為一棵樹,對于沒有孩子節點的節點稱為為葉子節點)。
2:在讀這篇博文之前,讀者腦海中應該有這樣一個模型(看圖)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiclRnblN0LclHdpZXYyd2LcBzNvwVZ2x2bzNXak9CX90TQNNkRrFlQKBTSvwFbslmZvwFMwQzLcVmepNHdu9mZvwFVywUNMZTY18CX052bm9CX1Z1RhFDZzgFbWhUZ1Z0RhZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39zM1MDOykjMxIzNxQDM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
整棵二叉樹根節點為A,A的左孩子為B,A的左子樹由B、D、G 3個節點構成,A的右孩子為C,A的右子樹由C、E、F 3個節點構成;
B節點(樹,對于D、G來說,它就是D、G的根節點),A的左孩子為D,A的左子樹右D、G構成,B沒有右孩子和右子樹
D節點(樹,對于G來說,它就是G的根節點)D沒有左孩子和左子樹,D的右孩子為G,D的右子樹由D構成
G節點(葉子節點,個人觀點葉子節點可以稱為樹)
(C、E、F讀者可自行分析)
先序序列和中序序列構造二叉樹:
圖解:
上代碼:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char ElementType ;
typedef struct node
{
ElementType data ;
struct node * leftChild ;
struct node * rightChild ;
}BTNode;
//pre:存放先序序列 in:存放中序序列
BTNode *createBT(char *pre , char *in ,int n)
{
BTNode *b;
char *p ;
int k ;
if(n<=0)
return NULL;
b=(BTNode *)malloc(sizeof(BTNode));
b->data = *pre ;
int j=0;
for(p=in;p<in+n;p++)
{
if(*p == *pre)
break;
}
k=p-in; //确定根節點在中序序列(in)中的位置 編号為0,1,2,...,n-1 (類似于數組中的下标号,不是邏輯序号)
b->leftChild = createBT(pre+1,in,k); //遞歸構造左子數
b->rightChild = createBT(pre+1+k,p+1,n-k-1); //遞歸構造右子樹
return b ;
}
//先序周遊二叉樹BinaryTree:先周遊根節點接着周遊左子樹,最後周遊右子樹
//(不是左孩子節點和右孩子節點,概念要厘清哦(雖然節點也是一個樹))
void showBTPreOrder(BTNode *b)
{
if(b != NULL)
{
//周遊根節點
printf("%c",b->data);
//周遊左子樹
showBTPreOrder(b->leftChild);
//周遊右子樹
showBTPreOrder(b->rightChild);
}
}
//中序周遊二叉樹BinaryTree:先周遊左子樹,接着周遊根節點,左後周遊右子樹
//(不是左孩子節點和右孩子節點,概念要厘清哦(雖然節點也是一個樹))
void showBTInOrder(BTNode *b)
{
if(b!=NULL)
{
//周遊左子樹
showBTInOrder(b->leftChild);
//周遊根節點
printf("%c",b->data);
//周遊右子樹
showBTInOrder(b->rightChild);
}
}
int main()
{
BTNode *b = NULL ;
char pre[] = "ABDGCEF";
char in[] = "DGBAECF" ;
b=createBT(pre,in,7);
//先序周遊周遊二叉樹
printf("先序周遊周遊二叉樹:\n");
showBTPreOrder(b);
printf("\n");
//中序周遊周遊二叉樹
printf("中序周遊周遊二叉樹:\n");
showBTInOrder(b);
printf("\n");
return 0 ;
}
程式運作結果:
先序周遊周遊二叉樹:
ABDGCEF
中序周遊周遊二叉樹:
DGBAECF
Press any key to continue
後序序列和中序序列構造二叉樹:
圖解:
上代碼:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char ElementType ;
typedef struct node
{
ElementType data ;
struct node * leftChild ;
struct node * rightChild ;
}BTNode;
//post:存放後序序列 in:存放中序序列
BTNode *createBT(char *post , char *in ,int n)
{
BTNode *b;
char *p ,root ; //root:根節點值
int k ;
if(n<=0)
return NULL;
root=*(post+n-1) ; //擷取根節點的值
b=(BTNode *)malloc(sizeof(BTNode));
b->data = root ;
for(p=in;p<in+n;p++)
{
if(*p == root)
break;
}
k=p-in; //确定根節點在中序序列(in)中的位置(下标号) 編号為0,1,2,...,n-1 (類似于數組中的下标号,不是邏輯序号)
b->leftChild = createBT(post,in,k); //遞歸構造左子數
b->rightChild = createBT(post+k,p+1,n-k-1); //遞歸構造右子樹
return b ;
}
//中序周遊二叉樹BinaryTree:先周遊左子樹,接着周遊根節點,左後周遊右子樹
//(不是左孩子節點和右孩子節點,概念要厘清哦(雖然節點也是一個樹))
void showBTInOrder(BTNode *b)
{
if(b!=NULL)
{
//周遊左子樹
showBTInOrder(b->leftChild);
//周遊根節點
printf("%c",b->data);
//周遊右子樹
showBTInOrder(b->rightChild);
}
}
//後序周遊二叉樹BinaryTree:先周遊左子樹,接着周遊右子樹,左後周遊根節點
//(不是左孩子節點和右孩子節點,概念要厘清哦(雖然節點也是一個樹))
void showBTPostOrder(BTNode *b)
{
if(b != NULL)
{
//周遊左子樹
showBTPostOrder(b->leftChild);
//周遊右子樹
showBTPostOrder(b->rightChild);
//周遊根節點
printf("%c",b->data);
}
}
int main()
{
BTNode *b = NULL ;
char in[] = "DGBAECF";
char post[] = "GDBEFCA" ;
b=createBT(post,in,7);
//中序周遊周遊二叉樹
printf("中序周遊周遊二叉樹:\n");
showBTInOrder(b);
printf("\n");
//後序周遊周遊二叉樹
printf("後序周遊周遊二叉樹:\n");
showBTPostOrder(b);
printf("\n");
return 0 ;
}
程式運作結果:
中序周遊周遊二叉樹:
DGBAECF
後序周遊周遊二叉樹:
GDBEFCA
Press any key to continue