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

?view plain copy
#include ?
#include "btree.h" ?
??
void LevelOrder(BTNode *b) ?
{ ?
????BTNode *p; ?
????//環形隊列采用順序隊存儲結構 ?
????BTNode *qu[MaxSize]; ???//定義環形隊列,存放節點指針 ?
????int front,rear; //定義隊頭和隊尾指針 ?
????front=rear=-1; ?????//置隊列為空隊列 ?
????rear++; ?
????qu[rear]=b; ????//根節點指針進入隊列 ?
????while (front!=rear) //隊列不為空 ?
????{ ?
????????front=(front+1)%MaxSize; ?
????????p=qu[front]; ???????//隊頭出隊列(出隊結點p) ?
????????printf("%c ",p->data); ?//訪問節點 ?
????????if (p->lchild!=NULL) ???//有左孩子時將其進隊 ?
????????{ ?
????????????rear=(rear+1)%MaxSize; ?
????????????qu[rear]=p->lchild; ?
????????} ?
????????if (p->rchild!=NULL) ???//有右孩子時將其進隊 ?
????????{ ?
????????????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; ?????????????//數據元素 ?
????struct node *lchild; ???????//指向左孩子 ?
????struct node *rchild; ???????//指向右孩子 ?
} BTNode; ?
void CreateBTNode(BTNode *&b,char *str); ???????//由str串創建二叉鏈 ?
BTNode *FindNode(BTNode *b,ElemType x); ????//返回data域為x的節點指針 ?
BTNode *LchildNode(BTNode *p); ?//返回*p節點的左孩子節點指針 ?
BTNode *RchildNode(BTNode *p); ?//返回*p節點的右孩子節點指針 ?
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串創建二叉鏈 ?
{ ?
????BTNode *St[MaxSize],*p=NULL; ?
????int top=-1,k,j=0; ?
????char ch; ?
????b=NULL; ????????????//建立的二叉樹初始時為空 ?
????ch=str[j]; ?
????while (ch!='\0') ???//str未掃描完時循環 ?
????{ ?
????????switch(ch) ?
????????{ ?
????????case '(': ?
????????????top++; ?
????????????St[top]=p; ?
????????????k=1; ?
????????????break; ?????//為左節點 ?
????????case ')': ?
????????????top--; ?
????????????break; ?
????????case ',': ?
????????????k=2; ?
????????????break; ?????????????????????????//為右節點 ?
????????default: ?
????????????p=(BTNode *)malloc(sizeof(BTNode)); ?
????????????p->data=ch; ?
????????????p->lchild=p->rchild=NULL; ?
????????????if (b==NULL) ???????????????????//p指向二叉樹的根節點 ?
????????????????b=p; ?
????????????else ???????????????????????????//已建立二叉樹根節點 ?
????????????{ ?
????????????????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域為x的節點指針 ?
{ ?
????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節點的左孩子節點指針 ?
{ ?
????return p->lchild; ?
} ?
BTNode *RchildNode(BTNode *p) ??//返回*p節點的右孩子節點指針 ?
{ ?
????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); ?
????} ?
} ?
?
運行結果：