數據結構考研分類復習真題 第六章 答案 (五)[5]

　　．[題目分析]二叉樹是遞歸定義的以遞歸方式建立最簡單判定是否是完全二叉樹可以使用隊列在遍歷中利用完全二叉樹若某結點無左子女就不應有右子女的原則進行判斷

　　BiTree Creat()       //建立二叉樹的二叉鏈表形式的存儲結構
　　{ElemType xBiTree bt;
　　scanf(%d&x);  //本題假定結點數據域為整型
　　if(x==) bt=null;
　　else if(x>)
　　{bt=(BiNode *)malloc(sizeof(BiNode));
　　bt>data=x; bt>lchild=creat(); bt>rchild=creat();
　　}
　　else error(輸入錯誤)
　　return(bt);
　　}//結束 BiTree
　　int JudgeComplete(BiTree bt)  //判斷二叉樹是否是完全二叉樹如是返回否則返回
　　{int tag=; BiTree p=bt Q[]; // Q是隊列元素是二叉樹結點指針容量足夠大
　　if(p==null) return ();
　　QueueInit(Q); QueueIn(Qp);  //初始化隊列根結點指針入隊
　　while (!QueueEmpty(Q))
　　{p=QueueOut(Q);                                //出隊
　　if (p>lchild && !tag) QueueIn(Qp>lchild);  //左子女入隊
　　else {if (p>lchild) return ;                //前邊已有結點為空本結點不空
　　else tag=;                             //首次出現結點為空
　　if (p>rchild && !tag) QueueIn(Qp>rchild);  //右子女入隊
　　else if (p>rchild) return ; else tag=;
　　} //while
　　return ;  } //JudgeComplete

　　[算法討論]完全二叉樹證明還有其它方法判斷時易犯的錯誤是證明其左子樹和右子數都是完全二叉樹由此推出整棵二叉樹必是完全二叉樹的錯誤結論

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23735.html