数据结构之线索二叉树

~

基本概念　　用五个标志域来存储结点的结构  　　以这种结点结构构成的二叉链表作为二叉树的存储结构叫做线索链表（Threaded Linked Lists） 　　线索 指向结点前驱和后继的指针 　　线索二叉树（Threaded Binary Tree） 加上线索的二叉树 　　线索化 对二叉树以某种次序遍历使其变为线索二叉树的过程 在结构示意图中 指针用实线表示 线索通常用虚线表示 　　线索二叉树的存储结构 二叉树按中序线索化的算法  线索二叉树上常用运算

　　查找某结点*p在指定次序下的前趋和后继结点 　　在中序线索二叉树中 查找指定结点*p的中序后继结点和中序前趋结点 　　1 若结点*p的左子树（或右子树）非空 则*p的中序前趋（或中序后继）是从*p的左孩子（或右孩子）开始往下查找 由于二叉链表中结点的链域是向下链接的 所以在非线索二叉树中亦同样容易找到*p的中序前趋（或中序后继） 　　2 若结点*p的左子树（或右子树）为空 则在中序线索二叉树中是通过*p的左线索（或右线索）直接找到*p的中序前趋（或中序后继） 但中序线索一般都是 向上 指向其祖先结点 而二叉链表中没有向上的链接 因此在这种情况下 对于非线索二叉树 仅从*p出发无法找到其中序前趋（或中序后继） 而必须从根结点开始中序遍历 才能找到*p的中序前趋（或中序后继）

　　在后序线索二叉树中 查找指定结点*p的后序前趋结点 　　1 若*p的左子树为空 同p >lchild是前趋线索 指示其后序前趋结点 　　2 若*p的左子树非空 则p >lchild不是前趋线索 当*p的右子树非空时 *p的右孩子必是其后序前趋

　　在后序线索二叉树中 查找指定结点*p的后序后继结点 　　1 若*p是根 则*p是该二叉树后序遍历过程中最后一个访问到的结点 　　2 若*p是其双亲的右孩子 则*p的后序后继结点就是其双亲结点 　　3 若*p是其双亲的左孩子 但*p无右兄弟时 *p的后序后继结点是其双亲结点 　　4 若*p是其双亲的左孩子 但*p有右兄弟 则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点 它是该子树中 最左下的叶结点

遍历线索二叉树

lishixinzhi/Article/program/sjjg/201311/23149

---

牡丹江市13073066499： 线索二叉树的实现 数据结构 - ？
于克舒脑： 参考一下这个吧...#include <stdio.h>#include <stdlib.h>#define OK 1#define NULL 0 typedef int Status; typedef char TElemType; typedef struct BiTNode //二叉树的二叉链表存储表示 {TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *...

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

牡丹江市13073066499： 线索二叉树 - ？
于克舒脑： 我先说一说 每个 节点 那 五个格 的数据 的含义 中间哪一个 是 存储数据 从左向右 ,第一个 和 第五个 是指针,具体指向什么 取决于第二个 和 第四个的值 第二个 如果是零,实线表示,则 第一个指向的是 左孩子 第二个 如果是1,虚线表示,则 第一个 指向的是 在中序遍历次序下 ,该节点的前驱(即前一个),,如果 该节点 自己就是第一个,没有前驱,,则为空指针 ,,图中最左边 的的C就是这样 (中序遍历 是先访问左孩子,再访问根,再访问右孩子,,图中节点的中根遍历次序为CBDAFHGIE) 第四个为0 ,则第五个指向右孩子 第四个为1.则第五个 指向 中序遍历次序下的后继,,如本身已经是最后一个 没有后继 ,则为空指针

牡丹江市13073066499： 数据结构的线索二叉树,为什么在有n个结点的二叉链表中必定存在n+1个空链域 - ？
于克舒脑：[答案] n个结点的二叉链表中必定存在n+1个空链域 因为n个结点的二叉链表中有2n个孩子指针,而n个结点除根结点外,均有一个指针指向它,所以2n-(n-1)=n+1个指针是空的

牡丹江市13073066499： 数据结构,关于线索二叉树 - ？
于克舒脑： 应该说线索既是一种逻辑也是一种存储,从概念而言,一般指用二叉链表多余的n + 1个指针域来存放二叉树遍历中结点前驱和后继位置,因此答案是b A不全面,C物理结构就是存储结构,这个不全面,d用的线性结构扯得太远

牡丹江市13073066499： 数据结构 二叉树 - ？
于克舒脑： 先介绍一下树:1.树的定义 树是一种常见的非线性的数据结构.树的递归定义如下: 树是n(n>0)个结点的有限集,这个集合满足以下条件: ⑴有且仅有一个结点没有前件(父亲结点),该结点称为树的根; ⑵除根外,其余的每个结点都有且仅...

牡丹江市13073066499： 线索二叉树的特点是什么 - ？
于克舒脑： 不知道是否你要的答案二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继).对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍历中得到. 线索二叉树的优点是便于在中序下查找前驱结点和后继结点.

牡丹江市13073066499： 二叉树线索化的思想是什么? - ？
于克舒脑： 线索二叉树就是 使用的对象:树节点中没有使用的n-1个空指针(n个树节点,空指针永远都是n+1个,自己推下). 运行的原则:某种深度遍历顺序——先序,中序,后序 过程:按照中序(当然也可以是其他的遍历)的前驱后继关系,若p的左...

牡丹江市13073066499： 数据结构中什么是二叉树？
于克舒脑： 树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.满二叉树,完全二叉树,排序二叉树.

牡丹江市13073066499： 数据结构二叉树 - ？
于克舒脑： 二叉树的定义:二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成.(在某个阶段都是两种结果的情形) 二叉树的特点有:*每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点.*左子树和右子树是有顺序的,次序不能任意颠倒.*即使树中某结点只有一棵子树,也要区分它是左子树还是右子树.二叉树具有五种基本形态:1.空二叉树.2.只有一个根结点.3.根结点只有左子树.4.根结点只有右子树.5.根结点既有左子树又有右子树.