数据结构考研分类复习真题 第六章 答案 (五)[38]

[题目分析]在线索二叉树上插入结点破坏了与被插入结点的线索因此插入结点时必须修复线索在结点y的右侧插入结点x因为是后序线索树要区分结点y有无左子树的情况

void TreeInsert(BiTree tyx)//在二叉树t的结点y的右侧插入结点x

{if(y>ltag==) //y有左子女

{p=y>lchild; if (p>rtag==) p>rchild=x; //x是y的左子女的后序后继

x>ltag=; x>lchild=p; //x的左线索是y的左子女

}

else //y无左子女

{x>ltag=; x>lchild=y>lchild;//y的左线索成为x的左线索

if(y>lchild>rtag==) //若y的后序前驱的右标记为

y>lchild>rchild=x; //则将y的后序前驱的后继改为x

}

x>rtag=; x>rchild=y; y>rtag=; y>rchild=x; //x作y的右子树

}//结束 TreeInsert

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []