東北大學(xué)計(jì)算機(jī)初試歷年二叉樹算法題目及解答

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1996設(shè)t為一棵二叉樹的根結(jié)點(diǎn)地址指針，試設(shè)計(jì)一個(gè)非遞歸算法完成把二叉樹中每個(gè)結(jié)點(diǎn)的左右孩子位置交換。int swithLRChild(BiTree *t) BiTree *stack100 = 0; int stack_length = 0; if (NULL = t) return 0; stackstack_length+ = t; while (stack_length > 0) /pop stack BiTree *node = stackstack_length - 1; stack_length -= 1; BiTree *temp = node

2、->lchild; node->lchild = node->rchild; node->rchild = temp; if (NULL != node->rchild) stackstack_length+ = node->rchild; if (NULL != node->lchild) stackstack_length+ = node->lchild; return 1; 1998一棵高度為K且有n個(gè)結(jié)點(diǎn)的二叉排序樹，同時(shí)又是一棵完全二叉樹存于向量t中，試設(shè)計(jì)刪除樹中序號為i且具有左右孩子的一個(gè)結(jié)點(diǎn)，而不使存儲量增加保證仍為二叉排序樹（不

3、一定是完全二叉樹）的算法。/存數(shù)據(jù)的位置是從1的索引開始的，避免需要訪問索引為0的空間，避免需要頻繁的索引轉(zhuǎn)換void delNodeInSortedBiTree(int *sorted_bitree, int *last_index,int i) /因?yàn)轭}目中描述具有左右孩子，所以直接從左孩子的最右邊葉子節(jié)點(diǎn)開始 /分兩種情況，左孩子沒有右孩子，那么左孩子之后的節(jié)點(diǎn)都移動(dòng)一個(gè)位子 /左孩子存在右孩子，則從右孩子的左孩子一直走，到葉子節(jié)點(diǎn)停止，因?yàn)槭侨~子節(jié)點(diǎn) /就不需要移動(dòng)元素了 int del_node_index = 2*i; if (2*del_node_index + 1 >=

4、*last_index) /左孩子只存在左子樹 sorted_bitreei = sorted_bitreedel_node_index; while (del_node_index*2 <= *last_index) /后面的位置都往上移動(dòng) sorted_bitreedel_node_index = sorted_bitree2*del_node_index; del_node_index *= 2; sorted_bitreedel_node_index = -1; printf("last_index:%dn", *last_index); else /移動(dòng)到左

5、孩子的右孩子 del_node_index = del_node_index*2 + 1; while (2*del_node_index <= *last_index) del_node_index *= 2; /因?yàn)槿~子節(jié)點(diǎn)，所以不需要移動(dòng) printf("r:%d rp:%dn", sorted_bitreei, sorted_bitreedel_node_index); sorted_bitree0 = sorted_bitreedel_node_index; sorted_bitreedel_node_index = -1; 2002對以二叉鏈表存儲的非空二

6、叉樹，從右向左依次釋放所有葉子結(jié)點(diǎn)，釋放的同時(shí)，把結(jié)點(diǎn)值存放到一個(gè)向量中。 要求：（1）用文字寫出實(shí)現(xiàn)上述過程的基本思想.（2）寫出算法*/keyType XLMAX;Int iTmp=0;void Ani_PreTravel(BiTree &T)if(T)if(T->lchild = NULL) && (T->rchild = NULL)XLiTmp+ = T->data;free(T);T = NULL;elseAni_PreTravel(T->rchild);Ani_PreTravel(T->lchild);2002設(shè)二叉排序樹已經(jīng)以

7、二叉鏈表的形式存儲在內(nèi)存中，使用遞歸方法，求各結(jié)點(diǎn)的平衡因子并輸出。要求： (1)用文字寫出實(shí)現(xiàn)上述過程的基本思想。 (2)寫出算法*/(1)分別求出左子樹與右子樹的深度，二者之差即為該結(jié)點(diǎn)的平衡因子。(2)/遞歸求二叉樹的深度int Depth(_PNode pNode) if (NULL != pNode) int ld = Depth(pNode->left); int rd = Depth(pNode->right); return ld > rd ? ld + 1: rd + 1; return 0;/遞歸求二叉樹每個(gè)結(jié)點(diǎn)的平衡因子void Balance(_PNo

8、de pNode) if (NULL != pNode) Balance(pNode->left); Balance(pNode->right); int hl = Depth(pNode->left); int hr = Depth(pNode->right); pNode->bf = hl - hr; print(pNode->bf);/輸出各節(jié)點(diǎn)的平衡因子 2003三、給出中 序線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)，試編寫在不使用棧和遞歸的情況下先序編歷中序線索二叉樹的算法。*/ 不懂！void InTraveseThr(BitTree thrt) /遍歷中序線索二叉

9、樹 p = thrt->lchild; /p指二叉樹根結(jié)點(diǎn)while (p!=thrt) while(p->Ltag = 0) p = p->lchild; printf(p->data); while(p->rtag = 1 && p->rchild != thrt) p = p->rchild; printf(p->data); /while p = p->rchild; /while/InTraversethr2005設(shè)二叉樹中結(jié)點(diǎn)的數(shù)據(jù)域的值互不相同，試設(shè)計(jì)一個(gè)算法將數(shù)據(jù)域值為X的結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的數(shù)據(jù)域打印出來。

10、/算法采用前序遍歷的遞歸算法，在典型的遍歷算法的參數(shù)表中增加了x，path，level。X代表要找的值；path記錄從根到含有x節(jié)點(diǎn)的路徑上所有的祖先節(jié)點(diǎn)，容量為maxsize，已經(jīng)由#define聲明；level傳遞當(dāng)前訪問節(jié)點(diǎn)的層次，初始值為1，用n來記錄祖先節(jié)點(diǎn)的個(gè)數(shù)int findAncestors(BTNode *t,char x,char path,int level,int &n)if(t!=NULL)pathlevel-1=t->data;if(t->data=x)n=level;return 1;if(findAncestors(t->lchild,

