数据结构 线索二叉树 原理及实现

通过考察各种二叉链表,不管儿叉树的形态如何,空链域的个数总是多过非空链域的个数。准确的说,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=ch;
        T->ltag=0;
        T->rtag=0;
        CreatTREE(T->lchild);
        CreatTREE(T->rchild);
    }
    return;
}
void travel_threadtree(Bitree H)     //中序遍历线索树 从头节点开始
{
    Bitree p;
    p=H->lchild;                     //p为二叉树头节点
    while(p!=H)
    {
        while(p->ltag==0)            //有左子树 则 一直往下
            p=p->lchild;
        printf("%c ",p->data);
        while(p->rtag==1&&p->rchild!=H)  //根据它的线索一直往后输出
        {
            p=p->rchild;
            printf("%c ",p->data);
        }
        p=p->rchild;                   //当没有线索时 表示有右子树
    }
    return;
}
void thread(Bitree T)               //线索化
{
    if(T)
    {
        thread(T->lchild);
        if(!T->lchild)
        {
            T->ltag=1;
            T->lchild=pre;
        }
        if(!pre->rchild)
        {
            pre->rtag=1;
            pre->rchild=T;
        }
        pre=T;                    //顺序是左子树 节点 右子树的中序遍历 所有 放这里
        thread(T->rchild);
    }
    return;
}
void threading_(Bitree &H,Bitree T)  //新增头节点
{
    H=(Bitree)malloc(sizeof(Binode));
    H->rchild=H;
    H->rtag=0;
    if(!T)                //二叉树为空
    {
        H->lchild=H;
        H->ltag=0;
    }
    else
    {
        pre=H;
        H->lchild=T;
        H->ltag=0;
        thread(T);
        H->rtag=1;
        H->rchild=pre;   //
        pre->rchild=H;    // 构成循环  以备跳出
    }
    return;
}
int main()
{
    Bitree T,H;
    CreatTREE(T);
    threading_(H,T);
    travel_threadtree(H);
    return 0;
}
时间: 11-14

数据结构 线索二叉树 原理及实现的相关文章

(原)数据结构——线索二叉树

原文地址:http://www.cnblogs.com/Security-Darren/p/4716082.html 转载务必注明出处! 线索二叉树的思想来源于二叉树的存储结构中,存在一些空的指针域,因此是否能够将这些空间利用起来,存储一些关于节点间先后顺序的信息,由此产生了线索二叉树.线索二叉树中,线索反映前驱.后继的关系,而指针则体现左右子树. 以二叉链表为例,线索二叉树存储结构上的特点是添加标识符,表明左右指针域究竟存的是指向前驱和后继的线索,还是指向左右子树的指针: 线索二叉树的优势是一

数据结构 - 线索二叉树

线索树 遍历二叉树是按一定的规则将树中的结点排列成一个线性序列,即是对非线性结构的线性化操作. 如何找到遍历过程中动态得到的每个结点的直接前驱和直接后继(第一个和最后一个除外)?如何保存这些信息? 问:一棵有n个结点的二叉树,有多少个空闲指针域未用? 若一棵二叉树有n个结点,则有n-1条指针连线 , 而n个结点共有2n个指针域(Lchild和Rchild) ,所以有n+1个空闲指针域未用. 可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息. 对结点的指针域做如下规定: ◆ 若结点有左孩

重拾算法(2)——线索二叉树

重拾算法(2)——线索二叉树 上一篇我们实现了二叉树的递归和非递归遍历,并为其复用精心设计了遍历方法Traverse(TraverseOrder order, NodeWorker<T> worker);今天就在此基础上实现线索二叉树. 什么是线索二叉树 二叉树中容易找到结点的左右孩子信息,但该结点在某一序列中的直接前驱和直接后继只能在某种遍历过程中动态获得. 先依遍历规则把每个结点某一序列中对应的前驱和后继线索预存起来,这叫做"线索化". 意义:从任一结点出发都能快速找到

javascript实现数据结构:线索二叉树

遍历二叉树是按一定的规则将树中的结点排列成一个线性序列,即是对非线性结构的线性化操作.如何找到遍历过程中动态得到的每个结点的直接前驱和直接后继(第一个和最后一个除外)?如何保存这些信息? 设一棵二叉树有n个结点,则有n-1条边(指针连线) , 而n个结点共有2n个指针域(Lchild和Rchild) ,显然有n+1个空闲指针域未用.则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息. 对结点的指针域做如下规定: 1.若结点有左子树,则其leftChild域指示其左孩子,否则令leftC

数据结构(三):非线性逻辑结构-特殊的二叉树结构:堆、哈夫曼树、二叉搜索树、平衡二叉搜索树、红黑树、线索二叉树

在上一篇数据结构的博文<数据结构(三):非线性逻辑结构-二叉树>中已经对二叉树的概念.遍历等基本的概念和操作进行了介绍.本篇博文主要介绍几个特殊的二叉树,堆.哈夫曼树.二叉搜索树.平衡二叉搜索树.红黑树.线索二叉树,它们在解决实际问题中有着非常重要的应用.本文主要从概念和一些基本操作上进行分类和总结. 一.概念总揽 (1) 堆 堆(heap order)是一种特殊的表,如果将它看做是一颗完全二叉树的层次序列,那么它具有如下的性质:每个节点的值都不大于其孩子的值,或每个节点的值都不小于其孩子的值

【算法与数据结构】二叉树 中序线索

中序线索二叉树 /************************************************************************ 线索二叉树 二叉树的节点有五部分构造 ----------------------------------------- | lChild | lTag | value | rTag | rChild | ----------------------------------------- lChild = (lTag == 0 ? 左

【数据结构】中序遍历线索二叉树

昨天写了个二叉树遍历,自以为对二叉树很了解了.自大的认为线索二叉树不过是加了点线索而已,不足挂齿.可是当真的自己编程序写的时候才发现完全不是那么容易.在有线索的情况下,如何判别Link类型的下一节点,如何不用栈跳过已访问节点搞得脑子晕晕的. 折腾一个晚上,才根据书上把线索二叉树的建立.中序遍历给写出来.要回去继续好好的理清关系. #include <stdio.h> #include <stdlib.h> typedef enum PointerTag{Link, Thread};

数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)

前言:前面了解了树的概念和基本的存储结构类型及树的分类,而在树中应用最广泛的种类是二叉树 一.简介 在树型结构中,如果每个父节点只有两个子节点,那么这样的树被称为二叉树(Binary tree).其中,一个父结点的两个字节点分别叫做“左子节点”和“右子节点”.不过也不是所有父节点都有两个子节点,只有左子节点或者只有右子节点的情况也存在.另外,也会存在叶子结点,也就是一个子节点都没有的节点,唯一的限制就是每一个节点的子节点不能超过两个. 之前谈过的单向链表,是一种通过“指向下一个元素的指针”来连接

数据结构之---C语言实现线索二叉树

//线索二叉树,这里在二叉树的基础上增加了线索化 //杨鑫 #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef enum {Link,Thread} childTag; //Link表示结点.Thread表示线索 typedef struct bitNode { ElemType data; struct bitNode *lchild, *rchild; int ltag, rtag; } b