线索二叉树

~

线索二叉树概念

．定义 　　n个结点的二叉链表中含有n+ 个空指针域 利用二叉链表中的空指针域 存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为 线索 ） 　　这种加上了线索的二叉链表称为线索链表 相应的二叉树称为线索二叉树(Threaded   BinaryTree) 根据线索性质的不同 线索二叉树可分为前序线索二叉树 中序线索二叉树和后序线索二叉树三种 　 注意 　　线索链表解决了二叉链表找左 右孩子困难的问题 出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题

．线索链表的结点结构 　　线索链表中的结点结构为

 　其中:　　ltag和rtag是增加的两个标志域 用来区分结点的左 右指针域是指向其左 右孩子的指针 还是指向其前趋或后继的线索

．线索二叉树的表示 　【例】下面(a)图所示的中序线索二叉树 其线索链表如下面(b)图所示

       　 注意 　　图中的实线表示指针 虚线表示线索 　　结点C的左线索为空 表示C是中序序列的开始结点 无前趋 　　结点E的右线索为空 表示E是中序序列的终端结点 无后继 　　线索二叉树中 一个结点是叶结点的充要条件为 左 右标志均是

二叉树的线索化   ．线索化和线索化实质 　　将二叉树变为线索二叉树的过程称为线索化 　　按某种次序将二叉树线索化的实质是 按该次序遍历二叉树 在遍历过程中用线索取代空指针 　　具体过程可【参见动画演示】

．二叉树的中序线索化 （ ）分析 　　算法与中序遍历算法类似 只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索 　　该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL） 而指针p指示当前正在访问的结点 结点*pre是结点*p的前趋 而*p是*pre的后继

（ ）将二叉树按中序线索化的算法   typedef enum { Link Thread} PointerTag //枚举值Link和Thread分别为   typedef struct node{      DataType data       PointerTag ltag rtag //左右标志      Struct node *lchild *rchild     } BinThrNode \\线索二叉树的结点类型  typedef BinThrNode *BinThrTree   BinThrNode *pre=NULL //全局量  void lnorderThreading(BinThrTree p)    {//将二叉树p中序线索化      if(p){ //p非空时 当前访问结点是*p             InorderThreading(p >lchild) //左子树线索化                 //以下直至右子树线索化之前相当于遍历算法中访问结点的操作             p >ltag=(p >lchild)?Link Thread //左指针非空时左标志为Link                                             //(即 ) 否则为Thread(即 )             p >rtag=(p >rchild)?Link Thread              *(pre){ //若*p的前趋*pre存在                   if(pre >rtag==Thread) //若*p的前趋右标志为线索                        pre >rchild=p //令*pre的右线索指向中序后继                  if(p >ltag==Thread) //*p的左标志为线索                       p >lchild=pre //令*p的左线索指向中序前趋                 } // 完成处理*pre的线索             pre=p //令pre是下一访问结点的中序前趋             InorderThreeding(p >rehild) //右子树线索化           }//endif    } //InorderThreading

（ ）算法分析 　　和中序遍历算法一样 递归过程中对每结点仅做一次访问 因此对于n个结点的二叉树 算法的时间复杂度亦为O(n)

lishixinzhi/Article/program/sjjg/201311/22726

---

上饶市15335927023： 线索二叉树 - 搜狗百科？
前邵贯新：[答案] 物理结构 逻辑结构:集合、线性、树和图 物理结构:线性存储和非线性存储 其中,线性存储结构有顺序(sequential)、链接(linked)、索引(indexed)和散列(hashing)4种结构 非线性存储结构有:树形存储结构、图形存储结构.

上饶市15335927023： 数据结构线索二叉树怎么画 已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHKIJD,画出此二叉树,并画出它的后序线索二叉树(... - ？
前邵贯新：[答案] 你求得后序排列应该错了吧应该是FEGKJIHDCBA画法嘛,首先从前序遍历得知根是A,所以从中序遍历中知道左分支是EF,右分支是GBCHKIJD,而前序遍历和中序遍历中E都在F之前,所以F是E的右孩子,所以可得到左分支剩下的是前序BG...

上饶市15335927023： 线索二叉树是一种什么结构? - ？
前邵贯新： 物理结构.包括线性存储和非线性存储其中,线性存储结构有顺序、链接、索引和散列4种结构.非线性存储结构有:树形存储结构、图形存储结构. n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域.利用二叉链表中的空指针域,存放...

上饶市15335927023： 线索二叉树 - ？
前邵贯新： //二叉树的二叉线索存储表示 #include<stdio.h> #include<stdlib.h>typedef enum PointerTagpointerType;//Link==0,指针,Thread==1,线索 typedef char TElemType; typedef struct BiThrNode {TElemType data;struct BiThrNode *lchild,*rchild; ...

上饶市15335927023： 线索二叉树是( )结构?A.逻辑 B逻辑和存储.C.D线性. - ？
前邵贯新：[答案] 应当是存储或者物理结构,因为是在存储结构二叉链表上实现的,并且是如果孩子为空,则就是线索

上饶市15335927023： 数据结构的线索二叉树,为什么在有n个结点的二叉链表中必定存在n+1个空链域 - ？
前邵贯新：[答案] n个结点的二叉链表中必定存在n+1个空链域 因为n个结点的二叉链表中有2n个孩子指针,而n个结点除根结点外,均有一个指针指向它,所以2n-(n-1)=n+1个指针是空的

上饶市15335927023： 在一个具有n个结点的线索二叉树中有多少个指针是用来作为线索处理的? - ？
前邵贯新：[答案] 在一个具有n个结点的线索二叉树中有n+1个指针是用来作为线索处理的 因为n个结点的二叉树中有2n个指针,而这些个结点(除根结点)都有一个指针指向它,这有就n-1个结点被实用,空的指针有n+1个,可用作线索

上饶市15335927023： 请教一道关于线索二叉树的问题 二叉树在线索化后,仍不能有效求解的问题是(D). - ？
前邵贯新：[选项] A. 先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 请问为什么选D啊

上饶市15335927023： 线索二叉树的结构体定义是什么 - ？
前邵贯新： 线索二叉树的结点结构 二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继).对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍...