亲宝软件园·资讯

展开

C语言线索二叉树

洛语言 人气:1

线索二叉树的意义

线索二叉树的定义

线索二叉树结构的实现

二叉树的线索存储结构

为了区分二叉树某一节点是指向它的孩子节点还是指向前驱或者后继节点,我们可以在每个节点增设两个标志,Ltag,Rtag.

其中:

所以,线索二叉树结构定义代码如下:

typedef char BTDataType;
typedef enum{Link,Thread}PointerTag;//Link 是0,Thread 是1。
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	PointerTag LTag ;
	PointerTag RTag;
	BTDataType data;
}BTNode;

二叉树的中序线索化

线索化的过程就是在遍历过程中修改空指针的过程

以上二叉树中序遍历可以得到:

  D B E A F C
  D的前驱是空,后继是B
  B的前驱是D,后继是E
  E的前驱是B,后继是A
  F的前驱是A,后继是C
  C的前驱是F,后继是空

线索化后:

中序遍历线索化的递归函数代码如下:

//中序线索化
BTNode* pre = NULL;/*全局变量,始终指向刚刚访问过的节点*/
void InThreading(BTNode* p)
{
	if (p == NULL) return;
	InThreading(p->left);//递归左子树线索化
	if (!p->left)//左孩子为空,left指针指向前驱
	{
		p->LTag = Thread;
		p->left = pre;
	}
	if (pre!=NULL && !pre->right)//右孩子为空,right指针指向后继指针。
	//这里判断 pre!=NULL 是因为线索化中序遍历的第一个节点(节点D)时,它并没有前驱节点,此时的pre仍然是NULL。
	{
		pre->RTag = Thread;
		pre->right = p;
	}
	pre = p;//保持pre指向p的前驱
	InThreading(p->right);
}

分析:

线索二叉树的中序遍历

void MidOrder(BTNode*p)
{
	while (p != NULL)
	{
		while (p->LTag == Link)//
		{
			p = p->left;
		}
		printf("%c ",p->data);
		while (p->RTag == Thread && p->right != p)
		{
			p = p->right;
			printf("%c ", p->data);
		}
		p = p->right;
	}
	return;
}

分析:

总结

如果所用的二叉数需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉数是一个很好的选择;

以上内容参考于《大话数据结构》。

加载全部内容

相关教程
猜你喜欢
用户评论