11、x,path,level+1,n)return 1;return findAncestors(t->rchild,x,path,level+1,n);elsereturn 0;2006 設(shè)二叉樹二叉鏈表為存儲結(jié)構(gòu)，編寫計(jì)算二叉樹tree中所有節(jié)點(diǎn)的平衡因子，同時(shí)返回二叉樹tree中非葉結(jié)點(diǎn)個(gè)數(shù)的算法與2002年一樣，只是加上非葉結(jié)點(diǎn)個(gè)數(shù)。2007設(shè)有n個(gè)結(jié)點(diǎn)的平衡二叉樹的每個(gè)結(jié)點(diǎn)都標(biāo)明了平衡因子b,設(shè)計(jì)結(jié)點(diǎn)存儲結(jié)構(gòu)，并編寫求平衡二叉樹的高度的算法/結(jié)點(diǎn)存儲結(jié)構(gòu)為typedef struct BTNodeint data;/頂點(diǎn)信息int bf;/頂點(diǎn)的平衡因子 struct BTNode

12、 *lchild;struct BTNode *rchild; ; int BalanceDepth(BTNode *bt)int level=0;/代表節(jié)點(diǎn)層數(shù)BTNode *p;p=bt;while(p)level+=1;if(p->bf>0)/如果當(dāng)前結(jié)點(diǎn)的平衡因子是正數(shù)，則說明左子樹高 p=p->lchild; else/如果為負(fù)數(shù)，說明右子樹高，如果為零，則左右子樹一樣高 p=p->rchild; return level;/返回該平衡二叉樹的高度 2009設(shè)某二叉樹以二叉鏈表為存儲結(jié)構(gòu)，設(shè)計(jì)算法將二叉樹中各結(jié)點(diǎn)的左右孩子位置互換。*/方法一:可以用二叉樹后序

13、遞歸遍歷框架來解此題，即對當(dāng)前樹的左子樹進(jìn)行交換，再對右子樹進(jìn)行交換，最后交換整棵樹（從底部到上面）void swap(BTNode *bt)if(b!=NULL)swap(b->lchild);swap(b->rchild);BTNode *temp=b->lchild;b->lchild=b->rchild;b->rchild=temp; 方法二：先序遍歷/這種通過返回樹的方式，比較簡便，可以借鑒BTree *Exchange(BTree *p)/將p指針指向的二叉樹的左右子樹進(jìn)行互換。BTree *r;/定義一個(gè)指針，用來交換左右子樹if(p != N

14、ULL)/交換p結(jié)點(diǎn)的左右孩子k+;r= p->lc;p->lc = p->rc;p->rc = r;p->lc = Exchange(p->lc);p->rc = Exchange(p->rc);return(p);/這種方式，如果指針需要變化，需要在開始用BTree *s=p;指向樹的指針需要進(jìn)行替換，或者用引用型void Exchange(BTree *s)/將s指針指向的二叉樹的左右子樹進(jìn)行互換。BTree *r;if(s != NULL)/交換p結(jié)點(diǎn)的左右孩子r= s->lc;s->lc = s->rc;s->r

15、c = r;Exchange(s->lc);Exchange(s->rc);2009已知一棵二叉樹的前序序列和中序序列分別存于兩個(gè)一維數(shù)組中，試編寫算法建立該二叉樹的二叉鏈表。*/typedef char TElemType;typedef struct BiTNode TElemType data; BiTNode *lchild, *rchild; BiTNode, *BiTree; /* 當(dāng)前要建立的子樹bt的元素總數(shù)為n，*/* 元素在前序序列pre的起始位置為ps，*/* 元素在中序序列ino的起始位置為is */void BuildBiTree(BiTree &

16、bt, int ps, char *pre,int is, char *ino, int n) int i,in1,count = 0; if(n < 1) return; bt = (BiTree)malloc(sizeof(BiTNode); bt->data = preps; bt->lchild = NULL; bt->rchild = NULL; /找出中序序列的中點(diǎn) for(i = is;inoi != preps;+i) +count; in1 = i; BuildBiTree(bt->lchild,ps+1,pre,is,ino,count); B

17、uildBiTree(bt->rchild,ps+count+1,pre,in1+1,ino,n-1-count);2010假設(shè)一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式以二叉鏈表形式存儲在二叉樹T中，編寫按后序遍歷計(jì)算表達(dá)式值的算法2011二叉樹采用二叉鏈表作為存儲結(jié)構(gòu)。編寫算法，求出二叉樹中第i層和第i+1層葉子結(jié)點(diǎn)個(gè)數(shù)之和2016 求二叉樹中指定節(jié)點(diǎn)所在的層數(shù)2017編寫算法，對一棵一孩子-兄弟鏈表表示的樹的度 typedef struct TreeNodeTreeNode *child;TreeNode *sibling;int data;TreeNode;/這是用了遞歸的思想，需要仔細(xì)體

18、會int GetChildeSiblingTreeDegree(TreeNode *root)/如果當(dāng)前樹的根節(jié)點(diǎn)沒有孩子和兄弟，那么，該樹的度就是0if (root->child = NULL && root->sibling = NULL)return 0;/如果該樹只有兄弟，則該樹的度就等效于對他的兄弟分支的子樹求度else if( root->sibling != NULL)return GetChildeSiblingTreeDegree(root->sibling);/如果該樹只有孩子，那么先求出該根節(jié)點(diǎn)的度，然后再對它孩子分支子樹求度，兩者取較大者，即該