Thread Binary Tree

线索二叉树的结点类

template <class T>
class ThreadBinaryTreeNode
{
	friend class ThreadBinaryTree<T>;
private:
	int leftTag, rightTag;
	ThreadBinaryTreeNode<T> *leftChild;
	ThreadBinaryTreeNode<T> *rightChild;
	T element;
public:
	ThreadBinaryTreeNode();
	ThreadBinaryTreeNode(const T &ele);
	ThreadBinaryTreeNode(const T &ele, ThreadBinaryTreeNode<T> *l, ThreadBinaryTreeNode<T> *r);
	ThreadBinaryTreeNode<T> *getLeftChild() const;
	ThreadBinaryTreeNode<T> *getRightChild() const;
	void setLeftChild(ThreadBinaryTreeNode<T> *l);
	void setRightChild(ThreadBinaryTreeNode<T> *r);
	T getValue() const;
	void setValue(const T &val);
};

线索二叉树类

template <class T>
class ThreadBinaryTree
{
private:
	ThreadBinaryTreeNode<T> *root;
public:
	ThreadBinaryTree();
	ThreadBinaryTree(ThreadBinaryTreeNode<T> *r);
	~ThreadBinaryTree();
	ThreadBinaryTreeNode<T> *getRoot();
	void InThread(ThreadBinaryTreeNode<T> *root, ThreadBinaryTreeNode<T> *pre);
	void InOrder(ThreadBinaryTreeNode<T> *root);
};

中序线索化二叉树

template <class T>
void ThreadBinaryTree<T>::InThread(ThreadBinaryTreeNode<T> *root, ThreadBinaryTreeNode<T> *pre)
{
	ThreadBinaryTreeNode<T> *current;
	current = root;
	if (current)
	{
		InThread(current->leftChild, pre);
		if (!current->leftChild)
		{
			current->leftChild = pre;
			current->leftTag = 1;
		}
		if ((pre) && (!pre->rightChild))
		{
			pre->rightChild = root;
			pre->rightTag = 1;
		}
		pre = current;
		InThread(current->rightChild, pre);
	}
}

中序遍历线索二叉树

template <class T>
void ThreadBinaryTree<T>::InOrder(ThreadBinaryTreeNode<T> *root)
{
	ThreadBinaryTreeNode<T> *current;
	current = root;
	while (!current->leftTag)
		current = current->leftChild;
	while (current)
	{
		visit(current);
		if (current->rightTag)
			current = current->rightChild;
		else
		{
			current = current->rightChild;
			while (current && !current->leftTag)
				current = current->leftChild;
		}
	}
}