樹和二叉樹復(fù)習(xí)

樹和二叉樹復(fù)數(shù)分別為4，2，1，1則T中的葉子數(shù)為（） 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。(每個結(jié)點(diǎn)有多少個分支葉子（終010 機(jī)實(shí)( 的結(jié)點(diǎn)樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值由樹的性質(zhì)知：結(jié)點(diǎn)數(shù)為所有結(jié)點(diǎn)的度數(shù)之和加1同時注意到葉子結(jié)點(diǎn)的度數(shù)為0。則總結(jié)點(diǎn)數(shù)(設(shè)葉子結(jié)點(diǎn)數(shù)為X)葉子結(jié)點(diǎn)數(shù)為X=16-4-3-2-具有10個葉結(jié)點(diǎn)的二叉樹中有（）個度為2的 的結(jié)點(diǎn)數(shù)n2，結(jié)點(diǎn)總數(shù)n=n0+n1+n2分支數(shù)：n1n1+2n2+1=n=n0+n1+得：n0n2一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ C．11至1025之 D．10至1024之 B．2h- 對于有n個結(jié)點(diǎn)的二叉樹,其高度為（ D．不確n個結(jié)點(diǎn)的完全二叉樹的樹高度（深度）（ C． D．log2n-一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（C C．11至1025之 D．10至1024之二叉樹最少有(B) B．2h- 對于有n個結(jié)點(diǎn)的二叉樹,其高度為（ D．不確（ C． D．log2n- 滿二叉樹最矮：210–1最長單支二叉樹，每層一個結(jié)點(diǎn)，1025面僅包含2個結(jié)點(diǎn)，因此結(jié)點(diǎn)總數(shù)=2h-2k-1-1n≤2k-1，有k-1≤log2nk，k是整數(shù)，有k=log2n+242458 滿 B．FEDCBA C．CBEDF 二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷HFIEJKG。該二叉樹根的右子樹的根是（）。A、 B、 C、 D、二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷HFIEJKG。該二叉樹根的右子樹的根是（C）。A、 B、 C、 D、化后，其中空的鏈域的個數(shù)是：(B)。A. B. C D結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為(C)。X的雙親B.X的右子樹中最左的點(diǎn)CX的左子樹中最右結(jié)點(diǎn)DX的左子設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點(diǎn)B的根為p,p的右子樹結(jié)點(diǎn)個數(shù)為n,森林中第一棵樹的結(jié)點(diǎn)個數(shù)是（ 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點(diǎn)B的根為p,p的右子樹結(jié)點(diǎn)個數(shù)為n,森林中第一棵樹的結(jié)點(diǎn)個數(shù)是（A 個數(shù)是（）。 個數(shù)是（D）。 空的結(jié)點(diǎn)有（）個。n- C． D．mn綜合可得：設(shè)給定權(quán)值總數(shù)有n個，其樹的結(jié)點(diǎn)總數(shù)為(D) 與先序遍歷算法比較一下例1求二叉樹的葉子結(jié)點(diǎn)個數(shù)的算法與先序遍歷算法比較一下結(jié)果：二叉樹的葉子結(jié)點(diǎn)個voidleaf(structBiTNode//采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹的葉子結(jié)點(diǎn)的個數(shù)//算法在先序遍歷二叉樹的過程中，統(tǒng)計葉子結(jié)點(diǎn)的個數(shù),第一次被調(diào)用時if(root->lchild=NULL&&root->rchild=NULL)n=n+1;//若root所指結(jié)點(diǎn)為葉子,則累加AA}}

B∧B∧∧C∧E∧∧F∧例2輸出二叉樹中voidPreOrder(structBiTNode//先序遍歷輸出二叉樹中的葉子結(jié)點(diǎn),root為指向二叉樹根結(jié)點(diǎn)的指{if(root!ifrootLChild==NULL&&root>RChild==NULL)printf(root->data); //輸出葉子結(jié)點(diǎn)PreOrder(root->LChild);//先序遍歷左子樹PreOrder(root->RChild);//先序遍歷右子樹}}例2輸出二叉樹中的雙孩子結(jié)點(diǎn)數(shù)voiddouble(structBiTNode//root為指向二叉樹根結(jié)點(diǎn)的指{intnum1,num2;intn=0；if(root!=NULL){if(root->LChild!=NULL&&root- double(rootLChild先序遍歷左子double(root->RChild先序遍歷右子}}例3叉樹高二叉樹的高度(深度)為二叉樹中結(jié)點(diǎn)層次的最大值。設(shè)根結(jié)點(diǎn)為第1層的結(jié)點(diǎn)，所有h層的結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)在1層，則可以通過遍歷計算二叉樹中每個結(jié)點(diǎn)的層次，其中最大值即為二叉樹的高度。voidBiTreeDepth(BiTreeT,intlevel,int{T指向二叉樹的根，levelT所指結(jié)點(diǎn)所在層次//其初值為1，depth為當(dāng)前求得的最大層次,其初值為if{if(level>depth)depth=level;BiTreeDepth(T->Lchild,level+1,depth);BiTreeDepth(T->Rchild,level+1,depth);}}//主函數(shù)中求二叉樹root的深度的語句為Flash演求指定結(jié)點(diǎn)的層voidfindlevel(BiTreeT,p,intlevel,int{T指向二叉樹的根，p待找結(jié)點(diǎn)，h待找p結(jié)點(diǎn)的層if(T==null)elseif(p==T->data)h=lh;

findlevel(T->Lchild,p,level+1,h);findlevel(T->Rchild,p,level+1,h);}Flash演試編寫一個判斷任意給定的二叉樹是否為類滿二叉樹（其任何結(jié)點(diǎn)或為葉子，或者有左、右兩顆非空子樹）的遞歸函數(shù)，并把它轉(zhuǎn)化為非歸函數(shù)遞歸定義f(b 若b->leftnull且b->rightf(b 若b->left,b->right之一為null，另一不為f(bf(b->left&&f(b->right 若b->leftnullb->rightintfull(btree{if(b->left=null&&b->right=returnelseif(b->left=null||b->right=elsereturn(full(b->left)&&full(b-}intfull1(btree{btreeinttop=1;ftree=if{while(top{if(p->left==null&&b->right!=null)||(p->left!=null&&b->right==ftree=elseif(p->left!=nu