二叉樹的輸入
二叉樹的輸入
你這個函數(shù)如果BinTree是struct node 指針類型的話是錯的，按照你的想法實(shí)現(xiàn)如下，測試用例是：0137++8++49+++25++6++，其中用加號表示空格，便于表示幾個空格（輸入時用空格代替加號就可以了），這是一顆用寬度優(yōu)先搜索得到0123456789的完全二叉樹，程序中打印樹以及建樹均是先序遍歷。
數(shù)據(jù)結(jié)構(gòu) 創(chuàng)建二叉樹
//?
二叉樹 數(shù)據(jù)結(jié)構(gòu)
#include<iostream>#include<cmath>//提供pow()函數(shù)using namespace std;#define OK 1#define ERROR 0typedef int Status;typedef struct BiTNode{ int data; struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//先序輸出二叉樹void PreOrderTraverse(BiTree T){ if(T) { cout<<T->data<<\’ \’; PreOrderTraverse(T->lChild); PreOrderTraverse(T->rChild); }}//中序輸出二叉樹void InOrderTraverse(BiTree T){ if(T) { InOrderTraverse(T->lChild); cout<<T->data<<\’ \’; InOrderTraverse(T->rChild); }}//后序輸出二叉樹void PostOrderTraverse(BiTree T){ if(T) { PostOrderTraverse(T->lChild); PostOrderTraverse(T->rChild); cout<<T->data<<\’ \’; }}//創(chuàng)建二叉樹Status CreateBiTree(BiTree& T){ int num; cin>>num; if(num==0) T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); T->data=num; CreateBiTree(T->lChild); CreateBiTree(T->rChild); } return OK;}//計算二叉樹的深度int BiTreeDepth(BiTree T){ int depth1,depth2; if(!T) return 0; else{ depth1=BiTreeDepth(T->lChild); depth2=BiTreeDepth(T->rChild); if(depth1>depth2) return depth1+1; else return depth2+1; }}static int n=0;int CountNode(BiTree T){ if(T) { n++; CountNode(T->lChild); CountNode(T->rChild); } return n;}//計算深度為depth的滿二叉樹的結(jié)點(diǎn)數(shù)inline int Count(int depth){ return pow(2,depth)-1;//滿二叉樹的結(jié)點(diǎn)計算法}int main(){ int depth,num; BiTree T; cout<<\”默認(rèn)為先序輸入二叉樹數(shù)據(jù)(以0為空格字符)。\”<<endl; cout<<\”例如:只有一個結(jié)點(diǎn)的二叉樹,輸入形式為:1 0 0\”<<endl<<endl;; cout<<\”現(xiàn)在,請您輸入\”<<endl; if(CreateBiTree(T)) { cout<<\”先序結(jié)果為:\”<<endl; PreOrderTraverse(T); cout百科<<endl<<endl; cout<<\”中序結(jié)果為:\”<<endl; InOrderTraverse(T); cout<<endl<<endl; cout<<\”后序結(jié)果為:\”<<endl; PostOrderTraverse(T); cout<<endl<<endl; depth=BiTreeDepth(T); num=CountNode(T); if(num==Count(depth))// cout<<\”二叉樹為滿二叉樹。
\”<<endl; else cout<<\”二叉樹不是滿二叉樹。
\”<<endl; } return 0;}我已經(jīng)調(diào)試過了，可以通過。
