• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
//线索二叉树,这里在二叉树的基础上增加了线索化
//杨鑫
#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;
} bitNode, *bitTree;

bitTree pre; 							//创建全局变量。表示刚刚訪问过的结点



/*
创建二叉树,其输入必须依照前序遍历的次序。

T:二叉树根节点 arr:依照前序遍历次序排列的各节点的值。无孩子结点时用空格取代 */ void create_tree(bitTree *T, char **arr) { char c; sscanf(*arr,"%c",&c); //读入一个结点值 (*arr)++; if(' '== c) //假设是空格,表示空结点 { *T=NULL; } else { *T=(bitTree)malloc(sizeof(bitNode)); //构造新结点 (*T)->data=c; (*T)->ltag=Link; (*T)->rtag=Link; create_tree(&(*T)->lchild,arr); //构造新结点的左孩子 create_tree(&(*T)->rchild,arr); //构造新结点的右孩子 } } /* 訪问结点信息 */ void visit(bitTree T) { printf("| %d | %c | %d |\n",T->ltag,T->data,T->rtag); } /* 前序遍历訪问二叉树 */ void pre_order_traverse(bitTree T,int level) { if(T) { visit(T); pre_order_traverse(T->lchild,level+1); pre_order_traverse(T->rchild,level+1); } } /* 中序遍历二叉树,对其进行线索化 */ void in_order_threading(bitTree T) { if(T) { in_order_threading(T->lchild); //左孩子线索化 if(!T->lchild) //假设左孩子为空,则将其指向直接前驱 { T->lchild=pre; T->ltag=Thread; } if(!pre->rchild) //假设上一个结点的右孩子为空,则将其指向直接后继。(注意:仅仅有訪问到下一个结点时,才会知道本结点的后继是谁) { pre->rchild=T; pre->rtag=Thread; } pre=T; in_order_threading(T->rchild); //右孩子线索化 } } /* 增加一个头结点,使二叉线索树成一个封闭环 P:带有头结点的二叉树。头结点的左孩子指向二叉树T;右孩子指向T树中的最后一个叶子结点 T:不带有头结点的二叉树。

*/ void in_thread(bitTree *P,bitTree T) { (*P)=(bitTree)malloc(sizeof(bitNode)); //构造新增加的头结点 (*P)->ltag=Link; (*P)->rtag=Thread; (*P)->rchild=*P; if(!T) //假设二叉树为空,则P的孩子指向自己。 { (*P)->lchild=*P; } else { (*P)->lchild=T; pre=*P; in_order_threading(T); //对二叉树进行线索化 (*P)->rchild=pre; //将头结点右孩子指向最后一个叶子结点 pre->rtag=Thread; //将最后一个叶子结点的右孩子指向头结点。这样。环就形成了。

pre->rchild=*P; } } /* 非递归方式:中序遍历二叉树(树必须带有头结点,且已经线索化) P:带有头结点的二叉树 */ void in_order_traverse(bitTree P) { bitTree T; T=P->lchild; while(T!=P) //推断是否空树 { while(T->ltag==Link) //从左孩子開始。直到叶子结点 { T=T->lchild; } visit(T); while(T->rtag==Thread && T->rchild!=P) //依据线索,訪问后继结点。而且后继结点不是指向头结点的 { T=T->rchild; visit(T); } T=T->rchild; } } int main() { bitTree P,T; int level =1; //表示该结点的深度 char *arr="ab d ce "; //构造二叉树所需结点(按前序遍历方式输入) create_tree(&T,&arr); //构造二叉树 printf("pre_order_traverse:先序遍历:\n"); pre_order_traverse(T,level); //前序遍历输出二叉树 printf("in_order_traverse:中序遍历:\n"); in_thread(&P,T); //二叉树线索化 in_order_traverse(P); //输出线索化后的二叉树 return 0; }


如图:




鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C语言中Static和Const关键字的的作用发布时间:2022-07-14
下一篇:
使用C++为对象分配与释放内存时的几个好习惯发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap