C語言二叉樹常見操作詳解【前序,中序,后序,層次遍歷及非遞歸查找,統(tǒng)計個數(shù),比較,求深度】
更新時間：2018年04月20日 09:42:26 作者：松陽
這篇文章主要介紹了C語言二叉樹常見操作,結(jié)合實例形式詳細分析了基于C語言的二叉樹前序,中序,后序,層次遍歷及非遞歸查找,統(tǒng)計個數(shù),比較,求深度等相關操作技巧與注意事項,需要的朋友可以參考下
本文實例講述了C語言二叉樹常見操作。分享給大家供大家參考，具體如下：
一、基本概念
每個結(jié)點最多有兩棵子樹，左子樹和右子樹，次序不可以顛倒。
性質(zhì)：
1、非空二叉樹的第n層上至多有2^(n-1)個元素。
2、深度為h的二叉樹至多有2^h-1個結(jié)點。
滿二叉樹：所有終端都在同一層次，且非終端結(jié)點的度數(shù)為2。
在滿二叉樹中若其深度為h，則其所包含的結(jié)點數(shù)必為2^h-1。
完全二叉樹：除了最大的層次即成為一顆滿二叉樹且層次最大那層所有的結(jié)點均向左靠齊，即集中在左面的位置上，不能有空位置。
對于完全二叉樹，設一個結(jié)點為i則其父節(jié)點為i/2，2i為左子節(jié)點，2i+1為右子節(jié)點。
二、存儲結(jié)構(gòu)
順序存儲：
將數(shù)據(jù)結(jié)構(gòu)存在一塊固定的數(shù)組中。
#define LENGTH 100
typedef char datatype;
typedef struct node{
datatype data;
int lchild,rchild;
int parent;
}Node;
Node tree[LENGTH];
int length;
int root;
雖然在遍歷速度上有一定的優(yōu)勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈式存儲。
鏈式存儲：
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode* lchild;
struct BinNode* rchild;
}BinNode;
typedef BinNode* bintree; //bintree本身是個指向結(jié)點的指針
三、二叉樹的遍歷
遍歷即將樹的所有結(jié)點訪問且僅訪問一次。按照根節(jié)點位置的不同分為前序遍歷，中序遍歷，后序遍歷。
前序遍歷：根節(jié)點->左子樹->右子樹
中序遍歷：左子樹->根節(jié)點->右子樹
后序遍歷：左子樹->右子樹->根節(jié)點
例如：求下面樹的三種遍歷
前序遍歷：abdefgc
中序遍歷：debgfac
后序遍歷：edgfbca
四、遍歷的實現(xiàn)
遞歸實現(xiàn)(以前序遍歷為例，其他的只是輸出的位置稍有不同)
void preorder(bintree t){
if(t){
printf("%c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
非遞歸的實現(xiàn)
因為當遍歷過根節(jié)點之后還要回來，所以必須將其存起來。考慮到后進先出的特點，選用棧存儲。數(shù)量確定，以順序棧存儲。
#define SIZE 100
typedef struct seqstack{
bintree data[SIZE];
int tag[SIZE]; //為后續(xù)遍歷準備的
int top; //top為數(shù)組的下標
}seqstack;
void push(seqstack *s,bintree t){
if(s->top == SIZE){
printf("the stack is full\n");
}else{
s->top++;
s->data[s->top]=t;
}
}
bintree pop(seqstack *s){
if(s->top == -1){
return NULL;
}else{
s->top--;
return s->data[s->top+1];
}
}
1、前序遍歷
void preorder_dev(bintree t){
seqstack s;
s.top = -1; //因為top在這里表示了數(shù)組中的位置，所以空為-1
if(!t){
printf("the tree is empty\n");
}else{
while(t || s.stop != -1){
while(t){ //只要結(jié)點不為空就應該入棧保存，與其左右結(jié)點無關
printf("%c ",t->data);
push(&s,t);
t= t->lchild;
}
t=pop(&s);
t=t->rchild;
}
}
}
2、中序遍歷
void midorder(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!\n");
}else{
while(t ||s.top != -1){
while(t){
push(&s,t);
t= t->lchild;
}
t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}
3、后序遍歷
因為后序遍歷最后還要要訪問根結(jié)點一次，所以要訪問根結(jié)點兩次。采取夾標志位的方法解決這個問題。
這段代碼非常糾結(jié)，對自己有信心的朋友可以嘗試獨立寫一下。反正我是寫了很長時間。邏輯不難，我畫了一張邏輯圖：
代碼：
void postorder_dev(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!\n");
}else{
while(t || s.top != -1){ //?？樟说耐瑫rt也為空。
while(t){
push(&s,t);
s.tag[s.top] = 0; //設置訪問標記，0為第一次訪問，1為第二次訪問
t= t->lchild;
}
if(s.tag[s.top] == 0){ //第一次訪問時，轉(zhuǎn)向同層右結(jié)點
t= s.data[s.top]; //左走到底時t是為空的，必須有這步！
s.tag[s.top]=1;
t=t->rchild;
}else {
while (s.tag[s.top] == 1){ //找到棧中下一個第一次訪問的結(jié)點，退出循環(huán)時并沒有pop所以為其左子結(jié)點
t = pop(&s);
printf("%c ",t->data);
}
t = NULL; //必須將t置空。跳過向左走，直接向右走
}
}
}
}
4、層次遍歷：即每一層從左向右輸出
元素需要儲存有先進先出的特性，所以選用隊列存儲。
隊列的定義：
#define MAX 1000
typedef struct seqqueue{
bintree data[MAX];
int front;
int rear;
}seqqueue;
void enter(seqqueue *q,bintree t){
if(q->rear == MAX){
printf("the queue is full!\n");
}else{
q->data[q->rear] = t;
q->rear++;
}
}
bintree del(seqqueue *q){
if(q->front == q->rear){
return NULL;
}else{
q->front++;
return q->data[q->front-1];
}
}
遍歷實現(xiàn)
void level_tree(bintree t){
seqqueue q;
bintree temp;
q.front = q.rear = 0;
if(!t){
printf("the tree is empty\n");
return ;
}
enter(&q,t);
while(q.front != q.rear){
t=del(&q);
printf("%c ",t->data);
if(t->lchild){
enter(&q,t->lchild);
}
if(t->rchild){
enter(&q,t->rchild);
}
}
}
5、利用前序遍歷的結(jié)果生成二叉樹
//遞歸調(diào)用，不存點，想的時候只關注于一個點，因為還會回來的，不要跟蹤程序運行，否則容易多加循環(huán)
void createtree(bintree *t){
datatype c;
if((c=getchar()) == '#')
*t = NULL;
else{
*t = (bintree)malloc(sizeof(BinNode));
(*t)->data = c;
createtree(&(*t)->lchild);
createtree(&(*t)->rchild);
}
}
6、二叉樹的查找
bintree search_tree(bintree t,datatype x){
if(!t){
return NULL;
}
if(t->data == x){
return t;
}else{
if(!search_tree(t->lchild,x)){
return search_tree(t->rchild,x);
}
return t;
}
}
7、統(tǒng)計結(jié)點個數(shù)
int count_tree(bintree t){
if(t){
return (count_tree(t->lchild)+count_tree(t->rchild)+1);
}
return 0;
}
8、比較兩個樹是否相同
int is_equal(bintree t1,bintree t2){
if(!t1 && !t2){ //都為空就相等
return 1;
}
if(t1 && t2 && t1->data == t2->data){ //有一個為空或數(shù)據(jù)不同就不判斷了
if(is_equal(t1->lchild,t2->lchild))
if(is_equal(t1->rchild,t2->rchild)){
return 1;
}
}
return 0;
}
9、求二叉樹的深度
int hight_tree(bintree t){
int h,left,right;
if(!t){
return 0;
}
left = hight_tree(t->lchild);
right = hight_tree(t->rchild);
h = (left>right?left:right)+1;
return h;
}
希望本文所述對大家C語言程序設計有所幫助。
相關文章
這篇文章主要給大家介紹了C/C++判斷素數(shù)的三種方法,常規(guī)的函數(shù)判斷法,埃氏篩法和歐拉篩法這三種方法,并通過代碼示例講解的非常詳細,具有一定的參考價值,需要的朋友可以參考下2023-12-12
這篇文章主要為大家介紹了C語言特殊符號的使用補充理解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-02-02
當程序與外界進行信息交換時，存在兩個對象，一個是程序中的對象，另一個是文件對象。流是信息流動的一種抽象，它負責在數(shù)據(jù)的生產(chǎn)者和數(shù)據(jù)的消費者之間建立聯(lián)系，并管理數(shù)據(jù)的流動2022-05-05
這篇文章主要介紹了C++實現(xiàn)棧的操作(push和pop)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
單值二叉樹你可能之前沒見過，如果二叉樹每個節(jié)點都具有相同的值，那么該二叉樹就是單值二叉樹，讓我們通過一個真題來深刻了解它吧2022-04-04
這篇文章主要為大家詳細介紹了C語言之二維數(shù)組，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助2022-01-01
C++數(shù)據(jù)結(jié)構(gòu)與算法之判斷一個鏈表是否為回文結(jié)構(gòu)的方法
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)與算法之判斷一個鏈表是否為回文結(jié)構(gòu)的方法,結(jié)合實例形式分析了回文結(jié)構(gòu)并結(jié)合實例給出了C++判斷回文的操作技巧,需要的朋友可以參考下2017-05-05
這篇文章主要給大家介紹了關于c++中引用作為形參的使用方法以及作用的相關資料,引用是地址傳值,作為引用的形參數(shù)值被修改的同時,也修改了對應實參的值,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-11-11
c++中strcpy函數(shù)在VS2015無法使用的問題
這篇文章主要介紹了c++中strcpy函數(shù)在VS2015無法使用的問題,具有一定的參考價值，有需要的可以了解一下。2016-11-11
經(jīng)典的推箱子是一個來自日本的古老游戲，目的是在訓練你的邏輯思考能力。本文將通過C語言和MySQL實現(xiàn)推箱子這一經(jīng)典游戲，感興趣的可以了解一下2022-02-02