在前一节中，我们说，在遍历二叉树中，在任何一个节点处，有三部分需要访问：左子树、右子树、根节点，让左子树在右子树前访问，这样按照根节点的访问位置，产生三种遍历方法：前序遍历，中序遍历，后序遍历。而在二叉树中，n个结点可以产生2n个指针，只有n-1可结点有指针指向，另外n+1个为空指针，线索化二叉树的思想就是把空指针利用起来，用他们存储线索，线索指向按照那种遍历方式应访问的下一个结点。

#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
struct btNodeT //线索化二叉树结点
{
	char data;
	btNodeT* lchild, * rchild;
	int ltag, rtag;//线索标记，0代表指向孩子结点，1代表指向线索。
};
void createBT2(btNodeT*& b, char str[])//用括号型表示法为二叉树赋值，像一般二叉树一样
{
	btNodeT* stack[100];
	int top = -1;//实现一个栈
	int k = 1, j = ;
	btNodeT* p;
	char ch;//用于扫描括号型表示字符串
	b = NULL;
	ch = str[j];
	p = (btNodeT*)malloc(sizeof(btNodeT));
	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':
			top++;
			stack[top] = p;
			k = 1;
			break;
		case ')':
			top--;
			break;
		case ',':
			k = 2;
			break;
		default:
			p = (btNodeT*)malloc(sizeof(btNodeT));
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (b == NULL)
				b = p;
			else
			{
				if (k == 1)
					stack[top]->lchild = p;
				if (k == 2)
					stack[top]->rchild = p;
			}
		}
		j++;
		ch = str[j];
	}
}

接下来先实现中序线索化

void ThreadIn(btNodeT*& p) //将节点p的子树添加线索
{
	if (p != NULL)
	{
		ThreadIn(p->lchild);
		if (p->lchild == NULL)
		{
			p->ltag = 1;
			p->lchild = pre;
		}
		else
			p->ltag = ;
		if (pre->rchild == NULL)
		{
			pre->rchild = p;
			pre->rtag = 1;
		}
		else
			pre->rtag = ;
		pre = p;
		ThreadIn(p->rchild);
	}
}
btNodeT* createThreadIn(btNodeT* b)  //添加一个头结点，并线索化
{
	btNodeT* root;
	root = (btNodeT*)malloc(sizeof(root));
	root->ltag = ;
	root->rtag = 1;
	root->rchild = b;
	if (b == NULL)
		root->lchild = root;
	else
	{
		root->lchild = b;
		pre = root;
		ThreadIn(b);
		pre->rtag = 1;
		pre->rchild = root;
		root->rchild = pre;
	}
	return root;
}

遍历中序线索化二叉树

void inOrderT(btNodeT* root)  //遍历中序线索化二叉树
{
	btNodeT* p;
	p = root->lchild;
	while (p != root)
	{
		while (p->ltag == )
			p = p->lchild;
		cout << p->data;
		while (p->rtag == 1 && p->rchild != root)
		{
			p = p->rchild;
			cout << p->data;
		}
		p = p->rchild;
	}
}

下面给出先序线索化二叉树

void ThreadPre(btNodeT*& p)
{
	if (p != NULL)
	{
		if (p->lchild == NULL)
		{
			p->ltag = 1;
			p->lchild = pre;
		}
		else
			p->ltag = ;
		if (pre->rchild == NULL)
		{
			pre->rtag = 1;
			pre->rchild = p;
		}
		else
			pre->rtag = ;
		pre = p;
		if (p->ltag == )
			ThreadPre(p->lchild);
		if (p->rtag != 1)
			ThreadPre(p->rchild);
	}
}
btNodeT* createThreadPre(btNodeT* b)
{
	btNodeT* root;
	root = (btNodeT*)malloc(sizeof(root));
	root->ltag = ;
	root->rtag = 1;
	root->rchild = b;
	if (b == NULL)
		root->lchild = root;
	else
	{
		root->lchild = b;
		pre = root; 
		ThreadPre(b); 
		pre->rtag = 1;
		pre->rchild = root;
		root->rchild = pre;
	}
	
	return root;
}
void preOrderT(btNodeT* root) //遍历
{
	btNodeT* p;
	p = root->lchild;
	while (p != root)
	{
		cout << p->data;
		while (p->ltag == )
		{
			p = p->lchild;
			cout << p->data;
		}
		p = p->rchild;
	}
}

最后是后序线索化二叉树。

void ThreadPost(btNodeT*& p)
{
	if (p != NULL)
	{
		pre = p;
		ThreadPre(p->lchild);
		ThreadPre(p->rchild);
		if (p->lchild == NULL)
		{
			p->ltag = 1;
			p->lchild = pre;
		}
		else
			p->ltag = ;
		if (pre->rchild == NULL)
		{
			pre->rtag = 1;
			pre->rchild = p;
		}
		else
			pre->rtag = ;
	}
}
btNodeT* createThreadPost(btNodeT* b)
{
	btNodeT* root;
	root = (btNodeT*)malloc(sizeof(root));
	root->ltag = ;
	root->rtag = 1;
	root->rchild = b;
	if (b == NULL)
		root->lchild = root;
	else
	{
		root->lchild = b;
		pre = root;
		ThreadPost(b);
		pre->rtag = 1;
		pre->rchild = root;
		root->rchild = pre;
	}

	return root;
}

如果存在某一个子树包含A（B（D，E），C）的结构，则后序遍历的顺序是D-E-B，接下来我们发现B没有指向C的指针，因此我们需要一个指针指向父母结点，而我们的结点定义中不包括这个，因而后序线索化二叉树的遍历方法很难给出。

ITPub博客

数据结构与算法实现（7）——线索化二叉树

最新文章