二叉樹層次遍歷算法的驗(yàn)證 - 全文

/* ??
* 問題描述: 實(shí)現(xiàn)二叉樹的層次遍歷算法，并對用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”創(chuàng)建的二叉樹進(jìn)行測試。 ?
* 輸入描述:無需輸入 ?
* 程序輸出:實(shí)現(xiàn)各種算法的函數(shù)的測試結(jié)果 ?
*/ ???

?view plain copy
#include ?
#include "btree.h" ?
??
void LevelOrder(BTNode *b) ?
{ ?
????BTNode *p; ?
????//環(huán)形隊(duì)列采用順序隊(duì)存儲結(jié)構(gòu) ?
????BTNode *qu[MaxSize]; ???//定義環(huán)形隊(duì)列,存放節(jié)點(diǎn)指針 ?
????int front,rear; //定義隊(duì)頭和隊(duì)尾指針 ?
????front=rear=-1; ?????//置隊(duì)列為空隊(duì)列 ?
????rear++; ?
????qu[rear]=b; ????//根節(jié)點(diǎn)指針進(jìn)入隊(duì)列 ?
????while (front!=rear) //隊(duì)列不為空 ?
????{ ?
????????front=(front+1)%MaxSize; ?
????????p=qu[front]; ???????//隊(duì)頭出隊(duì)列(出隊(duì)結(jié)點(diǎn)p) ?
????????printf("%c ",p->data); ?//訪問節(jié)點(diǎn) ?
????????if (p->lchild!=NULL) ???//有左孩子時(shí)將其進(jìn)隊(duì) ?
????????{ ?
????????????rear=(rear+1)%MaxSize; ?
????????????qu[rear]=p->lchild; ?
????????} ?
????????if (p->rchild!=NULL) ???//有右孩子時(shí)將其進(jìn)隊(duì) ?
????????{ ?
????????????rear=(rear+1)%MaxSize; ?
????????????qu[rear]=p->rchild; ?
????????} ?
????} ?
} ?

??

int main() ?
{ ?
????BTNode *b; ?
????CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); ?
????printf("二叉樹b: "); ?
????DispBTNode(b); ?
????printf("\n"); ?
????printf("層次遍歷序列:\n"); ?
????LevelOrder(b); ?
????DestroyBTNode(b); ?
????return 0; ?
} ?
?
[cpp] view plain copy
#ifndef BTREE_H_INCLUDED ?
#define BTREE_H_INCLUDED ?
??
#define MaxSize 100 ?
typedef char ElemType; ?
typedef struct node ?
{ ?
????ElemType data; ?????????????//數(shù)據(jù)元素 ?
????struct node *lchild; ???????//指向左孩子 ?
????struct node *rchild; ???????//指向右孩子 ?
} BTNode; ?
void CreateBTNode(BTNode *&b,char *str); ???????//由str串創(chuàng)建二叉鏈 ?
BTNode *FindNode(BTNode *b,ElemType x); ????//返回data域?yàn)閤的節(jié)點(diǎn)指針 ?
BTNode *LchildNode(BTNode *p); ?//返回*p節(jié)點(diǎn)的左孩子節(jié)點(diǎn)指針 ?
BTNode *RchildNode(BTNode *p); ?//返回*p節(jié)點(diǎn)的右孩子節(jié)點(diǎn)指針 ?
int BTNodeDepth(BTNode *b); //求二叉樹b的深度 ?
void DispBTNode(BTNode *b); //以括號表示法輸出二叉樹 ?
void DestroyBTNode(BTNode *&b); ?//銷毀二叉樹 ?
??
#endif // BTREE_H_INCLUDED ?
?
view plain copy
#include ?
#include ?
#include "btree.h" ?
??
void CreateBTNode(BTNode *&b,char *str) ????//由str串創(chuàng)建二叉鏈 ?
{ ?
????BTNode *St[MaxSize],*p=NULL; ?
????int top=-1,k,j=0; ?
????char ch; ?
????b=NULL; ????????????//建立的二叉樹初始時(shí)為空 ?
????ch=str[j]; ?
????while (ch!='\0') ???//str未掃描完時(shí)循環(huán) ?
????{ ?
????????switch(ch) ?
????????{ ?
????????case '(': ?
????????????top++; ?
????????????St[top]=p; ?
????????????k=1; ?
????????????break; ?????//為左節(jié)點(diǎn) ?
????????case ')': ?
????????????top--; ?
????????????break; ?
????????case ',': ?
????????????k=2; ?
????????????break; ?????????????????????????//為右節(jié)點(diǎn) ?
????????default: ?
????????????p=(BTNode *)malloc(sizeof(BTNode)); ?
????????????p->data=ch; ?
????????????p->lchild=p->rchild=NULL; ?
????????????if (b==NULL) ???????????????????//p指向二叉樹的根節(jié)點(diǎn) ?
????????????????b=p; ?
????????????else ???????????????????????????//已建立二叉樹根節(jié)點(diǎn) ?
????????????{ ?
????????????????switch(k) ?
????????????????{ ?
????????????????case 1: ?
????????????????????St[top]->lchild=p; ?
????????????????????break; ?
????????????????case 2: ?
????????????????????St[top]->rchild=p; ?
????????????????????break; ?
????????????????} ?
????????????} ?
????????} ?
????????j++; ?
????????ch=str[j]; ?
????} ?
} ?

BTNode *FindNode(BTNode *b,ElemType x) ?//返回data域?yàn)閤的節(jié)點(diǎn)指針 ?
{ ?
????BTNode *p; ?
????if (b==NULL) ?
????????return NULL; ?
????else if (b->data==x) ?
????????return b; ?
????else ?
????{ ?
????????p=FindNode(b->lchild,x); ?
????????if (p!=NULL) ?
????????????return p; ?
????????else ?
????????????return FindNode(b->rchild,x); ?
????} ?
} ?
BTNode *LchildNode(BTNode *p) ??//返回*p節(jié)點(diǎn)的左孩子節(jié)點(diǎn)指針 ?
{ ?
????return p->lchild; ?
} ?
BTNode *RchildNode(BTNode *p) ??//返回*p節(jié)點(diǎn)的右孩子節(jié)點(diǎn)指針 ?
{ ?
????return p->rchild; ?
} ?
int BTNodeDepth(BTNode *b) ?//求二叉樹b的深度 ?
{ ?
????int lchilddep,rchilddep; ?
????if (b==NULL) ?
????????return(0); ?????????????????????????//空樹的高度為0 ?
????else ?
????{ ?
????????lchilddep=BTNodeDepth(b->lchild); ??//求左子樹的高度為lchilddep ?
????????rchilddep=BTNodeDepth(b->rchild); ??//求右子樹的高度為rchilddep ?
????????return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1); ?
????} ?
} ?
void DispBTNode(BTNode *b) ?//以括號表示法輸出二叉樹 ?
{ ?
????if (b!=NULL) ?
????{ ?
????????printf("%c",b->data); ?
????????if (b->lchild!=NULL || b->rchild!=NULL) ?
????????{ ?
????????????printf("("); ?
????????????DispBTNode(b->lchild); ?
????????????if (b->rchild!=NULL) printf(","); ?
????????????DispBTNode(b->rchild); ?
????????????printf(")"); ?
????????} ?
????} ?
} ?
void DestroyBTNode(BTNode *&b) ??//銷毀二叉樹 ?
{ ?
????if (b!=NULL) ?
????{ ?
????????DestroyBTNode(b->lchild); ?
????????DestroyBTNode(b->rchild); ?
????????free(b); ?
????} ?
} ?
?
運(yùn)行結(jié)果：