“先序线索化” //递归出错，同样的方式实现中序、后序线索化二叉树却是正确的，代码如下 //先序遍历线索

发布网友 发布时间：2022-05-30 21:57

我来回答

共2个回答

热心网友 时间：2023-11-23 11:50

//给你两个代码 一个错误用于启示 一个正确却需要理解-也就是你的正确改版

//错误版本：
//看下面这个结果与你的相反 而且还要返回最后一个 正确的看下一个改版！！！！
//但你可以从这个错误中得到启示！！！！ 只是顺序相反了罢了 想法改过来就得
ThreadNode* PreOrderThread(ThreadTree bt)
{
static ThreadNode* pre=NULL;
if(bt != NULL) //只有不是NULL才是递归条件啊 没个结点都到这来检测是否为NULL
{
bt->lChild = pre; //bt永远指向pre 这样就构成了线索了 不过这样跟结点在最后罢了
pre = bt; //然后pre也该改变到了新的位置了 如此重复
//上面两句是 根遍历
PreOrderThread(bt->lchild); // 左子树遍历
PreOrderThread(bt->rchild); // 右子树遍历
// 一看就是先序线索了吗？根-左(根左右)-右(根左右)
}
return pre; //返回最后一个线索的结点 也就是最右边的结点 否则怎么知道呢
}

正确改版：
//由于方向相反了 我们就“右-左-根”的遍历 最后一个就是根了 也不用返回了
// 不就一切OK了

void PreOrderThread(ThreadTree bt)
{
static ThreadNode* pre=NULL;
if(bt != NULL) //只有不是NULL才是递归条件啊 没个结点都到这来检测是否为NULL
{
PreOrderThread(bt->rchild); // 右子树遍历
PreOrderThread(bt->lchild); // 左子树遍历
bt->lChild = pre; // 根遍历
pre = bt;
//怎么 没明白 呵呵 拿笔纸上写写看就明白了
//你想啊
//(1)只有根 正确
//(2)2个结点的(有根左或者有根右 两种情况) 都正确吧
//(3)3个结点(有根左右) 正确吧
//(4)现在多于3个结点的 归纳到(1)-(3) 呵呵 可以利用数学上的归纳法证明呀
//哈哈 扯淡到数学去了 反正就是这种简单的做法
}
}

就这么简单 就怕理解不了 而扯淡出一大堆代码 就像我上面的 有返回 费解易错

这和只遍历而不改变树是一个道理的
理解的话
其他的线索化 代码也这么简单 没什么的！！！

热心网友 时间：2023-11-23 11:50

*tb) // 先序线索化二叉树先序实现先序遍历
{
TBTNode *p = tb;
TBTNode *q;
while(p != tb) //就是这个地方有错误~~
{