需實現：（1）輸出二叉樹b的節點個數
? ? ? ? ? ? ? （2）輸出二叉樹b的葉子節點個數
? ? ? ? ? ? ? （3）求二叉樹b中指定節點值（假設所有節點值不同）的節點的層次。
? ? ? ? ? ? ? （4）利用層次遍歷求二叉樹b的寬度
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
const int MaxSize=10000;
using namespace std;
typedef struct node
{char data;struct node * lchild;struct node * rchild;
}BTNode;
typedef struct qnode
{BTNode *data;struct qnode *next;
}DataNode;
typedef struct
{int Size;DataNode *front;DataNode *rear;
}SqQueue;
void InitQueue(SqQueue * &q)
{q=(SqQueue *)malloc(sizeof(SqQueue));q->front=q->rear=NULL;q->Size=0;
}
bool QueueEmpty(SqQueue *q)
{return (q->rear==NULL);
}
void enQueue(SqQueue * &q,BTNode *e)
{DataNode *p;p=(DataNode *)malloc(sizeof(DataNode));p->data=e;p->next=NULL;if(q->rear==NULL)q->front=q->rear=p;else{q->rear->next=p;q->rear=p;}q->Size++;
}
bool deQueue(SqQueue * &q,BTNode * &e)
{DataNode * t;if(q->rear==NULL)return false;t=q->front;if(q->front==q->rear)q->front=q->rear=NULL;elseq->front=q->front->next;e=t->data;free(t);q->Size--;return true;
}
int QueueSize(SqQueue * q)
{return q->Size;
}
void CreatBTree(BTNode * &b,char * str) //建立二叉樹
{BTNode *St[MaxSize],*p;int top=-1,k,j=0;char ch;b=NULL;ch=str[j];while(ch!='\0'){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)b=p;else{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}
}
int yznum;
char yz[MaxSize];
void YZjiedian(BTNode *b) //找葉子節點的個數
{if(b!=NULL){if(b->lchild==NULL&&b->rchild==NULL) {yznum++;yz[yznum]=b->data;}YZjiedian(b->lchild);YZjiedian(b->rchild);}
}
int jdnum;
char jd[MaxSize];
void JieDian(BTNode *b) //找節點的個數
{if(b!=NULL){jdnum++;jd[jdnum]=b->data;JieDian(b->lchild);JieDian(b->rchild);}
}
void PreOrder(BTNode *b) //先序遍歷
{if(b!=NULL){printf("%c ",b->data);PreOrder(b->lchild);PreOrder(b->rchild);}
}
void InOrder(BTNode *b) //中序遍歷
{if(b!=NULL){InOrder(b->lchild);printf("%c ",b->data);InOrder(b->rchild);}
}
void PostOrder(BTNode *b) //后序遍歷
{if(b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);printf("%c ",b->data);}
}
int result;
void LevelOrder(BTNode *b) //求二叉樹的最大寬度
{BTNode *nape;nape=b;int cnt;BTNode *p;SqQueue *qu;InitQueue(qu);enQueue(qu,b);while(!QueueEmpty(qu)){cnt=QueueSize(qu);result=max(result,cnt);while(cnt--){deQueue(qu,p);if(p->lchild!=NULL)enQueue(qu,p->lchild);if(p->rchild!=NULL)enQueue(qu,p->rchild);}}
}
int FindJieDian(BTNode *b,char c) //尋找節點層次
{BTNode *nape;nape=b;int cnt;int level=0;BTNode *p;SqQueue *qu;InitQueue(qu);enQueue(qu,b);while(!QueueEmpty(qu)){cnt=QueueSize(qu);level++;while(cnt--){deQueue(qu,p);if(p->data==c)return level;if(p->lchild!=NULL)enQueue(qu,p->lchild);if(p->rchild!=NULL)enQueue(qu,p->rchild);}}return -1;
}
int main()
{char str[MaxSize]={"A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))"};printf("此棵二叉樹為:%s\n",str);BTNode *b;CreatBTree(b,str);JieDian(b);printf("此二叉樹的結點個數為：%d\n",jdnum);printf("此二叉樹的節點為:");for(int i=1;i<=jdnum;i++)printf(" %c",jd[i]);printf("\n");printf("先序遍歷輸出節點為：");PreOrder(b);printf("\n");printf("中序遍歷輸出節點為：");InOrder(b);printf("\n");printf("后序遍歷輸出節點為：");PostOrder(b);printf("\n");YZjiedian(b);printf("此二叉樹的葉子結點個數為：%d\n",yznum);printf("此二叉樹的葉子節點為:");for(int i=1;i<=yznum;i++)printf(" %c",yz[i]);printf("\n");LevelOrder(b);printf("此二叉樹的最大寬度為：%d\n",result);char ch;while(printf("請輸入你要查詢的節點：")!=EOF){scanf(" %c",&ch);int nape=FindJieDian(b,ch);if(nape==-1)printf("二叉樹中無此節點\n");elseprintf("節點%c在二叉樹中的層數為：%d\n",ch,nape);}return 0;
}
?
實現圖片：
)
