线索二叉树,利用无左右孩子的指针域存入前趋/后继关系,没想明白。 5C

依书中的意思,有部分结点没有左(右)孩子,此时它的指针域被浪费了,所以在这些空 的指针域中存入“线索”。重点来了:书上说,线索二叉树,就是把一颗二叉树转变成一个双向链表,我对这句有疑问。双向链表的每个结点的前驱后继都是很清楚的,如果二叉树当中,只有一个空闲的指针域,比如只有结点E的lchild是空闲的。此时在E的lchild存入一个线索,貌似做不到充分展示整个双向链表吧?只能指明E的前驱或是后继。其他的都不是空闲的,怎样存入线索呢,无法存入线索,怎么展示出整个双向链表的前趋后继关系呢?

2个回答

lchild ltag data rtag
rchild
其中:ltag=0 时lchild指向左子女;
ltag=1 时lchild指向前驱;
rtag=0 时rchild指向右子女;
rtag=1 时rchild指向后继;

    二叉树的线索化指的是依照某种遍历次序使二叉树成为线索二叉树的过程。
线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程。
仿照线性表的存储结构,在二叉树的线索链表上也添加一个头结点head,头结点的指针域的安排是:

◆ Lchild域:指向二叉树的根结点;
◆ Rchild域:指向中序遍历时的最后一个结点;
◆ 二叉树中序序列中的第一个结点Lchild指针域和最后一个结点Rchild指针域均指向头结点head。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