1、精選優質文檔-傾情為你奉上1996設t為一棵二叉樹的根結點地址指針，試設計一個非遞歸算法完成把二叉樹中每個結點的左右孩子位置交換。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個結點的二叉排序樹，同時又是一棵完全二叉樹存于向量t中，試設計刪除樹中序號為i且具有左右孩子的一個結點，而不使存儲量增加保證仍為二叉排序樹（不

3、一定是完全二叉樹）的算法。/存數據的位置是從1的索引開始的，避免需要訪問索引為0的空間，避免需要頻繁的索引轉換void delNodeInSortedBiTree(int *sorted_bitree, int *last_index,int i) /因為題目中描述具有左右孩子，所以直接從左孩子的最右邊葉子節點開始 /分兩種情況，左孩子沒有右孩子，那么左孩子之后的節點都移動一個位子 /左孩子存在右孩子，則從右孩子的左孩子一直走，到葉子節點停止，因為是葉子節點 /就不需要移動元素了 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) /后面的位置都往上移動 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 /移動到左

5、孩子的右孩子 del_node_index = del_node_index*2 + 1; while (2*del_node_index <= *last_index) del_node_index *= 2; /因為葉子節點，所以不需要移動 printf("r:%d rp:%dn", sorted_bitreei, sorted_bitreedel_node_index); sorted_bitree0 = sorted_bitreedel_node_index; sorted_bitreedel_node_index = -1; 2002對以二叉鏈表存儲的非空二

6、叉樹，從右向左依次釋放所有葉子結點，釋放的同時，把結點值存放到一個向量中。 要求：（1）用文字寫出實現上述過程的基本思想.（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設二叉排序樹已經以

7、二叉鏈表的形式存儲在內存中，使用遞歸方法，求各結點的平衡因子并輸出。要求： (1)用文字寫出實現上述過程的基本思想。 (2)寫出算法*/(1)分別求出左子樹與右子樹的深度，二者之差即為該結點的平衡因子。(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;/遞歸求二叉樹每個結點的平衡因子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);/輸出各節點的平衡因子 2003三、給出中 序線索二叉樹的結點結構，試編寫在不使用棧和遞歸的情況下先序編歷中序線索二叉樹的算法。*/ 不懂！void InTraveseThr(BitTree thrt) /遍歷中序線索二叉

9、樹 p = thrt->lchild; /p指二叉樹根結點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設二叉樹中結點的數據域的值互不相同，試設計一個算法將數據域值為X的結點的所有祖先結點的數據域打印出來。

10、/算法采用前序遍歷的遞歸算法，在典型的遍歷算法的參數表中增加了x，path，level。X代表要找的值；path記錄從根到含有x節點的路徑上所有的祖先節點，容量為maxsize，已經由#define聲明；level傳遞當前訪問節點的層次，初始值為1，用n來記錄祖先節點的個數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 設二叉樹二叉鏈表為存儲結構，編寫計算二叉樹tree中所有節點的平衡因子，同時返回二叉樹tree中非葉結點個數的算法與2002年一樣，只是加上非葉結點個數。2007設有n個結點的平衡二叉樹的每個結點都標明了平衡因子b,設計結點存儲結構，并編寫求平衡二叉樹的高度的算法/結點存儲結構為typedef struct BTNodeint data;/頂點信息int bf;/頂點的平衡因子 struct BTNode

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

13、遞歸遍歷框架來解此題，即對當前樹的左子樹進行交換，再對右子樹進行交換，最后交換整棵樹（從底部到上面）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指針指向的二叉樹的左右子樹進行互換。BTree *r;/定義一個指針，用來交換左右子樹if(p != N

14、ULL)/交換p結點的左右孩子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;指向樹的指針需要進行替換，或者用引用型void Exchange(BTree *s)/將s指針指向的二叉樹的左右子樹進行互換。BTree *r;if(s != NULL)/交換p結點的左右孩子r= s->lc;s->lc = s->rc;s->r

15、c = r;Exchange(s->lc);Exchange(s->rc);2009已知一棵二叉樹的前序序列和中序序列分別存于兩個一維數組中，試編寫算法建立該二叉樹的二叉鏈表。*/typedef char TElemType;typedef struct BiTNode TElemType data; BiTNode *lchild, *rchild; BiTNode, *BiTree; /* 當前要建立的子樹bt的元素總數為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; /找出中序序列的中點 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假設一個僅包含二元運算符的算術表達式以二叉鏈表形式存儲在二叉樹T中，編寫按后序遍歷計算表達式值的算法2011二叉樹采用二叉鏈表作為存儲結構。編寫算法，求出二叉樹中第i層和第i+1層葉子結點個數之和2016 求二叉樹中指定節點所在的層數2017編寫算法，對一棵一孩子-兄弟鏈表表示的樹的度 typedef struct TreeNodeTreeNode *child;TreeNode *sibling;int data;TreeNode;/這是用了遞歸的思想，需要仔細體

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