/* c6-3.h 二叉树的二叉线索存储表示 */ typedef enum{Link,Thread}PointerTag; /* Link(0):指针,Thread(1):线索 */ typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; /* 左右孩子指针 */ PointerTag LTag,RTag; /* 左右标志 */ }BiThrNode,*BiThrTree;
/* bo6-3.c 二叉树的二叉线索存储(存储结构由c6-3.h定义)的基本操作 */ Status CreateBiThrTree(BiThrTree *T) { /* 按先序输入二叉线索树中结点的值,构造二叉线索树T */ /* 0(整型)/空格(字符型)表示空结点 */ TElemType h; #if CHAR scanf("%c",&h); #else scanf("%d",&h); #endif if(h==Nil) *T=NULL; else { *T=(BiThrTree)malloc(sizeof(BiThrNode)); if(!*T) exit(OVERFLOW); (*T)->data=h; /* 生成根结点(先序) */ CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */ if((*T)->lchild) /* 有左孩子 */ (*T)->LTag=Link; CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */ if((*T)->rchild) /* 有右孩子 */ (*T)->RTag=Link; } return OK; } BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */ void InThreading(BiThrTree p) { /* 中序遍历进行中序线索化。算法6.7 */ if(p) { InThreading(p->lchild); /* 递归左子树线索化 */ if(!p->lchild) /* 没有左孩子 */ { p->LTag=Thread; /* 前驱线索 */ p->lchild=pre; /* 左孩子指针指向前驱 */ } if(!pre->rchild) /* 前驱没有右孩子 */ { pre->RTag=Thread; /* 后继线索 */ pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */ } pre=p; /* 保持pre指向p的前驱 */ InThreading(p->rchild); /* 递归右子树线索化 */ } } Status InOrderThreading(BiThrTree *Thrt,BiThrTree T) { /* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点。算法6.6 */ *Thrt=(BiThrTree)malloc(sizeof(BiThrNode)); if(!*Thrt) exit(OVERFLOW); (*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 OK; } Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType)) { /* 中序遍历二叉线索树T(头结点)的非递归算法。算法6.5 */ BiThrTree p; p=T->lchild; /* p指向根结点 */ while(p!=T) { /* 空树或遍历结束时,p==T */ while(p->LTag==Link) p=p->lchild; if(!Visit(p->data)) /* 访问其左子树为空的结点 */ return ERROR; while(p->RTag==Thread&&p->rchild!=T) { p=p->rchild; Visit(p->data); /* 访问后继结点 */ } p=p->rchild; } return OK; }
/* main6-3.c 检验bo6-3.c的主程序 */ #define CHAR 1 /* 字符型 */ /*#define CHAR 0 /* 整型(二者选一) */ #if CHAR typedef char TElemType; TElemType Nil=' '; /* 字符型以空格符为空 */ #else typedef int TElemType; TElemType Nil=0; /* 整型以0为空 */ #endif #include"c1.h" #include"c6-3.h" #include"bo6-3.c" Status vi(TElemType c) { #if CHAR printf("%c ",c); #else printf("%d ",c); #endif return OK; } void main() { BiThrTree H,T; #if CHAR printf("请按先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n"); #else printf("请按先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n"); #endif CreateBiThrTree(&T); /* 按先序产生二叉树 */ InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */ printf("中序遍历(输出)二叉线索树:\n"); InOrderTraverse_Thr(H,vi); /* 中序遍历(输出)二叉线索树 */ printf("\n"); }
相关推荐
实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点、兄弟节点获取、先中后序递归及非遍历、按层次遍历、中序迭代器(非递归算法)、节点查找、先序和中序序列重建二叉树、数组和二叉链表存储结构...
本节主要讲述二叉树的线索链表存储结构和相关操作
线索二叉树的存储结构、线索化和遍历,其中的代码很不错
(2) 用先序遍历法建立二叉树二叉链表存储结构(结点数据域类型为char,输入字符序列用字符'#'表示NULL),实现中序线索化,并用非递归算法输出中序遍历结果的正序和逆序序列。 二、图 1. 已知某无向图如下图所示。画出...
关于数据结构实验的二叉树问题
1. 一棵二叉树的顺序存储情况如下: 树中,度为2的结点数为( )。 A.1 B.2 C.3 D.4 2. 一棵“完全二叉树”结点数为25,高度为( )。 A.4 B.5 C.6 D.不确定 3.下列说法中,( )是正确的。 A. 二叉树就是...
二叉树的遍历、线索及应用( 用递归或非递归的方法都可以) [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 ...
(2) 用先序遍历法建立二叉树二叉链表存储结构(结点数据域类型为char,输入字符序列用字符'#'表示NULL),实现中序线索化,并用非递归算法输出中序遍历结果的正序和逆序序列。 二、图 1. 已知某无向图如下图所示。画出...
(1) 用先序遍历法建立二叉树二叉链表存储结构(结点数据域类型为char,输入字符序列用字符'#'表示NULL),实现中序线索化,并用非递归算法输出中序遍历结果的正序和逆序序列 1. 简答题 1. 已知某无向图如下图所示。画...
当以二叉链表作为储存结构时,只能找到结点的左右孩子的信息,而不能直接找到结点的前驱后继,所以我们在每个结点上增加两个指针域fwd和bawd,分别指示结点在任一次序遍历时得到的前驱后继信息。
2004年研究生数据结构试题 中序线索二叉树二叉链表的形式存储
8 树与二叉树 二叉链表存储的二叉树 BiTree 孩子-兄弟存储的树 CTree 二叉树线索化 先序 PreThreading 中序 InThreading 后序 PostThreading 最优二叉树 HuffmanTree 9 图 图类的实现 数组表示 ArrayGraph ...
1.创建以二叉链表作存储结构的二叉树; 2.按前序遍历二叉树; 3.按中序遍历二叉树; 4.按后序遍历二叉树; 5.计算二叉树的单枝结点数; 6.按层次遍历二叉树。
// 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; // 左右孩子指针 ...
前驱和后继结点的指针称为线索,加上线索的二叉树称为线索二叉树,加上线索的二叉链表称为线索链表。 5.5 二叉树遍历的非递归算法 5.5.1 前序遍历非递归算法 关键:在前序遍历过某个左子树后,如何找到该结点的右子...
6.2.4 二叉树二叉链表的一个生成算法 6.3 遍历二叉树 6.3.1 先根遍历 6.3.2 中根遍历 6.3.3 后根遍历 6.3.4 二叉树遍历算法的应用 6.4 线索二叉树 6.4.1 线索二叉树的基本概念 6.4.2 线索二叉树的逻辑表示...
寻找中序线索化二叉树指定结点的前驱 寻找中序线索化二叉树指定结点的后继 构造哈夫曼树的算法模拟 构造哈夫曼树过程 树、森林和二叉树的转换 开放定址法建立散列表 拉链法创建散列表 朴素串匹配算法过程示意 图的...
理解二叉树的定义,性质,存储结构等基本概念,熟悉使用多种表示法构造二叉树,掌握采用二叉链表存储结构实现二叉树的构造,遍历,插入,删除等操作算法,理解线索二叉树的作用,掌握获得线索二叉树结点在指定遍历...
第一章绪论、算法衡量指标、第二章线性表、顺序表、链表、第三章栈和队、栈、栈的应用举例、队列、循环队列、第四章串、串的模式匹配、第五章数组和广义表、稀疏矩阵的压缩存储方法:、广义表、第六章树和二叉树、...
一些算法的 flash动画演示:B树的删除,B树的生长过程,三元组表的转置,中序线索化二叉树,串的顺序存储,二分查找,二叉排序树的删除,二叉排序树的生成,二叉树的建立,克鲁斯卡尔算法构造最小生成树,冒泡排序,...