数据结构——线索二叉树

在二叉树中，查找某种遍历（如前中后序遍历、层次遍历）的前驱后继，在普通的二叉树结构中会显得很麻烦。有两种方法可以解决。

1.增加前驱后继两个指针，这样大大增加了空间消耗，不太可取。

2.将结点结构变为如下结构。若结点有左子树，left指向左孩子否则指向某种遍历的前驱。

若结点有右子树，right指向右孩子，否则指向某种遍历的后继。

这样，中序遍历的一个线索二叉树结构为：

将一个二叉树中序线索化，类似中序遍历，假如该结点有左节点，向左节点递归。

没有左节点时，对该结点进行一系列 *** 作，再向其右节点递归。

最左下边的前驱和最右下的后继为nullptr。

 考虑一个结点的前驱，两种情况。

1.left不是左孩子，则其left是前驱，直接返回。

2.如果是左孩子，则其前驱是其左孩子的最右下孩子的结点

后继同理。

#pragma once
#include
#include
#include
template
class tbinary_tree
{
public:
	struct node
	{
		T data;
		node* left;
		node* right;
		bool l_mark;
		bool r_mark;
		node() = default;
		node(const T& d, node* const l = nullptr, node* const r = nullptr)
		{
			data = d; left = l; right = r;
			l_mark = false;
			r_mark = false;
		}
	};
	node* root;
	tbinary_tree() :root(nullptr) {}
	~tbinary_tree() { p_clear(root); }
	void inThread() ;//将二叉树线索化
	node* last(node* current);//求前驱
	node* next(node* current);//求后继
	void inorder() { p_inorder(root); };//特有中序遍历
private:
	//名字前面有个p表示私有private
	void p_clear(node* root);//删除所有结点
	void p_inThread(node* current, node*& pre);
	void p_inorder(node* root);
};
template
void tbinary_tree::inThread()
{
	node* pre = nullptr;
	if (root)
	{
		p_inThread(root, pre);
		pre->right = nullptr;
		pre->r_mark = true;
	}
}
template
void tbinary_tree::p_inThread(node* current, node*& pre)
{
	if (!current)
		return;
	p_inThread(current->left, pre);
	if (!current->left)
	{
		current->left = pre;
		current->l_mark = true;
	}
	if (pre && !pre->right)
	{
		pre->right = current;
		pre->r_mark = true;
	}
	pre = current;
	p_inThread(current->right, pre);
}
template
typename tbinary_tree::node* tbinary_tree::last(node* current)
{
	node* p = current->left;
	if (!current->l_mark)
	{
		while (!p->r_mark)
			p = p->right;
	}
	return p;
}
template
typename tbinary_tree::node* tbinary_tree::next(node* current)
{
	node* p = current->right;
	if (!current->r_mark)
	{
		while (!p->l_mark)
			p = p->left;
	}
	return p;
}
template
void tbinary_tree::p_inorder(node* root)
{
	//当然也可以按普通二叉树遍历,以下是线索二叉树特有的遍历
	if (!root)
		return;
	node* p = root;
	while (p->left)
		p = p->left;
	if(p->r_mark)
		std::cout << p->data << " ";
	node* q = next(p);
	while (q)
	{
		std::cout << q->data << " ";
		q = next(q);
	}
	//另一种方式
	/*
	node* p = root;
	while (p)
	{
		while (!p->l_mark)
			p = p->left;
		std::cout << p->data;
		while (p && p->r_mark)
		{
			p = p->right;
			if (p)
				std::cout << p->data;
		}
		if (p)
			p = p->right;
	}*/
}
template
void tbinary_tree::p_clear(node* root)
{
	if (!root)//结点为空就返回
 		return;
	node* p = root;
	while (p->left)
		p = p->left;
	node* q = next(p);
	delete p;
	while (q)
	{
		p = q;
		q = next(q);
		delete p;
	}
}