开发者社区> 孤独的猫董> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

线索二叉树

简介: 线索二叉树-概念          当用二叉链表作为二叉树的存储结构时,因为每个结点中只有指向其左、右儿子结点的指针,所以从任一结点出发只能直接找到该结点的左、右儿子。
+关注继续查看

             

线索二叉树-概念

   

     当用二叉链表作为二叉树的存储结构时,因为每个结点中只有指向其左、右儿子结点的指针,所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针,将降低存储空间的效率。

我们可以证明:在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针,除了根结点,每个结点都有一个从父结点指向该结点的指针,因此一共使用了n-1个指针,所以在n个结点的二叉链表中含有n+1个空指针。

因此可以利用这些空指针,存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索,加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

实现

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef char DataType;/*¶¨ÒåDataTypeÀàÐÍ*/
typedef enum {Link,Thread}PointerTag;
typedef struct node{
  DataType data;
  struct node *lchild, *rchild;/*×óÓÒº¢×Ó×ÓÊ÷*/
  PointerTag LTag,RTag;
}BiThrNode;
typedef BiThrNode *BiThrTree ;
void  CreatBinTree(BiThrTree *T)
{ /*¹¹Ôì¶þ²æÁ´±í,×¢Òâ:ÊäÈëÐòÁÐÊÇÏÈÐòÐòÁÐ*/
 char ch;
 if ((ch=getchar())==' ')
  *T=NULL;
 else{ /*¶ÁÈë·Ç¿Õ¸ñ*/
  *T=(BiThrNode *)malloc(sizeof(BiThrNode));/*Éú³É½áµã*/
 (*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
 CreatBinTree(&(*T)->lchild); /*¹¹Ôì×ó×ÓÊ÷    */
 CreatBinTree(&(*T)->rchild); /*¹¹ÔìÓÒ×ÓÊ÷*/
 }
}

BiThrTree pre;
void InThreading(BiThrTree p)
{
  if(p)
  {InThreading(p->lchild);/*×ó×ÓÊ÷ÏßË÷»¯*/
  if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*Ç°ÇýÏßË÷*/
  if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*ºó¼ÌÏßË÷*/
  pre=p;/*±£³ÖpreÖ¸Ïòp*/
  InThreading(p->rchild);/*ÓÒ×ÓÊ÷ÏßË÷»¯*/
 }
}
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
                                  /*ÖÐÐò±éÀ÷¶þ²æÊ÷T£¬²¢½«ÆäÖÐÐòÏßË÷»¯£¬ThrtÖ¸ÏòÍ·½áµã*/
{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
  (*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*½¨Í·½áµã*/
  (*Thrt)->rchild=*Thrt;/*ÓÒÖ¸Õë»ØÖ¸*/
  if(!T) (*Thrt)->lchild=*Thrt;
  else
  { (*Thrt)->lchild=T;pre=*Thrt;
    InThreading(T);/*ÖÐÐò±éÀú½øÐÐÖÐÐòÏßË÷»¯*/
 pre->rchild=*Thrt;pre->RTag=Thread;/*×îºóÒ»¸ö½áµãÏßË÷»¯*/
 (*Thrt)->rchild=pre;
  }
  return 1;
}

int print(BiThrTree e)
{printf("%d  %c  %d\n",e->LTag,e->data,e->RTag);return 1;}

int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
                                  /*中序遍历线索二叉树*/
{BiThrTree p;
 p=T->lchild;/*pÖ¸Ïò¸ù½áµã*/
 while(p!=T)/*空树或线索遍历结束时p==T*/
 {while(p->LTag==Link) p=p->lchild;
  if(!visit(p)) return 0;/*´òÓ¡*/
  while(p->RTag==Thread&&p->rchild!=T)
  {p=p->rchild;visit(p);}/*·ÃÎʺó¼Ì½áµã*/
  p=p->rchild;
 }
 return 1;
}

void main()
{ /*测试程序*/
  BiThrTree T,Thrt;
  CreatBinTree(&T);
  InOrderThreading(&Thrt,T);
  InOrderTraverse(Thrt,print);
  getch();
}
/*可以输入"-+a  *b  -c  d  /e  f  "*/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
线索二叉树
线索二叉树在二叉树的结点上加上线索的二叉树称为线索二叉树。
0 0
二叉树前序非递归遍历
二叉树前序非递归遍历 二叉树前序非递归遍历
0 0
二叉树中序非递归遍历
二叉树中序非递归遍历 二叉树中序非递归遍历
0 0
二叉树非递归遍历
来源:http://www.cnblogs.com/JCSU/articles/2005944.html 【bitree.cpp】   /*************************************************************************...
613 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载