190-线索二叉树.md

一：背景

线索二叉树的定义为：一个二叉树通过如下的方法“穿起来”：所有应该为空的右孩子指针指向该结点在中序序列中的后继，所有应该为空的左孩子指针指向该结点的中序序列的前驱。

那么在有N个结点的二叉树中共有N+1个空指针，这些空指针就叫做“线索”。（提示：在一个有N个结点的二叉树中，每个结点有2个指针，所以一共有2N个指针，将这N个结点连接起来需要N-1条线，即使用了N-1个指针。所以剩下2N-(N-1)=N+1个空指针。）

那线索二叉树有何用处呢？由于巧妙地利用了空指针，所以它可以快速地查找到二叉树中某结点的前驱和后继。接下来具体介绍这个数据结构。

在进行下文之前，约定如下：

struct Node
{
	bool left_thread;
	bool right_thread;
	char data;
	Node * left;
	Node * right;

	Node()
	{
		left_thread = right_thread = false;
		data = 0;
		left = right = nullptr;
	}
};

class ThreadedBinaryTree
{
public:
	ThreadedBinaryTree();
	Node * create();
	void threaded(Node * cur, Node *& pre);  // 线索化
	void formLoop();                         // 构环
	Node * get_successor(Node * node);       // 返回后继结点
	Node * get_precursor(Node * node);       // 返回前驱结点
	void in_order_print();                   // 中序遍历
private:
	Node * header;  // 头结点
	Node * root;    // 二叉树根结点
};

请注意，在决定left是指向左孩子还是前驱，right是指向右孩子还是后继，我们是需要一个区分标志的。因此我们在Node结构体中增设两个布尔变量left_thread和right_thread，其中： （1）：left_thread为true时指向前驱，为false时指向该结点的左子树； （2）：right_thread为true时指向后继，为false时指向该结点的右子树。

二：具体实现与代码分析

2.1 构造二叉树

ThreadedBinaryTree::ThreadedBinaryTree()
{
	root = create();
}

Node * ThreadedBinaryTree::create()
{
	Node * p = nullptr;
	char ch;
	cin >> ch;
  
	if (ch == '.')  // 结束输入
		p = nullptr;
	else
	{
		p = new Node;
		p->data = ch;
		p->left = create();
		p->right = create();
	}
  
	return p;
}

2.2 线索化及二叉树构环

void ThreadedBinaryTree::threaded(Node * cur, Node *& pre)
{
	if (cur == nullptr)
		return;
	else
	{
		// 按照中序遍历方向，先处理左子树
		threaded(cur->left, pre);

		// 再处理当前结点
		if (cur->left == nullptr)
		{
			cur->left_thread = true;
			cur->left = pre;
		}
		if (cur->right == nullptr)
			cur->right_thread = true;
		if (pre->right_thread)
			pre->right = cur;
		pre = cur;

		// 最后处理右子树
		threaded(cur->right, pre);
	}
}

void ThreadedBinaryTree::formLoop()
{
	header = new Node;  // 创建头结点，并完成初始化
	header->left_thread = true;
	header->right_thread = true;
	header->left = header->right = header;

	Node * pre = header;  // 记录中序遍历的前一个结点
	threaded(root, pre);  // 进行线索化

	pre->right_thread = true;  // 线索化完后，把中序遍历的最后一个结点即 pre，指向 header
	pre->right = header;
	header->left = pre;  // 注意，header 的左指针指向中序遍历的最后一个
}

header结点的作用就是把线索化后的二叉树串起来，形成一个环。header的左孩子指向中序遍历序列的最后一个结点，右孩子指向中序遍历序列的第一个结点，如下图：

2.3 后继和前驱

Node * ThreadedBinaryTree::get_successor(Node * node)
{
	if (node->right_thread)
		return node->right;
  
	Node * p = node->right;
	while (p->left_thread == false)  // 已线索化，故此处只能用 left_thread 来判断左子树的情况
		p = p->left;
  
	return p;
}

Node * ThreadedBinaryTree::get_precursor(Node * node)
{
	if (node->left_thread)
		return node->left;
  
	Node * p = node->left;
	while (p->right_thread == false)  // 已线索化，故此处只能用 right_thread 来判断右子树的情况
		p = p->right;
  
	return p;
}

2.4 中序遍历

void ThreadedBinaryTree::in_order_print()
{
	cout << "中序遍历为：";
	Node * p = header->right;  // header 的右结点指向二叉树中序遍历的第一个结点
  
	while (p != header)
	{
		cout << p->data << " ";
		p = get_successor(p);
	}
  
	cout << endl;
}

三：完整代码

/**
 *
 * author : 刘毅（Limer）
 * date   : 2017-03-26
 * mode   : C++
 */

#include <iostream>

using namespace std;

struct Node
{
	bool left_thread;
	bool right_thread;
	char data;
	Node * left;
	Node * right;

	Node()
	{
		left_thread = right_thread = false;
		data = 0;
		left = right = nullptr;
	}
};

class ThreadedBinaryTree
{
public:
	ThreadedBinaryTree();
	Node * create();
	void threaded(Node * cur, Node *& pre);  // 线索化
	void formLoop();                         // 构环
	Node * get_successor(Node * node);       // 返回后继结点
	Node * get_precursor(Node * node);       // 返回前驱结点
	void in_order_print();                   // 中序遍历
private:
	Node * header;  // 头结点
	Node * root;    // 二叉树根结点
};

int main()
{

	ThreadedBinaryTree my_tree;
	my_tree.formLoop();
	my_tree.in_order_print();

	return 0;
}

ThreadedBinaryTree::ThreadedBinaryTree()
{
	root = create();
}

Node * ThreadedBinaryTree::create()
{
	Node * p = nullptr;
	char ch;
	cin >> ch;
  
	if (ch == '.')  // 结束输入
		p = nullptr;
	else
	{
		p = new Node;
		p->data = ch;
		p->left = create();
		p->right = create();
	}
  
	return p;
}

void ThreadedBinaryTree::threaded(Node * cur, Node *& pre)
{
	if (cur == nullptr)
		return;
	else
	{
		// 按照中序遍历方向，先处理左子树
		threaded(cur->left, pre);

		// 再处理当前结点
		if (cur->left == nullptr)
		{
			cur->left_thread = true;
			cur->left = pre;
		}
		if (cur->right == nullptr)
			cur->right_thread = true;
		if (pre->right_thread)
			pre->right = cur;
		pre = cur;

		// 最后处理右子树
		threaded(cur->right, pre);
	}
}

void ThreadedBinaryTree::formLoop()
{
	header = new Node;  // 创建头结点，并完成初始化
	header->left_thread = true;
	header->right_thread = true;
	header->left = header->right = header;

	Node * pre = _header;  // 记录中序遍历的前一个结点
	threaded(root, pre);   // 进行线索化

	pre->right_thread = true;  // 线索化完后，把中序遍历的最后一个结点即 pre，指向 header
	pre->right = header;
	header->left = pre;  // 注意，header 的左指针指向中序遍历的最后一个
}

Node * ThreadedBinaryTree::get_successor(Node * node)
{
	if (node->right_thread)
		return node->right;
  
	Node * p = node->right;
	while (p->left_thread == false)  // 已线索化，故此处只能用 left_thread 来判断左子树的情况
		p = p->left;
  
	return p;
}

Node * ThreadedBinaryTree::get_precursor(Node * node)
{
	if (node->left_thread)
		return node->left;
  
	Node * p = node->left;
	while (p->right_thread == false)  // 已线索化，故此处只能用 right_thread 来判断右子树的情况
		p = p->right;
  
	return p;
}

void ThreadedBinaryTree::in_order_print()
{
	cout << "中序遍历为：";
	Node * p = header->right;  // header 的右结点指向二叉树中序遍历的第一个结点
  
	while (p != header)
	{
		cout << p->data << " ";
		p = get_successor(p);
	}
  
	cout << endl;
}

以（2.2）中的图为例，输入数据及测试结果为：