数据结构之线索二叉树,线索二叉树

风姿洒脱 什么是头脑二叉树

在有n个结点的二叉链表中必定期存款在n+1个空指针域,因而得以行使那个空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针,这种针对前趋和后继结点的指针称为“线索”,加上线索的二叉链表称为线索链表,相应的二叉树被称之为线索二叉树。

二 为啥要创设线索二叉树

有了二叉树不就丰硕了吗?那干什么还要弄个线索二叉树出来吧?

在原先的二叉链表中,查找结点的左,右孩子能够一贯达成,但是大器晚成旦要找该结点的前趋和后继结点呢?那就变得可怜难堪,所感觉了促成这么些广阔的急需,大家要在各种结点中加进五个指针域来存放遍历时拿到的前趋和后继结点,那样就能够通过该指针直接或间接待上访谈其前趋和后继结点。

三 如何将二叉树线索化

按某种次序遍历二叉树,在遍历进度中用线索取代空指针就可以。

下边是头脑二叉树和线索二叉链表暗中提示图,它可以扶植我们越来越好地精通线索二叉树。

图片 1

 

图片 2

代码如下:

/** 线索二叉树 **/
#include<stdio.h>
#include<stdlib.h>

typedef char ElemType; //数据类型
typedef enum {Link,Thread} childTag; //Link表示结点,Thread表示线索
typedef struct threadBiTree{
    ElemType data;
    struct threadBiTree *lchild,*rchild;
    int ltag,rtag;  //标志位,区分枚举类型中的节点或线索两种取值
}threadBiTree,*ptrThreadBiTree;

/**
 * 创建一颗普通的二叉树
 */
void create_BiTree(ptrThreadBiTree &TNode,char* &str){
    char ch;
    sscanf(str,"%c",&ch);
    str++;
    if(ch == '#'){ //空节点
        TNode = NULL;
    }else{
        TNode = (ptrThreadBiTree)malloc(sizeof(threadBiTree)); 
        TNode->data = ch;
        TNode->ltag = Link;
        TNode->rtag = Link;
        create_BiTree(TNode->lchild,str);
        create_BiTree(TNode->rchild,str);
    }
}

/** 
 * 访问结点信息 
 */  
void visit(ptrThreadBiTree &TNode){
     printf("%d-%c-%dn",TNode->ltag,TNode->data,TNode->rtag);
}

/**
 * 前序遍历访问二叉树
 */ 
void pre_order_traverse(ptrThreadBiTree &TNode,int level){
    if(TNode){
        visit(TNode);
        pre_order_traverse(TNode->lchild,level+1);
        pre_order_traverse(TNode->rchild,level+1);
    }
}

/**
 * 中序线索化二叉树
 */
void in_order_threading(ptrThreadBiTree &preNode,ptrThreadBiTree &root){
    if(root){
       in_order_threading(preNode,root->lchild);
       if(!root->lchild){ //左孩子为空,使其线索指向直接前驱
          root->lchild = preNode;
          root->ltag = Thread;
       }
       if(!preNode->rchild){ //如果上一个结点的右孩子为空,则将其指向直接后继(注意:只有访问到下一个结点时,才会知道本结点的后继是谁)
          preNode->rchild = root;
          preNode->rtag = Thread;
       }
       preNode = root;
       in_order_threading(preNode,root->rchild);
    }
}


/**
 * 加入一个头结点,使二叉线索树成一个封闭环 
 * 带有头结点的二叉树,头结点的左孩子指向二叉树T; 右孩子指向T树中的最后一个叶子结点 
 * 不带有头结点的二叉树 
 */
void in_thread(ptrThreadBiTree &head,ptrThreadBiTree &root){
    head = (ptrThreadBiTree)malloc(sizeof(threadBiTree)); //新增头节点
    head->ltag = Link;
    head->rtag = Thread;
    head->rchild = head; //初始时使其右线索指向自身
    if(!root){ //二叉树为空,使其左孩子指针指向自身
        head->lchild = head;
    }else{
        head->lchild = root;
        ptrThreadBiTree preNode = head; //记录上次访问的结点
        in_order_threading(preNode,root);
        head->rchild = preNode; //将头结点右孩子指向最后一个叶子结点 
        preNode->rtag = Thread;
        preNode->rchild = head; //将最后一个叶子结点的右孩子指向头结点,环路就形成了
    }
}

/**
 * 中序线索二叉树
 */
void mid_order_traverse(ptrThreadBiTree &head){
    ptrThreadBiTree root = head->lchild;
    while(root!=head){ //判断是否空树
        while(root->ltag == Link){
            root = root->lchild;
        }
        visit(root);
        while(root->rtag == Thread && root->rchild!=head){ //根据线索,访问后继结点,并且后继结点不是指向头结点的
            root=root->rchild;  
            visit(root); 
        }
        root=root->rchild;
    }
}

int main(){
    ptrThreadBiTree head,biTree=NULL;
    char *ch = "ab#d##ce###";

    create_BiTree(biTree,ch);
    //printf("前序遍历输出普通二叉树:n");
    //pre_order_traverse(biTree,1);
    //printf("=======================n");

    in_thread(head,biTree);
    printf("中序线索二叉树:n");
    mid_order_traverse(head);

    return 0;
}

运维结果截图:

图片 3

大器晚成什么是头脑二叉树
在有n个结点的二叉链表中一定期存款在n+1个空指针域,因而得以选拔那些空指针域存…

相关文章