生活随笔
收集整理的這篇文章主要介紹了
二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
一、基本概念
每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，左子樹(shù)和右子樹(shù)，次序不可以顛倒。
性質(zhì)：
1、非空二叉樹(shù)的第n層上至多有2^(n-1)個(gè)元素。
2、深度為h的二叉樹(shù)至多有2^h-1個(gè)結(jié)點(diǎn)。
滿二叉樹(shù)：所有終端都在同一層次，且非終端結(jié)點(diǎn)的度數(shù)為2。
在滿二叉樹(shù)中若其深度為h，則其所包含的結(jié)點(diǎn)數(shù)必為2^h-1。
完全二叉樹(shù)：除了最大的層次即成為一顆滿二叉樹(shù)且層次最大那層所有的結(jié)點(diǎn)均向左靠齊，即集中在左面的位置上，不能有空位置。
對(duì)于完全二叉樹(shù)，設(shè)一個(gè)結(jié)點(diǎn)為i則其父節(jié)點(diǎn)為i/2，2i為左子節(jié)點(diǎn)，2i+1為右子節(jié)點(diǎn)。
二、存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)：
將數(shù)據(jù)結(jié)構(gòu)存在一塊固定的數(shù)組中。
[cpp]?view plaincopyprint?
#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)勢(shì)，但因所占空間比較大，是非主流二叉樹(shù)。二叉樹(shù)通常以鏈?zhǔn)酱鎯?chǔ)。
鏈?zhǔn)酱鎯?chǔ)：
[cpp]?view plaincopyprint?
typedef?char?datatype;?? ?? typedef?struct?BinNode{?? ????datatype?data;?? ????struct?BinNode*?lchild;?? ????struct?BinNode*?rchild;?? }BinNode;?? ?? typedef?BinNode*?bintree;????????????
?三、二叉樹(shù)的遍歷
遍歷即將樹(shù)的所有結(jié)點(diǎn)訪問(wèn)且僅訪問(wèn)一次。按照根節(jié)點(diǎn)位置的不同分為前序遍歷，中序遍歷，后序遍歷。
前序遍歷：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
中序遍歷：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
后序遍歷：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)
例如：求下面樹(shù)的三種遍歷
?
前序遍歷：abdefgc
中序遍歷：debgfac
后序遍歷：edgfbca
四、遍歷的實(shí)現(xiàn)
遞歸實(shí)現(xiàn)(以前序遍歷為例，其他的只是輸出的位置稍有不同)
[cpp]?view plaincopyprint?
void?preorder(bintree?t){?? ????if(t){?? ????????printf("%c?",t->data);?? ????????preorder(t->lchild);?? ????????preorder(t->rchild);?? ????}?? }??
非遞歸的實(shí)現(xiàn)
因?yàn)楫?dāng)遍歷過(guò)根節(jié)點(diǎn)之后還要回來(lái)，所以必須將其存起來(lái)。考慮到后進(jìn)先出的特點(diǎn)，選用棧存儲(chǔ)。數(shù)量確定，以順序棧存儲(chǔ)。
[cpp]?view plaincopyprint?
#define?SIZE?100?? typedef?struct?seqstack{?? ????bintree?data[SIZE];?? ????int?tag[SIZE];????? ????int?top;??????? }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、前序遍歷?
[cpp]?view plaincopyprint?
void?preorder_dev(bintree?t){?? ????seqstack?s;?? ????s.top?=?-1;??????? ????if(!t){?? ????????printf("the?tree?is?empty\n");?? ????}else{?? ????????while(t?||?s.stop?!=?-1){?? ????????????while(t){?????? ??????????????????printf("%c?",t->data);?? ????????????????push(&s,t);?? ????????????????t=?t->lchild;?? ????????????}?? ????????????t=pop(&s);?? ????????????t=t->rchild;?? ????????}?? ????}?? }??
?2、中序遍歷
?
[cpp]?view plaincopyprint?
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、后序遍歷
因?yàn)楹笮虮闅v最后還要要訪問(wèn)根結(jié)點(diǎn)一次，所以要訪問(wèn)根結(jié)點(diǎn)兩次。采取夾標(biāo)志位的方法解決這個(gè)問(wèn)題。
這段代碼非常糾結(jié)，對(duì)自己有信心的朋友可以嘗試獨(dú)立寫一下。反正我是寫了很長(zhǎng)時(shí)間。邏輯不難，我畫了一張邏輯圖：
?代碼：
?
[cpp]?view plaincopyprint?
void?postorder_dev(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);?? ????????????????s.tag[s.top]?=?0;????? ????????????????t=?t->lchild;?? ????????????}?? ????????????if(s.tag[s.top]?==?0){???? ????????????????t=?s.data[s.top];????? ????????????????s.tag[s.top]=1;??????? ????????????????t=t->rchild;?? ????????????}else?{?? ????????????????while?(s.tag[s.top]?==?1){??? ????????????????????t?=?pop(&s);?? ????????????????????printf("%c?",t->data);?? ????????????????}?? ????????????????t?=?NULL;??? ????????????}?? ????????}?? ????}?? }??
?4、層次遍歷：即每一層從左向右輸出
元素需要儲(chǔ)存有先進(jìn)先出的特性，所以選用隊(duì)列存儲(chǔ)。
隊(duì)列的定義：
[cpp]?view plaincopyprint?
#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];?? ????}?? }??
遍歷實(shí)現(xiàn)?
[cpp]?view plaincopyprint?
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é)果生成二叉樹(shù)
[cpp]?view plaincopyprint?
?? ?? 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、二叉樹(shù)的查找
[cpp]?view plaincopyprint?
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)計(jì)結(jié)點(diǎn)個(gè)數(shù)
[cpp]?view plaincopyprint?
int?count_tree(bintree?t){?? ????if(t){?? ????????return?(count_tree(t->lchild)+count_tree(t->rchild)+1);?? ????}?? ????return?0;?? }??
8、比較兩個(gè)樹(shù)是否相同
[cpp]?view plaincopyprint?
int?is_equal(bintree?t1,bintree?t2){?? ????if(!t1?&&?!t2){???????? ????????return?1;?? ????}?? ????if(t1?&&?t2?&&?t1->data?==?t2->data){???????? ????????if(is_equal(t1->lchild,t2->lchild))?? ????????????if(is_equal(t1->rchild,t2->rchild)){?? ????????????????return?1;?? ????????????}?? ????}?? ????return?0;?? }??
9、求二叉樹(shù)的深度
[cpp]?view plaincopyprint?
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;?? }??
?
總結(jié)
以上是生活随笔為你收集整理的二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
