东北大学计算机初试历年二叉树算法题目及解答

[1996]设t为一棵二叉树的根结点地址指针，试设计一个非递归算法完成把二叉树中每个结点的左右孩子位置交换。intswithLRChild(BiTree*t){BiTree*stack[100]={0};intstack_length=0;if(NULL==t){return0;}stack[stack_length++]=t;while(stack_length0){//popstackBiTree*node=stack[stack_length-1];stack_length-=1;BiTree*temp=node-lchild;node-lchild=node-rchild;node-rchild=temp;if(NULL!=node-rchild){stack[stack_length++]=node-rchild;}if(NULL!=node-lchild){stack[stack_length++]=node-lchild;}}return1;}[1998]一棵高度为K且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t中，试设计删除树中序号为i且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树（不一定是完全二叉树）的算法。//存数据的位置是从1的索引开始的，避免需要访问索引为0的空间，避免需要频繁的索引转换voiddelNodeInSortedBiTree(int*sorted_bitree,int*last_index,inti){//因为题目中描述具有左右孩子，所以直接从左孩子的最右边叶子节点开始//分两种情况，左孩子没有右孩子，那么左孩子之后的节点都移动一个位子//左孩子存在右孩子，则从右孩子的左孩子一直走，到叶子节点停止，因为是叶子节点//就不需要移动元素了intdel_node_index=2*i;if(2*del_node_index+1=*last_index){//左孩子只存在左子树sorted_bitree[i]=sorted_bitree[del_node_index];while(del_node_index*2=*last_index){//后面的位置都往上移动sorted_bitree[del_node_index]=sorted_bitree[2*del_node_index];del_node_index*=2;}sorted_bitree[del_node_index]=-1;printf(last_index:%d\n,*last_index);}else{//移动到左孩子的右孩子del_node_index=del_node_index*2+1;while(2*del_node_index=*last_index){del_node_index*=2;}//因为叶子节点，所以不需要移动printf(r:%drp:%d\n,sorted_bitree[i],sorted_bitree[del_node_index]);sorted_bitree[0]=sorted_bitree[del_node_index];sorted_bitree[del_node_index]=-1;}}[2002]对以二叉链表存储的非空二叉树，从右向左依次释放所有叶子结点，释放的同时，把结点值存放到一个向量中。要求：（1）用文字写出实现上述过程的基本思想.（2）写出算法*/keyTypeXL[MAX];IntiTmp=0;voidAni_PreTravel(BiTree&T){if(T){if((T-lchild==NULL)&&(T-rchild==NULL)){XL[iTmp++]==T-data;free(T);T=NULL;}else{Ani_PreTravel(T-rchild);Ani_PreTravel(T-lchild);}}}[2002]设二叉排序树已经以二叉链表的形式存储在内存中，使用递归方法，求各结点的平衡因子并输出。要求：(1)用文字写出实现上述过程的基本思想。(2)写出算法*/(1)分别求出左子树与右子树的深度，二者之差即为该结点的平衡因子。(2)//递归求二叉树的深度intDepth(_PNodepNode){if(NULL!=pNode){intld=Depth(pNode-left);intrd=Depth(pNode-right);returnldrd?ld+1:rd+1;}return0;}//递归求二叉树每个结点的平衡因子voidBalance(_PNodepNode){if(NULL!=pNode){Balance(pNode-left);Balance(pNode-right);inthl=Depth(pNode-left);inthr=Depth(pNode-right);pNode-bf=hl-hr;print(pNode-bf);//输出各节点的平衡因子}}[2003]三、给出中序线索二叉树的结点结构，试编写在不使用栈和递归的情况下先序编历中序线索二叉树的算法。*/不懂！！！！！！！！！！！！！！voidInTraveseThr(BitTreethrt){//遍历中序线索二叉树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);}//whilep=p-rchild;}//while}//InTraversethr[2005]设二叉树中结点的数据域的值互不相同，试设计一个算法将数据域值为X的结点的所有祖先结点的数据域打印出来。//算法采用前序遍历的递归算法，在典型的遍历算法的参数表中增加了x，path[]，level。X代表要找的值；path[]记录从根到含有x节点的路径上所有的祖先节点，容量为maxsize，已经由#define声明；level传递当前访问节点的层次，初始值为1，用n来记录祖先节点的个数intfindAncestors(BTNode*t,charx,charpath[],intlevel,int&n){if(t!=NULL){path[level-1]=t-data;if(t-data==x){n=level;return1;}if(findAncestors(t-lchild,x,path,level+1,n)){return1;}returnfindAncestors(t-rchild,x,path,level+1,n);}else{return0;}}[2006]设二叉树二叉链表为存储结构，编写计算二叉树tree中所有节点的平衡因子，同时返回二叉树tree中非叶结点个数的算法与2002年一样，只是加上非叶结点个数。[2007]设有n个结点的平衡二叉树的每个结点都标明了平衡因子b,设计结点存储结构，并编写求平衡二叉树的高度的算法//结点存储结构为typedefstructBTNode{intdata;//顶点信息intbf;//顶点的平衡因子structBTNode*lchild;structBTNode*rchild;};intBalanceDepth(BTNode*bt){intlevel=0;//代表节点层数BTNode*p;p=bt;while(p){level+=1;if(p-bf0){//如果当前结点的平衡因子是正数，则说明左子树高p=p-lchild;}else{//如果为负数，说明右子树高，如果为零，则左右子树一样高p=p-rchild;}}returnlevel;//返回该平衡二叉树的高度}[2009]设某二叉树以二叉链表为存储结构，设计算法将二叉树中各结点的左右孩子位置互换。*/方法一:可以用二叉树后序递归遍历框架来解此题，即对当前树的左子树进行交换，再对右子树进行交换，最后交换整棵树（从底部到上面）voidswap(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!=NULL)//交换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;指向树的指针需要进行替换，或者用引用型voidExchange(BTree*s)//将s指针指向的二叉树的左右子树进行互换。{BTree*r;if(s!=NULL)//交换p结点的左右孩子{r=s-lc;s-lc=s-rc;s-rc=r;Exchange(s-lc);Exchange(s-rc);}}[2009]已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。*/typedefcharTElemType;typedefstructBiTNode{TElemTypedata;BiTNode*lchild,*rchild;}BiTNode,*BiTree;/*当前要建立的子树bt的元素总数为n，*//*元素在前序序列pre的起始位置为ps，*//*元素在中序序列ino的起始位置为is*/voidBuildBiTree(BiTree&bt,intps,char*pre,intis,char*ino,intn){inti,in1,count=0;if(n1)return;bt=(BiTree)malloc(sizeof(BiTNode));bt-data=pre[ps];bt-lchild=NULL;bt-rchild=NULL;//找出中序序列的中点for(i=is;ino[i]!=pre[ps];++i)++count;in1=i;BuildBiTree(bt-lchild,ps+1,pre,is,ino,count);BuildBiTree(bt-rchild,ps+count+1,pre,in1+1,ino,n-1-count);}[2010]假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树T中，编写按后序遍历计算表达式值的算法[2011]二叉树采用二叉链表作为存储结构。编写算法，求出二叉树中第i层和第i+1层叶子结点个数之和[2016]求二叉树中指定节点所在的层数[2017]编写算法，对一棵一孩子-兄弟链表表示的树的度typedefstructTreeNode{TreeNode*child;TreeNode*sibling;intdata;}TreeNode;//这是用了递归的思想，需要仔细体会intGetChildeSiblingTreeDegree(TreeNode*root){//如果当前树的根节点没有孩子和兄弟，那么，该树的度就是0if(root-child==NULL&&root-sibling==NULL){return0;}//如果该树只有兄弟，则该树的度就等效于对他的兄弟分支的子树求度elseif(root-sibling!=NULL){returnGetChildeSiblingTreeDegree(root-sibling);}//如果该树只有孩子，那么先求出该根节点的度，然后再对它孩子分支子树求度，两者取较大者，即该树的度elseif(root-