假设二叉树采用二叉链存储结构存储#仅供借鉴

1、假设二叉树采用二叉链存储结构存储，分别实现以下算法，并在程序中完成测试：（1）计算二叉树节点个数；（2）输出所有叶子节点；（3）求二叉树b的叶子节点个数；（4）求二叉树b的宽度#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串创建

2、二叉链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); /销毁二叉树void LevelOrder(BTNode *b) BTNode *

3、p; BTNode *quMaxSize; /定义环形队列,存放节点指针 int front,rear; /定义队头和队尾指针 front=rear=-1; /置队列为空队列 rear+; qurear=b; /根节点指针进入队列 while (front!=rear) /队列不为空 front=(front+1)%MaxSize; p=qufront; /队头出队列 printf(%c ,p-data); /访问节点 if (p-lchild!=NULL) /有左孩子时将其进队 rear=(rear+1)%MaxSize; qurear=p-lchild; if (p-rchild!=NUL

4、L) /有右孩子时将其进队 rear=(rear+1)%MaxSize; qurear=p-rchild; void CreateBTNode(BTNode *&b,char *str) /由str串创建二叉链 BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=NULL; /建立的二叉树初始时为空 ch=strj; while (ch!=0) /str未扫描完时循环 switch(ch) case (: top+; Sttop=p; k=1; break; /为左节点 case ): top-; break; case ,: k=2

5、; 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; break; case 2: Sttop-rchild=p; break; j+; ch=strj; BTNode *FindNode(BTNode *b,ElemType x) /返回data域为x的节点指针 BTNode *p; if (b=NULL

6、) 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 lchil

7、ddep,rchilddep; if (b=NULL) return(0); /空树的高度为0 else lchilddep=BTNodeDepth(b-lchild); /求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild); /求右子树的高度为rchilddep return (lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); void DispBTNode(BTNode *b) /以括号表示法输出二叉树 if (b!=NULL) printf(%c,b-data); if (b-lchild!

8、=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); void PreOrder1(BTNode *b) BTNode *StMaxSize,*p; int top=-1; if (b!=NULL

9、) top+; /根节点入栈 Sttop=b; while (top-1) /栈不为空时循环 p=Sttop; /退栈并访问该节点 top-; printf(%c ,p-data); if (p-rchild!=NULL) /右孩子入栈 top+; Sttop=p-rchild; if (p-lchild!=NULL) /左孩子入栈 top+; Sttop=p-lchild; printf(n); void InOrder1(BTNode *b) BTNode *StMaxSize,*p; int top=-1; if (b!=NULL) p=b; while (top-1 | p!=NULL

10、) while (p!=NULL) top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop; top-; printf(%c ,p-data); p=p-rchild; printf(n); void PostOrder1(BTNode *b) BTNode *StMaxSize; BTNode *p; int flag,top=-1; /栈指针置初值 if (b!=NULL) do while (b!=NULL) /将t的所有左节点入栈 top+; Sttop=b; b=b-lchild; p=NULL; /p指向当前节点的前一个已访问的节点 flag=1; while (top!=-1 & flag) b=Sttop; /取出当前的栈顶元素 if (b-rchild=p) /右子树不存在或已被访问,访问之 printf(%c ,b-data); /访问*b节点 top-; p=b; /p指向则被访问的节点 else b=b-rchild; /t指向右子树 flag=0; while (top!=-1); printf(n); int main() BTNode *b; CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I);