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

[1996]设t为一棵二叉树的根结点地址指针，试设计一个非递归算法完成把二叉树中每个结

点的左右孩子位置交换。

intswithLRChild(BiTree*t)

{BiTree*stack[100]={0};

intstack_length=0;

if(NULL==t){

return0;

}

stack[stack_length++]=t;

while(stack_length0){

//popstack

BiTree*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;

}

else

{

//移动到左孩子的右孩子

del_node_index=del_node_index*2+1;

while(2*del_node_index=*last_index)

{

del_node_index*=2;

}

//因为叶子节点，所以不需要移动

sorted_bitree[0]=sorted_bitree[del_node_index];

sorted_bitree[del_node_index]=-1;

}

}

[2002]对以二叉链表存储的非空二叉树，从右向左依次释放所有叶子结点，释放的同时，

把结点值存放到一个向量中。

要求：（1）用文字写出实现上述过程的基本思想.（2）写出算法*/

keyTypeXL[MAX];

IntiTmp=0;

voidAni_PreTravel(BiTreeT