【数据结构 | C语言】中序线索化二叉树与遍历

【数据结构 | C语言】中序线索化二叉树与遍历

原创代码，如有错误，欢迎批评指正

线索二叉树：

        有 n 个结点的二叉树中必定存在 n+1 个空链域。因此，我们可以利用这些空链域存储结点的前驱和后继信息。同时为了区分存储的是左右结点还是线索，为树的结点添加了标志域说明

LTaglchilddatarchildRTag

上面提到了前驱和后继。因此，存储的线索与遍历方式有关。以最简单的二叉树为例

        

先序：ABC

中序：BAC

后序：BCA

        对于B来说，我们选择将此树中序线索化，B的后继就是A，C的前驱是A。由于B前和C后没有结点，因此设置为NULL

线索化

以下两种方式效果相同

pnode pre = NULL;
void InThreadTree(pnode root) {
	if (root!=NULL) {
		// 先线索化左子数
		InThreadTree(root->lnode);
		// 线索化当前结点
		if (root->lnode == NULL) {
			root->lnode = pre;
			root->ltag = Thread;
		}
		// 后续结点
		if (pre!=NULL && pre->rnode==NULL) {
			pre->rnode = root;
			pre->rtag = Thread;
		}
		// 向前走
		pre = root;
		// 线索化右子数
		InThreadTree(root->rnode);
	}
}


// pre作为二级指针，保存上一结点
void InThreadTree2(pnode root, pnode *pre) {
	if (root!=NULL) {
		// 线索化左子数
		InThreadTree2(root->lnode, pre);
		// 线索化当前结点
		if (root->lnode==NULL) {
			root->lnode = *pre;
			root->ltag = Thread;
		}
		if (*pre!=NULL && (*pre)->rnode==NULL) {
			(*pre)->rnode = root;
			(*pre)->rtag = Thread;
		}
		*pre = root;
		InThreadTree2(root->rnode, pre);
	}
}

遍历

void Traverse_InThreadTree(pnode root) {
	while (root) {
		// 如果是结点，就一直向左找到线索
		while (root->ltag == link) {
			root = root->lnode;
		}	
		// 中序遍历最先输出的是当前树最左边的结点
		printf("%dt", root->val);
		// rnode为NULL说明到了结尾
		// 如果是线索，就向右走并输出
		while (root->rnode != NULL && root->rtag == Thread) {
			root = root->rnode;
			printf("%dt", root->val);
		}
		// 否则，就向右走
		// 此处一定能向右走，因为root不会到结尾的，在上一个whle里面，如果右结点为空就不走，因此上面不会走到NULL
		root = root->rnode;
	}
	printf("n");
}

完整代码：

# include 
# include 
# include 

typedef int ElemType;
typedef int bool;
typedef struct Node node;
typedef struct Node *pnode;
typedef enum Tag tag;

# define true 1
# define false 0

enum Tag {
	link, Thread
};

struct Node {
	ElemType val;
	struct Node *lnode, *rnode;
	tag ltag, rtag;
};

pnode CreateNode();
void Add(pnode *p, ElemType val);
void PreOrder(pnode root);
void InOrder(pnode root);
void PostOrder(pnode root);

void InThreadTree(pnode root);
void InThreadTree2(pnode root, pnode *pre);

void Traverse_InThreadTree(pnode root);


int main() {
	pnode proot = CreateNode(0);
	Add(&proot->lnode, 1);
	Add(&proot->rnode, 2);
	Add(&proot->lnode->lnode, 3);
	Add(&proot->lnode->rnode, 4);
	Add(&proot->rnode->lnode, 5);
	Add(&proot->rnode->rnode, 6);

	// 输出
	printf("inOrder : ");
	InOrder(proot);
	printf("n");

	// 线索化
	// InThreadTree(proot);

    // 使用pre二级指针线索化
	pnode pre = NULL;
	InThreadTree2(proot, &pre);
	// 输出
	printf("traverse : ");
	Traverse_InThreadTree(proot);

	return 0;
}

pnode CreateNode() {
	pnode new = (pnode) malloc(sizeof(node));
	memset(new, 0, sizeof(node));
	return new;
}

void Add(pnode *p, ElemType val) {
	pnode new = CreateNode();
	new->val = val;
	*p = new;
}

void PreOrder(pnode root) {
	if (root) {
		printf("%dt", root->val);
		PreOrder(root->lnode);
		PreOrder(root->rnode);
	}
}

void InOrder(pnode root) {
	if (root) {
		InOrder(root->lnode);
		printf("%dt", root->val);
		InOrder(root->rnode);
	}
}

void PostOrder(pnode root) {
	if (root) {
		PostOrder(root->lnode);
		PostOrder(root->rnode);
		printf("%dt", root->val);
	}
}


pnode pre = NULL;
void InThreadTree(pnode root) {
	if (root!=NULL) {
		// 先线索化左子数
		InThreadTree(root->lnode);
		// 线索化当前结点
		if (root->lnode == NULL) {
			root->lnode = pre;
			root->ltag = Thread;
		}
		// 后续结点
		if (pre!=NULL && pre->rnode==NULL) {
			pre->rnode = root;
			pre->rtag = Thread;
		}
		// 向前走
		pre = root;
		// 线索化右子数
		InThreadTree(root->rnode);
	}
}

// pre作为二级指针，保存上一结点
void InThreadTree2(pnode root, pnode *pre) {
	if (root!=NULL) {
		// 线索化左子数
		InThreadTree2(root->lnode, pre);
		// 线索化当前结点
		if (root->lnode==NULL) {
			root->lnode = *pre;
			root->ltag = Thread;
		}
		if (*pre!=NULL && (*pre)->rnode==NULL) {
			(*pre)->rnode = root;
			(*pre)->rtag = Thread;
		}
		*pre = root;
		InThreadTree2(root->rnode, pre);
	}
}


void Traverse_InThreadTree(pnode root) {
	while (root) {
		// 如果是结点，就一直向左找到线索
		while (root->ltag == link) {
			root = root->lnode;
		}	
		// 中序遍历最先输出的是当前树最左边的结点
		printf("%dt", root->val);
		// rnode为NULL说明到了结尾
		// 如果是线索，就向右走并输出
		while (root->rnode != NULL && root->rtag == Thread) {
			root = root->rnode;
			printf("%dt", root->val);
		}
		// 否则，就向右走
		// 此处一定能向右走，因为root不会到结尾的，在上一个whle里面，如果右结点为空就不走，因此上面不会走到NULL
		root = root->rnode;
	}
	printf("n");
}