以二叉链表为存储结构,写一算法交换各结点的左右子树

Question

如题所述

Answer 1

问题：以二叉链表为存储结构， 写一算法交换各结点的左右子树。

答案：
要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。

void ChangeBinTree(BinTree *T)
{ //交换子树
if(*T)
{ //这里以指针为参数使得交换在实参的结点上进行后序遍历
BinTree temp;
ChangeBinTree(&(*T)->lchild);
ChangeBinTree(&(*T)->rchild);
temp=(*T)->lchild;
(*T)->lchild=(*T)->rchild;
(*T)->rchild=temp;
}
}

Answer 2

递归的方法，节点类型是BiNode
void jiaohuan(BiTREE &L)
{BiNode *p=L;
if(L->lchild!=NULL&&L->rchild!=NULL)
{jiaohuan(L->lchild);
jiaohuan(L->rchild);
p=L->lchild;L->lchild=L->rchild;L->rchild=p;
}
}本回答被提问者和网友采纳