C语言数据结构之线索二叉树及其遍历语言数据结构之线索二叉树及其遍历
C语言数据结构之线索二叉树及其遍历语言数据结构之线索二叉树及其遍历
遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一
个非线性的结构进行线性化。使得在这个访问序列中每一个节点都有一个直接前驱和直接后继。传统的链式结构只能体现一种
父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些
空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作。引入线索二叉树的目的是: 为了
加快查找节点的前驱和后继。对二叉树的线索化就是对二叉树进行一次遍历,在遍历的过程中检测节点的左右指针是否为空,
如果是空,则将他们改为指向前驱和后继节点的线索。
如果二叉树没有被线索化,也可以使用<<非递归>>的代码进行遍历的,但是那就需要借助于<<栈>>,但是在线索化之后,对线
索化的二叉树进行<<非递归>>的遍历就不再需要栈的辅助。
实现代码:实现代码:
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;
/* 定义枚举类型,其值只能是Link和Thread
* Link表示的该指针指示的是孩子
* Thread表示的是还指针指示的是前驱或者是后缀
* */
typedef enum {
Link,Thread
}PointerTag;
typedef struct ThrBiTrNode{
ElemType data;
struct ThrBiTrNode *lchild, *rchild;
PointerTag rTag, lTag;
}ThrBiTrNode, *ThrBiTree;
ThrBiTree Pre;
Status InitThreadBinaryTree(ThrBiTree* T){
*T = NULL;
return OK;
}
//先序建立二叉树,lchild和rchild都是指示做孩子和右孩子,所以lTag和rTag为Link
Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){
ElemType c;
scanf("%c", &c);
if( ' ' == c ){
*T = NULL;
}
else{
*T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode));
if( !*T ){
return ERROR;
}
(*T)->data = c;
(*T)->lTag = Link;
(*T)->rTag = Link;
ThreadBinaryTree_PreOrderInput(&(*T)->lchild);
ThreadBinaryTree_PreOrderInput(&(*T)->rchild);
}
return OK;
}
//<<中序遍历>>对二叉树进行<<线索化>>,但是没有提供Pre的初始值,只是给出了
//中间的过程,递归的思想和思考方式。
//1 线索化左子树