首页 > 代码库 > 数据结构 线索二叉树 原理及实现
数据结构 线索二叉树 原理及实现
通过考察各种二叉链表,不管儿叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,n各结点的二叉链表共有2n个链域,非空链域为n-1个,但其中的空链域却有n+1个。如下图所示。
因此,提出了一种方法,利用原来的空链域存放指针,指向树中其他结点。这种指针称为线索。
记ptr指向二叉链表中的一个结点,以下是建立线索的规则:
(1)如果ptr->lchild为空,则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱;
(2)如果ptr->rchild为空,则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继;
显然,在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继,需要一个区分标志的。因此,我们在每个结点再增设两个标志域ltag和rtag,注意ltag和rtag只是区分0或1数字的布尔型变量,其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。
其中:
(1)ltag为0时指向该结点的左孩子,为1时指向该结点的前驱;
(2)rtag为0时指向该结点的右孩子,为1时指向该结点的后继;
(3)因此对于上图的二叉链表图可以修改为下图的养子。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; typedef struct Binode { char data; struct Binode *lchild,*rchild; int ltag,rtag; } Binode,*Bitree; Bitree pre; void CreatTREE(Bitree &T) { char ch; scanf("%c",&ch); if(ch==' ') { T=NULL; } else { T=(Bitree)malloc(sizeof(Binode)); T->data=http://www.mamicode.com/ch;>
数据结构 线索二叉树 原理及实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。