if (p->Rtag==link) //右链域为指针，则转右于树，继续右于树前序遍历 p=p->rchild; } }
算法时间复杂度为O(n)。
7．以二叉链表为存储结构，写出交换各结点左右子树的算法。
【解答】要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。算法如下：
typedef char DataType; //定义DaTaType类型 typedef struct node { DataType data;
struct node lchild，rchild; //左右孩子子树 } BinNode; //结点类型 typedef BinNode *BinTree; #include
void ChangeBinTee (BinTree *T) //交换子树
{ if(*T) //这里以指针为参数使交换在实参的结点上进行 {
BinTreetemp; //后序遍历 ChangeBinTree(＆(*T) ->lchild); ChangeBinTree(＆(*T) ->rchlld); temp= (*T) ->lchild;
(*T) ->lchild= (*T) ->rchild; (*T) ->rchild=temp; } }
void PrintNode (BinTree T) //以前序序列打印结点数据 { if (T) {
Printf(¨%C\ PrintNode (T->lchild); PrintNode( T->rchiid); }
16 / 17
}
void main() //测试程序 { BinTree root;
CreatBinTree( &root); //建立二叉链表 PrintNode (root); //输出原表 printf( \
ChangeBinTree( &root); //交换子树 PrintNode (root); //输出新表 printf(\＼n\ }
17 / 17
数据结构课后习题标准答案第六章
