平衡二叉樹的判定

?1000(ms)

?10000(kb)

?2325?/?5161

Tags:?樹

編寫程序判斷給定的二叉樹是否是平衡二叉樹。

輸入

二叉樹的先序序列。

輸出

如果是平衡二叉樹，輸出yes！，否者輸出no！

樣例輸入

AB##C##

樣例輸出

yes！ #include<stdio.h> #include<malloc.h> struct BTNode {char data;int hight;//計算高度 BTNode *lchild;BTNode *rchild; }; void PreOrder(BTNode *&p)//先序遍歷創(chuàng)建二叉樹 {char a;scanf("%c",&a);if(a=='#') p=NULL;else{p=(BTNode *)malloc(sizeof(BTNode));p->data=a;PreOrder(p->lchild);PreOrder(p->rchild);} } void PostOrder(BTNode *&p)//后序遍歷賦值hight的值，即從樹的底部到根結(jié)點頂部 {if(p!=NULL){PostOrder(p->lchild);PostOrder(p->rchild);if(p->lchild==NULL&&p->rchild==NULL) p->hight=1;//如果左右結(jié)點都為空，則為底部的子葉結(jié)點，將hight賦值為1 else if(p->lchild!=NULL&&p->rchild==NULL) p->hight=p->lchild->hight+1;//一個孩子為空，一個孩子不為空，將其hight賦值為不為空的孩子的hight+1； else if(p->lchild==NULL&&p->rchild!=NULL) p->hight=p->rchild->hight+1;//一個孩子為空，一個孩子不為空，將其hight賦值為不為空的孩子的hight+1； else if(p->lchild!=NULL&&p->rchild!=NULL)//都不為空時hight賦值為左右孩子中最大的hight+1 {if(p->lchild->hight>p->rchild->hight) p->hight=p->lchild->hight+1;else p->hight=p->rchild->hight+1;}} } int t=0;//設(shè)置標(biāo)記 void Search(BTNode *&p)//先序遍歷查看該結(jié)點的左右孩子的hight值的差小于等于|1|。 {if(p!=NULL){if(p->lchild!=NULL&&p->rchild!=NULL){if(p->lchild->hight-p->rchild->hight!=0&&p->lchild->hight-p->rchild->hight!=1&&p->lchild->hight-p->rchild->hight!=-1) t=1;}else if(p->lchild!=NULL&&p->rchild==NULL){if(p->lchild->hight!=1) t=1;}else if(p->lchild==NULL&&p->rchild!=NULL){if(p->rchild->hight!=1) t=1;}Search(p->lchild);Search(p->rchild);} } int main() {BTNode *p;PreOrder(p);PostOrder(p);Search(p);if(t==0) printf("yes!");else printf("no!"); }

?

總結(jié)

以上是生活随笔為你收集整理的西南科技大学OJ题 平衡二叉树的判定1077的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。