数据结构课后习题标准答案第六章

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