先序前驱线索化示意图

先把二叉树给标记化(把二叉树遍历一遍):既设置两个标记ltag,rtag,如果左孩子指针为空,ltag=1,如果右孩子指针为空,rtag=1. 建一个队列,根据你的遍历方式进行入队, 比如先序遍历,就把visit到的元素依次入队,特别注意,中序遍历或后序遍历visit是从左下角开始的,不是根节点,如果还是不懂,就把输出元素那行改成入队的代码就ok了 然后如果ltag=1,此时把左孩子指针回指队里前一个元素,这个元素就是前驱节点,然后往队尾依次进行线索化,同理,后继的话为rtag=1时,你也应该知道怎么弄了吧.

实线代表二叉树中原有结点的链接,虚线代表遍历序列的线索,左边的是遍历序列前驱的线索,右边的是遍历序列后继的线索先序是abdfjkgcehilm

后序:FDBGHECA

写出对图所示二叉树进行先序、中序、后序遍历的结点序列,并画出该二叉树的先序线索二叉树. 悬赏: 0 答案豆 提问人: 匿名网友 您可能感兴趣的试题 已知一棵二叉树的中序遍历序列为ABCDEFG

一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后,其空链域数为(17).A.0B.1C.2D.不确定 A.0 B.1 C.2 D.不确定 请帮忙给出正确答案和分析,谢谢! 悬赏: 0 答案豆 提问人:00****44

虚线就是线索啊,是原来没有孩子时的空指针改为指向遍历序列的前驱后继,其中左边链指向遍历序列前驱,右边链指向遍历序列的后继

因为双亲节点指向该叶节点啊,你要查找叶节点,就是要找一个指向它的指针域 是,叶子节点指向前驱后继,但是前驱后继的左右孩子域并不指向叶子节点啊,

第一节结点(根节点)没有前驱 ,后继结点 先序遍历 是左子树,中序遍历是右子树,后序遍历没有.最后一个结点,前驱 先序是左子树,等等

(1)线索用的是left或right的空指针.(2)left指向前驱,right指向后继.(3)给你一棵树,画中序线索,先把中序遍历结果写出来.(4)逐个检查遍历结果的数据元素对应的结点,有left空指针,则画线索到前驱结点上,right空指针同理.