转自: http://blog.csdn.net/cheneagle/article/details/4397750
线索二叉树利用末节点的空指针将其他节点连接起来,达到整个树枝顺序和逆序都能遍历的作用。因为任何一棵n节点的二叉树,它总有n+1个空的指针。比如1个节点二叉树,那么就有2个左右孩子为空指针,同理以此类推。这样就充分利用空间而达到快速遍历的作用。详细请看源代码:
为了以后快速查找,我还是简单说下怎么输入数据,如下图所示的数据结构:
像这样的数据结构我们怎么输入呢?
第一次输入ab#,然后回车。
第二次输入c##,然后回车。
第三次输入d#,然后回车。
第四次输入g##,然后回车。
不知道以后的我或者网友是否看明白呢?希望以后的我和大家领悟能力比我现在这些苍白的文字强n的XX次方!
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream.h> typedef char DataType; typedef struct _ThreadBiTreeNode { DataType data; int ltag, rtag; struct _ThreadBiTreeNode *right, *left; }ThreadBiTreeNode, *ThreadBiTree; /** * 先序方式创建线索二叉树 * 请用以下方式输入ab#,然后回车;c##,然后回车; * d#,然后回车;g##,然后回车。 */ ThreadBiTree CreateTree( ) { ThreadBiTree t; DataType ch; cin >> ch; if( ch == '#' ) t = NULL; else { t = ( ThreadBiTree )malloc( sizeof( ThreadBiTreeNode ) ); if( t ) { t->data = ch; t->ltag = t->rtag = 0; t->left = CreateTree(); t->right = CreateTree(); } } return t; } /** * 先序线索二叉树,将空的指针指向一个连接 * 这里要申请一个全局变量g_pre * */ ThreadBiTree g_pre; void PreThreadTree( ThreadBiTree t ) { if( t == NULL ) return; if( t->left == NULL ) t->ltag = 1; if( t->right == NULL ) t->rtag = 1; if( g_pre != NULL && t->ltag == 1 ) t->left = g_pre; if( g_pre != NULL && g_pre->rtag == 1 ) g_pre->right = t; g_pre = t; if( t->ltag == 0 ) PreThreadTree( t->left ); if( t->rtag == 0 ) PreThreadTree( t->right ); } /** * 中序线索二叉树 * * */ void InThreadTree( ThreadBiTree t ) { if( t == NULL ) return; InThreadTree( t->left ); if( t->left == NULL ) t->ltag = 1; if( t->right == NULL ) t->rtag = 1; if( g_pre != NULL && t->ltag == 1 ) t->left = g_pre; if( g_pre != NULL && g_pre->rtag == 1 ) g_pre->right = t; g_pre = t; if( t->rtag == 0 ) InThreadTree( t->right ); } /** * 后序线索二叉树 * * */ void PostThreadTree( ThreadBiTree t ) { if( t == NULL ) return; PostThreadTree( t->left ); PostThreadTree( t->right ); if( t->left == NULL ) t->ltag = 1; if( t->right == NULL ) t->rtag = 1; if( g_pre != NULL && t->ltag == 1 ) t->left = g_pre; if( g_pre != NULL && g_pre->rtag == 1 ) g_pre->right = t; g_pre = t; } /** * 寻找当前节点的后节点 * * */ ThreadBiTree FindNode( ThreadBiTree t ) { if( t->rtag == 1 ) return t->right; else { t = t->right; while( t->ltag == 0 ) { t = t->left; } return t; } } /** * 中序方式遍历线索二叉树 * 在VC6.0下测试成功 * */ void InOrderThreadBiTree( ThreadBiTree t ) { if( t == NULL ) return; printf( "%c ", t->data ); ThreadBiTree p; //当只有一个元素时,并没有建立起线索二叉树 if( t->ltag == 0 ) p = t->left; else p = t->right; while( p && ( p != t ) ) { while( p->ltag == 0 ) { printf( "%c ", p->data ); p = p->left; } printf( "%c ", p->data ); while( p->rtag == 1 && p->right != t && p->right ) { p = p->right; printf( "%c ", p->data ); } p = p->right; } } /** * 插入右节点: 参考网上代码,有些地方需要商榷。 * * */ void InsertRightNode( ThreadBiTree p, ThreadBiTree node ) { node->ltag = node->rtag = 1;//node->rtag=1为什么要置1,因为有node->right=p->right;这句 node->left = p; //这可以考虑node->rtag = 0. node->right = p->right;//也可以让它为node->left = p->right,(^_^)是不是钻牛角尖了呢? p->right = p; //当然因为线索连接好了,为了不影响先前设置好的线索,故这样做,暂不考证! p->rtag = 0; } int main( void ) { ThreadBiTree t; t = CreateTree(); PreThreadTree( t ); InOrderThreadBiTree( t ); return 0; }
相关推荐
二叉树创建遍历及线索化,二叉树的创建存储以及先序中序后序遍历,图形树输出
数据结构中二叉树的遍历及线索化,三种递归遍历,两种非递归遍历,两种线索化,供大家参考参考!!!!
c,数据结构 用c写的线索二叉树的创建,后续遍历,输出
主要介绍了PHP实现的线索二叉树及二叉树遍历方法,结合实例形式较为详细的分析了线索二叉树的定义,创建,判断与遍历等技巧,需要的朋友可以参考下
通过前序序列创建线索二叉树 1:中序遍历 2:查找节点前驱后继 3:插入节点 4:删除节点 0:退出
NULL 博文链接:https://1350579085.iteye.com/blog/1954013
。。。
。。。
1.创建以二叉链表作存储结构的二叉树; 2.按前序遍历二叉树; 3.按中序遍历二叉树; 4.按后序遍历二叉树; 5.计算二叉树的单枝结点数; 6.按层次遍历二叉树。
二叉树的创建、遍历、以及左右子树交换,非递归遍历,叶子节点计算及线索树等完整程序
关于数据结构实验的二叉树问题
二叉树的遍历、线索及应用( 用递归或非递归的方法都可以) [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 ...
个人认为比较简洁 使用递归方式 创建使用扩展二叉树更加便捷 且有部分先序线索化代码 不够完善
这是一个关于线索化二叉树内容的文档 主要写了中序线索化二叉树的创建,遍历和插入
利用双亲表示法创建一棵树,将该树转换成二叉链表表示,并给出转换后的二叉树的先序、中序和后序遍历结果以及对该二叉树进行中序遍历线索化。
个人的实验报告,包括了源代码,使用C++编写的,可以参考一下
画演示软件包括二叉树的遍历、二叉树遍历算法的应用、二叉树的创建、二叉树的线索化、树和森林的基本操作、哈夫曼树六个模块。本系统突出从教师教学环节中的难点和学生易于出错的知识点这两方面出发,解决了现有...
C语言 二叉树实验报告,创建并输出二叉树,输出内容有:图形、数的深度、数的叶子数量。然后根据所创建的二叉树进行线序遍历,创建一棵先序线索二叉树链表,并非递归地输出先序遍历序列。包含各函数算法,源代码。
本包里包含了Java版的创建二叉树,二叉树的遍历,哈夫曼树,链表,链队,链栈,顺序表,顺序查找,顺序队,顺序栈,线索二叉树,折半查找的代码