C语言中序遍历实现线索二叉树（二叉树的改进）

文章目录

• 结构体
• 初始化
• 创建中序线索二叉树
• • • 线索化的规则是：左线索指针指向当前结点在中序遍历序列中的前驱结点，右线索指针指向后继结点
  • 下面以这棵二叉树进行分析
  • • • 1.递归找到根的左孩子的左孩子……（即中序遍历的第一个结点）
• 获取第一个结点
• 获取最后一个结点
• 获取当前结点的前驱
• 获取当前结点的后继
• 获取当前结点的父结点
• 线索二叉树的中序遍历
• 查找指定的元素
• 测试

结构体

#define ElemType char

typedef enum{LINK,THREAD}Tag_Type;//LINK表示指针,指向结点的左右孩子
                                  //THREAD表示线索，指向结点的前驱(L)或后继(R)
typedef struct BinTreeNode
{
	ElemType data;
	struct BinTreeNode *leftChild;
	struct BinTreeNode *rightChild;
	Tag_Type ltag;//线索标记
	Tag_Type rtag;
}BinTreeNode;

typedef struct BinTree
{
	BinTreeNode *root;
	ElemType     refvalue; //stop value
}BinTree;
           

初始化

void InitBinTree(BinTree *bt, ElemType ref)
{
	bt->root = NULL;
	bt->refvalue = ref;
}

//用于开辟一个新结点的空间和这个结点链的初始化
BinTreeNode* _Buynode(ElemType x)
{
	BinTreeNode *s = (BinTreeNode*)malloc(sizeof(BinTreeNode));
	assert(s != NULL);
	s->data = x;//给这个空间赋值（数据）
	s->leftChild = s->rightChild = NULL;
	s->ltag = s->rtag = LINK;//一开始标记为指针，指向左右孩子
	return s;
}
           

创建中序线索二叉树

线索化的规则是：左线索指针指向当前结点在中序遍历序列中的前驱结点，右线索指针指向后继结点

void CreateInThread(BinTree *bt)
{
	BinTreeNode *pre = NULL;//一开始前驱结点设为NULL
	CreateInThread(bt->root,pre);
	pre->rightChild = NULL;//如果是最后一个元素，他没有后继
	pre->rtag = THREAD;
}
void CreateInThread(BinTreeNode *&t, BinTreeNode *&pre)
{//t表示指向根节点的指针
	if(t == NULL)
		return;
	CreateInThread(t->leftChild,pre);
	//建立当前节点的额前驱线索
	if(t->leftChild == NULL)
	{
		t->ltag = THREAD;
		t->leftChild = pre;
	}
	//建立前驱结点的后继线索
	if(pre!=NULL && pre->rightChild==NULL)
	{
		pre->rtag = THREAD;
		pre->rightChild = t;
	}
	pre = t;
	CreateInThread(t->rightChild,pre);
}
           

下面以这棵二叉树进行分析

没有加入线索前的线索二叉树

该二叉树的中序遍历转化为线性结构的顺序是CBEDFAGH

1.递归找到根的左孩子的左孩子……（即中序遍历的第一个结点）

递归到C后继续递归，发现递归到C的左孩子为空，于是跳出递归，这样就找到了C，执行递归后面的代码，发现C的左孩子是空的，

左标记标记为Thread（书上把他当做1，说明这是个线索，指向前驱），此时C的左孩子就相当于指向C的前驱。

继续执行，C的前驱为空，不执行下面的if

pre前驱结点指向C

继续遍历t的右孩子（此时t是C），C没有右孩子，return ；

接下来指针t回到了C

因为递归会返回原来因为一些条件没有被执行完的东西，t这时回到了B

B的左孩子不为空，不执行第一个if，但是此时pre（也就是C）不为空且pre（C）的右孩子为空，执行第二个if

这时就完成了C的前驱和后继，B的前驱

然后pre指针指向此时的t（即B），因为B左右都有孩子，所以标志为LINk

递归遍历B的右孩子，此时在递归执行B的右孩子的左孩子（即D）时，又发现了左孩子，继续递归，到达了E

pre指针指向了E，然后建立对前驱结点（即E）的后继线索

t指针继续指向t的后孩子，发现为空，回退到E,接着回退到D，建立E（pre）的后继是D（即现在的t）

pre指向D

然后对D的右孩子，F先建立前驱线索，当t回退到A时，再建立F的后继线索，如此往复，直到pre指向最后一个结点，让pre的后继指向NULL。

得到了一颗线索二叉树

获取第一个结点

BinTreeNode* First(BinTree *bt)
{
	return First(bt->root);
}
BinTreeNode* First(BinTreeNode *t)//中序遍历的第一个结点就是根结点的左孩子的左孩子……直到那个左孩子的左孩子是空
{
	if(t == NULL)
		return NULL;
	BinTreeNode *p = t;//p指针先指向根结点
	while(p->ltag == LINK)
		p = p->leftChild;
	return p;
}
           

获取最后一个结点

