假設二叉樹采用鏈接存儲結構存儲,設計一個算法,求二叉樹b的寬度

1、假設二叉樹采用鏈接存儲結構存儲，設計一個算法，求二叉樹b的寬度程序1#include #include #define MaxSize 100typedef char ElemType; typedef struct node數據元素指向左孩子數據元素指向左孩子指向右孩子ElemType data; struct node *lchild; struct node *rchild; BTNode;void CreateBTNode(BTNode *&b,char *str)由str 串創(chuàng)建二叉鏈BTNode *StMaxSize,*p=NULL;int top=-l,k,j=0;char ch

2、;b=NULL;建立的二叉樹初始時為空ch=strj;while (ch!=0) /str未掃描完時循環(huán)switch(ch)case (:top +;Sttop=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:Sttop -lchild=p ;bre

3、ak;case 2:Sttop -rchild=p ;break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x)返回data域為 x的結點指針 BTNode *p;if (b=NULL)return NULL;else if (b-data=x)return b;elsep =FindNode(b-lchild x);if (p !=NULL)return p;elsereturn FindNode(b-rchild,x);BTNode *LchildNode(BTNode *p)返回*卩結點的左孩子結點指針return p-lchild;B

4、TNode *RchildNode(BTNode *p)返回*卩結點的右孩子結點指針return p-rchild;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();int BTWidth(BTNode *b) 求二叉樹b 的寬度structint lno;結點的

5、層次編號BTNode *p;結點指針 QuMaxSize;定義順序非循環(huán)隊列int front,rear;int lnum,max,i,n;int front,rear;int lnum,max,i,n;front=rear=0;if (b!=NULL)rear+;Qurear.p=b;Qurear.lno=1; while (rear!=front) front+;b=Qufront.p;/定義隊首和隊尾指針/置隊列為空隊根結點指針入隊/根結點的層次編號為隊列不為空隊頭出隊lnum= Qu front .lno;if (b-lchild!=NULL)if (b-lchild!=NULL)左孩

6、子入隊rear+;Qurear.p =b-lchild;/右孩子入隊/右孩子入隊if (b-rchild!=NULL)rear+;Qurear.p =b-rchild;Qu rear.lno=lnum+1;max=O;lnum=l;i=l;while (i=rear)n=0;while (imax) max=n;return max;elsereturn 0;程序2#include typedef char ElemType;typedef struct nodeElemType data;數據元素struct node *lchild;/扌旨向左孩子struct node *rchild;/

7、扌旨向右孩子 BTNode;extern void CreateBTNode (BTNode *&b,char *str); extern BTNode *FindNode(BTNode *b,ElemType x); externBTNode *LchildNode(BTNode *p);extern BTNode *RchildNode(BTNode *p);extern int BTNodeDepth(BTNode *b);extern void DispBTNode (BTNode *b);extern int BTWidth(BTNode *b);extern int Nodes(BTNode *b);extern int LeafNodes(BTNode *b);void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,A(B(D(H,G),C(E,F); printf(n);p=FindNode(b,H);if (p!=NULL)lp=LchildNode(p);if (lp!=NULL)printf(” 左孩子為。,lp-data);elseprintf(無左孩子);rp =RchildNode(p);if (rp!=NULL)printf(右孩子為 %c,rp-d