threadbintree.h

实现了线索化二叉树

/*--------------------------------------------------------
文件名:ThreadBinTree.h
作用：定义了线索二叉树
作者：谢亚龙
创建日期：2008年5月23日
最后修改日期：2008年5月24日
--------------------------------------------------------*/
#ifndef _THREADBINTREE
#define _THREADBINTREE

#include "stdafx.h"
#include "ThreadBinTreeNode.h"
#include <stack>
#include <iostream>
using namespace std;

template <class Elem>
class ThreadBinTree
{
private:
	ThreadBinTreeNode<Elem>* root;//树根节点
	void DeleteAll(ThreadBinTreeNode<Elem>* p)//删除以p为根的子树
	{
		if(!p)//如果p为空，返回
			return;
		DeleteAll(p->Left());//删除p的左子树
		DeleteAll(p->Right());//删除p的右子树
		delete p;//删除p节点本身
	}

	ThreadBinTreeNode<Elem>* Create(Elem& ch)//供内部使用的建树函数
	{
		//构建二叉树，当输入的为ch时，构建空二叉树	
		Elem i;
		cin >> i;
		if(i != ch)
		{
			//如果输入的不是结束标志，则表示继续构造
			ThreadBinTreeNode<Elem>* temp = new ThreadBinTreeNode<Elem>(i);
			temp->SetLeft(Create(ch));		//构建左子树
			temp->SetRight(Create(ch));		//构建右子树
			return temp;						//返回根节点
		}
		return NULL;	//当得到的是结束符时，表示此子树构建完成,返回空子树
	}

	void InThread(ThreadBinTreeNode<Elem>* root,ThreadBinTreeNode<Elem>* &pre)
	{
		//供内部使用的中序线索化一棵二叉树，root为该树节点 pre为前驱节点
		if(root)//树不为空
		{
			InThread(root->Left(),pre);//先线索化左子树
			if(!root->Left())//左子树为空
			{
				root->SetLeft(pre);//左指针指向其前驱
				if(pre)//前驱不为空
					root->LTag(true);
			}
			if( pre && !pre->Right())//前驱不为空 且 前驱的右子树为空
			{
				pre->SetRight(root);//把前驱的 右指针指向root节点，作为pre的后继
				pre->RTag(true);//改变右标记位的值
			}
			pre = root;
			InThread(root->Right(),pre);//再线索化右子树
		}
	}

public:
	ThreadBinTree():root(NULL){};//缺省构造函数
	~ThreadBinTree()//析构函数
	{
		DeleteAll(root);
	}

	void CreateTree(Elem& ch)//供外部使用的建树函数,ch是建树结束符
	{
		//得到的树的根赋值给 root就好了
		root = Create(ch);
//		InThread();//构建好树之后 立即线索化
		InThreadWithStack();
	}

	ThreadBinTreeNode<Elem>* GetRoot()const//返回根节点
	{
		return root;
	}

	void InThread()//供外部使用的线索化二叉树
	{
		ThreadBinTreeNode<Elem>* pre = NULL;//第一个前驱节点的值为空
		InThread(root,pre);//调用内部的线索化函数，以树根为节点
	}

	void InOrder()//中序周游线索化二叉树
	{
		if(!root)//为空树
			return;
		ThreadBinTreeNode<Elem>* temp = root;
		while(temp->Left())//当temp->left没指空时
			temp = temp->Left();
		while(1)
		{
			Visit(temp);//访问的都是 最左节点
			if(!temp->Right())//如果temp右指针指空，则表示temp为线索化的最后的一个右节点的后继
				return;
			if(temp->RTag())//为后继，则按照后继移动即可
				temp = temp->Right();
			else
			{
				temp = temp->Right();//上面的各步都是temp为左的情况
				while(!temp->LTag())//当左标记位表示为 左子节点时
					temp = temp->Left();
			}
		}
	}

	void Visit(ThreadBinTreeNode<Elem>* temp)//访问当前节点
	{
		if(!temp)//为空节点
			return;
		cout << temp->GetValue() << " ";
	}

	void InThreadWithStack()//用非递归实现中序线索化二叉树
	{
		if(!root)//为空树
			return;
		ThreadBinTreeNode<Elem>* pre = NULL;//第一个前驱节点的值为空
		ThreadBinTreeNode<Elem>* temp = root;
		stack<ThreadBinTreeNode<Elem>*> s;
		while(temp != NULL || !s.empty())//当 当前节点不为空 或 栈不为空时循环
		{
			if(temp != NULL)//当前节点不为空
			{
				s.push(temp);//入栈
				temp = temp->Left();
			}
			else
			{
				temp = s.top();//的到栈顶元素的值
				if(pre && !pre->Right())//前驱不为空，且前驱的右指针为空时
				{
					pre->SetRight(temp);//得到 pre 的后继节点为 当前节点
					pre->RTag(true);//改变标记位
				}
				s.pop();//栈顶元素出栈
				if(!temp->Left())//当弹出的元素的左指针为空
				{
					temp->SetLeft(pre);
					if(pre)//如果前驱指针不为空，则改变其左标记位
						temp->LTag(true);
				}
				pre = temp;
				temp = temp->Right();
			}
			
		}
	}


};

#endif