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

　　．BiTree Creat(ElemType A[]int i)
　　//n個結點的完全二叉樹存於一維數組A中本算法據此建立以二叉鏈表表示的完全二叉樹
　　{BiTree tree;
　　if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree>data=A[i];
　　if(*i>n) tree>lchild=nullelse tree>lchild=Creat(A*i)
　　if(*i+>n) tree>rchild=nullelse tree>rchild=Creat(A*i+)   }
　　return (tree) }//Creat

　　[算法討論]初始調用時i=

　　 [題目分析]二叉樹高度可遞歸計算如下若二叉樹為空則高度為零否則二叉樹的高度等於左右子樹高度的大者加這裡二叉樹為空的標記不是null而是設根結點層號為則每個結點的層號等於其雙親層號加

　　現將二叉樹的存儲結構定義如下:

　　typedef struct node
　　{int L[];//編號為i的結點的左兒子
　　int R[];//編號為i的結點的右兒子
　　int D[];//編號為i的結點的層號
　　int i;  //存儲結點的順序號（下標）
　　}tnode;
　　（）int Height(tnode tint i)//求二叉樹高度調用時i=
　　{int lhrh;
　　if (i==) return ();
　　else{lh=Height(ttL[i]); rh=Height(ttR[i]);
　　if(lh>rh) return(lh+); else return(rh+);
　　}
　　}//結束Height

　　（）int Level（tnode t）//求二叉樹各結點的層號已知編號為的結點是根且層號為
　　{tD[]=;
　　for(i=;i<=n;i++) {depth=tD[i]        //取出根結點層號
　　if(tL[i]!=)   tD[tL[i]]=depth+;   //i結點左兒子層號
　　if(tR[i]!=)   tD[tR[i]]=depth+;  }//i結點右兒子層號
　　}結束level

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

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