请在Chrome、Firefox等现代浏览器浏览本站。

线索二叉树的创立及遍历(C言语完成)

经过前面对二叉树的进修,了解到二叉树自身是一种非线性结构,采取任何一种遍历二叉树的方法,都可以掉掉落树中一切结点的一个线性序列。在这个序列中,除第一个结点外,每个

  经过前面对二叉树的进修,了解到二叉树自身是一种非线性结构,采取任何一种遍历二叉树的方法,都可以掉掉落树中一切结点的一个线性序列。在这个序列中,除第一个结点外,每个结点都有自己的直接前趋;除最后一个结点外,每个结点都有一个直接后继。

  

  图1 满二叉树

  例如,图 1 采取先序遍历的方法掉掉落的结点序列为:,在这个序列中,结点 2 的直接前趋结点为 1,直接后继结点为 4。

  假设算法中屡次触及到对二叉树的遍历,通俗的二叉树就需求应用栈结构做重复性的操作。

  线索二叉树不需求如此,在遍历的同时,应用二叉树中闲暇的内存空间记录某些结点的前趋和后继元素的位置(不是全部)。如许在算法前期需求遍历二叉树时,便可以应用保管的结点信息,提高了遍历的效力。应用这类方法构建的二叉树,即为“线索二叉树”。

  假设在二叉树中想保管每个结点前趋和后继地点的位置信息,最直接的想法主意就是修改结点的结构,即添加两个指针域,辨别指向该结点的前趋和后继。

  然则这类方法会降低树存储结构的存储密度。而关于二叉树来讲,其自身还有很多未应用的空间。

  每棵二叉树上,很多结点都含有未应用的指向NULL的指针域。除度为2的结点,度为 1 的结点,有一个空的指针域;叶子结点两个指针域都为NULL。

  规律:在有 n 个结点的二叉链表中肯定存在 n+1 个空指针域。

  线索二叉树实践上就是应用这些空指针域来存储结点之间前趋和后继关系的一种特别的二叉树。

  线索二叉树中,假设结点有左子树,则 lchild 指针域指向左孩子,否则 lchild 指针域指向该结点的直接前趋;异样,假设结点有右子树,则 rchild 指针域指向右孩子,否则 rchild 指针域指向该结点的直接后继。

  为了防止指针域指向的结点的意义混淆,需求修改结点自身的结构,添加两个标记域,如图 2 所示。

  

  图2 线索二叉树中的结点结构

  LTag 和 RTag 为标记域。实践上就是两个布尔类型的变量:

  LTag 值为 0 时,表现 lchild 指针域指向的是该结点的左孩子;为 1 时,表现指向的是该结点的直接前趋结点;

  RTag 值为 0 时,表现 rchild 指针域指向的是该结点的右孩子;为 1 时,表现指向的是该结点的直接后继结点。

  结点结构代码完成:

喜欢 (0) or 分享 (0)
发表我的评论
取消评论

表情

您的回复是我们的动力!

  • 昵称 (必填)

网友最新评论