BinTreeNode* Last(BinTree *bt)
{
	return Last(bt->root);
}
BinTreeNode* Last(BinTreeNode *t)
{
	if(t == NULL)
		return NULL;
	BinTreeNode *p = t;
	while(p->rtag == LINK)//根结点的右子树中，只要右标记为线，说明这是最后一个结点
		p = p->rightChild;
	return p;
}
           

获取当前结点的前驱

BinTreeNode* Prio(BinTree *bt, BinTreeNode *cur)
{
	return Prio(bt->root,cur);
}
BinTreeNode* Prio(BinTreeNode *t, BinTreeNode *cur)
{
	if(t==NULL || cur==NULL)
		return NULL;
	if(cur->ltag == THREAD)//如果当前结点的左标记是线索（1），说明指向的是前驱结点
		return cur->leftChild;
	return Last(cur->leftChild);//如果是A位置,他的前驱就是F，即A的左子树的最后一个结点
}
           

获取当前结点的后继

BinTreeNode* Next(BinTree *bt, BinTreeNode *cur)
{
	return Next(bt->root,cur);
}
BinTreeNode* Next(BinTreeNode *t, BinTreeNode *cur)
{
	if(t==NULL || cur==NULL)
		return NULL;
	if(cur->rtag == THREAD)//如果当前结点的右标记是线索（1），说明指向的是后继
		return cur->rightChild;
	return First(cur->rightChild);//如果当前结点的左右线索是0，如B，D的位置，就需要先找到B的右子树中序遍历的第一个节点（即E），E就是B的后继
}
           

获取当前结点的父结点

BinTreeNode* Parent(BinTree *bt, BinTreeNode *cur)
{
	return Parent(bt->root,cur);
}
BinTreeNode* Parent(BinTreeNode *t, BinTreeNode *cur)
{
	if(t==NULL || cur==NULL)
		return NULL;
	if(t == cur)
		return NULL;
/**************如果当前结点有线索，那父节点可能存在于  前驱的右孩子  或   后继的左孩子******************/
	BinTreeNode *p;
	//如E的后继D就是E的父结点， G的前驱A就是G的的父节点
	if(cur->ltag == THREAD)
	{
		p = cur->leftChild;//若当前结点是E，p就是B                              若当前结点是G，p就是A
		if(p->rightChild == cur)//若B的右子树是E，直接返回，但是并不是。            显然A的右子树就是G，直接返回
			return p;
	}
	if(cur->rtag == THREAD)
	{
		p = cur->rightChild;//当前结点是E，p就是D
		if(p->leftChild == cur)//p的左子树是当前结点E，直接返回p（即D）
			return p;
	}
/*************如果当前结点没有线索如B，D结点***************************************/
	p = First(cur->leftChild);//若当前结点是D，p就是D左孩子中的第一个结点（即E）        //若当前结点是B，p就是C
	p = p->leftChild;//第一个结点可定有前驱，此时E的前驱就是B，p=B						//C的前驱是NULL，不执行面的if
	if(p!=NULL && p->rightChild == cur)//B的右孩子就是D，直接返回
		return p;

	p = Last(cur->rightChild);                                                   //找到B的右子树的最后一个结点，即F
	return p->rightChild;                                                         //返回找到F的后继A，显然A就是B的父节点
}
           

线索二叉树的中序遍历

在树的结点上增加了线索，不能按照左孩子右孩子的递归遍历了。

思路是根据依次找到p的前驱和后继，让p=p的后继，循环输出。例如先找到了C，根据C找到后继B，此时让p=B，开始找到B的后继E……

void InOrder(BinTree *bt)
{
	InOrder(bt->root);
}
void InOrder(BinTreeNode *t)
{
	BinTreeNode *p;
	for(p=First(t); p!=NULL; p=Next(t,p))//p=Next(t,p)，让p=当前结点的后继
	{
		printf("%c ",p->data);
	}
	printf("\n");
}
           

查找指定的元素

BinTreeNode* Search(BinTree *bt, ElemType key)
{
	return Search(bt->root,key);
}
BinTreeNode* Search(BinTreeNode *t, ElemType key)
{
	if(t == NULL)
		return NULL;
	if(t->data == key)//如果刚好查找的是树根，直接返回。如果这个if不加，当然下面的循环也会查找到根，有利有弊
		return t;

	BinTreeNode *p;
	for(p=First(t); p!=NULL; p=Next(t,p))//根据遍历为线性结构，循环查找
	{
		if(p->data == key)
			return p;
	}
	return NULL;

}
           

测试

void main()
{
	char *str = "ABC##DE##F##G#H##";
	BinTree mytree;
	InitBinTree(&mytree,'#');
	CreateBinTree(&mytree,str);

	CreateInThread(&mytree);

	//BinTreeNode *p = Search(&mytree,'B');
	//BinTreeNode *parent = Parent(&mytree,p);
	//BinTreeNode *q = Prio(&mytree,p);
	//InOrder(&mytree);
}