假设二叉树采用链接存储结构存储,设计一个算法,求二叉树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 串创建二叉链BTNode *StMaxSize,*p=NULL;int top=-l,k,j=0;char ch

2、;b=NULL;建立的二叉树初始时为空ch=strj;while (ch!=0) /str未扫描完时循环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;定义顺序非循环队列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