C++-线索二叉树【中序线索二叉树构造与遍历】

     ，花了好几个个小时，看了线索二叉树的构造，感觉是挺简单的…但是，上手写中序线索二叉树的构造代码时，，，算法流程没错，代码没错，愣是构造不出来子树下面的右孩子结点对应的后继线索，后来设置了将其中的一个参数前置结点preNode作为类的成员变量拿出去，总算构造出来了。。。

• 1 线索二叉树结点定义
• 2 线索二叉树类定义
• 3 代码测试
• 4 测试结果

#include 
using namespace std;


template 
class ThreadNode{
public:
	//setter
	void setData(T data){
		if (typeid(data)==typeid(char))
		{
			this->data=data;
			return;
		}
		std::cout<<"The Type is Wrong!"<lchild=lchild;
	}
	void setRchild(ThreadNode* rchild){
			this->rchild=rchild;
	}
	void setLTag(int ltag){ this->ltag=ltag; }
	void setRTag(int rtag){ this->rtag=rtag; }
	//getter
	T getData(){
		return this->data;
	}
	ThreadNode* getLchild(){
		return this->lchild;
	}
	ThreadNode* getRchild(){
		return this->rchild;
	}
	int getLTag(){ return this->ltag; }
	int getRTag(){ return this->rtag; }
	//constructor
	ThreadNode(){
		this->setData(0);
		this->lchild=NULL;
		this->rchild=NULL;
		this->rtag=0;
		this->ltag=0;
	}
	ThreadNode(T data){
		this->setData(data);
		this->lchild=NULL;
		this->rchild=NULL;
		this->rtag=0;
		this->ltag=0;
	}
	//methods
	void visit(){
		//std::cout<<" "<data<<" "<data<<"tlchild:";
		if (this->lchild==NULL)
			std::cout<<"NULL"<<"trchild:";
		else
			std::cout<lchild->getData()<<"trchild:";
		if (this->rchild==NULL)
			std::cout<<"NULL"<<"tltag="<ltag<<"trtag="<rtag<rchild->getData()<<"tltag="<ltag<<"trtag="<rtag<visit();
		if (this->lchild!=NULL)
		{
			this->lchild->preOrder();
		}
		if (this->rchild!=NULL)
		{
			this->rchild->preOrder();
		}
	}

	//中序遍历
	void inOrder(){
		if (this->lchild!=NULL)
		{
			this->lchild->inOrder();
		}
		this->visit();
		//this->toString();
		if (this->rchild!=NULL)
		{
			this->rchild->inOrder();
		}
	}

	//后序遍历
	void postOrder(){
		if (this->lchild!=NULL)
		{
			this->lchild->postOrder();
		}
		if (this->rchild!=NULL)
		{
			this->rchild->postOrder();
		}
		this->visit();
	}

	
	ThreadNode* FirstNode(ThreadNode* p){
		while (p->ltag==0) p=p->getLchild();//ltag为0-指向左子树
		return p;
	}

	
	ThreadNode* NextNode(ThreadNode* p){
		if (p->rtag==0) return this->FirstNode(p->getRchild());//rtag为0-指向右子树
		return p->getRchild();
	}

	
	void inOrderThread(ThreadNode* tree){
		if (tree!=NULL)
		{
			for (ThreadNode* p=FirstNode(tree);p!=NULL;p=NextNode(p))
				p->visit();
		}
	}

	//toString
	void toString(){
		std::cout<<"data:"<data<<"tlchild:"<lchild<<"trchild:"<rchild<<"tltag="<ltag<<"trtag="<rtag< 
2 线索二叉树类定义 
#include "ThreadNode.h"
#include "linkedQueue.h"
#include "linkedStack.h"


template 
class ThreadTree{
public:
	//setter
	void setRoot(ThreadNode* root){
		if (root!=NULL)
		{
			this->root=root;
			return;
		}
		std::cout<<"Root Is Not NULL!"<* getRoot(){
		return this->root;
	}
	//constructor
	ThreadTree(){
		this->root=NULL;
		this->preNode=NULL;
	}
	ThreadTree(ThreadNode* root){
		this->root=root;
		this->preNode=NULL;
	}

	
	void preOrder(){
		if (this->root!=NULL)
		{
			this->root->preOrder();
		}
	}

	
	void inOrder(){
		if (this->root!=NULL)
		{
			this->root->inOrder();
		}
	}

	
	void postOrder(){
		if (this->root!=NULL)
		{
			this->root->postOrder();
		}
	}

	
	void levelOrder(){
		if (this->root!=NULL)
		{
			linkedQueue*>* Q=new linkedQueue*>;//初始化队列
			//判断队列是否初始化成功
			if (Q==NULL) return;
			ThreadNode* p=this->root;//工作指针
			Q->enQueue(p); //根结点入队
			while (!Q->isEmpty())
			{
				Q->deQueue(p);//队首节点出队
				p->visit();//访问结点
				if (p->getLchild()) Q->enQueue(p->getLchild());
				if (p->getRchild()) Q->enQueue(p->getRchild());
			}
			//释放队列
			if (Q!=NULL) delete Q;
		}
	}

	
	void preOrderWithStack(){
		if (this->root!=NULL)
		{
			linkedStack*>* S=new linkedStack*>;//初始化栈
			if (S==NULL) return;
			ThreadNode* p=this->root;//工作指针
			//循环-前序遍历非递归实现
			while (p!=NULL||!S->isEmpty())
			{
				if (p!=NULL)
				{
					p->visit();//访问根节点
					S->PushlinkedStack(p);//p结点进栈
					p=p->getLchild();//遍历左子树
				}else
				{
					S->PoplinkedStack(p);//栈顶元素出栈-当前子树的根节点
					p=p->getRchild();
				}//if
			}//while
			if (S!=NULL) delete S;
		}//if
	}

	
	void inOrderWithStack(){
		if (this->root!=NULL)
		{
			linkedStack*>* S=new linkedStack*>;//初始化栈
			if (S==NULL) return;
			ThreadNode* p=this->root;//工作指针
			//循环-中序遍历非递归实现
			while (p!=NULL||!S->isEmpty())
			{
				if (p!=NULL)
				{
					S->PushlinkedStack(p);//当前子树根结点入栈
					p=p->getLchild();//遍历左子树
				}else
				{
					S->PoplinkedStack(p);//当前子树根结点出栈
					p->visit();//访问当前结点
					p=p->getRchild();//遍历右子树
				}//if
			}//while
			if (S!=NULL) delete S;
		}
	}

	
	void postOrderWithStack(){
		if (this->root!=NULL)
		{
			linkedStack*>* S=new linkedStack*>;//初始化栈
			ThreadNode* p=this->root;//工作指针
			ThreadNode* r=NULL;//记录最近一次被访问的结点
			//循环-后序遍历非递归算法实现
			while (p!=NULL||!S->isEmpty())
			{
				if (p!=NULL)
				{
					S->PushlinkedStack(p);//当前子树根结点入栈
					p=p->getLchild();//遍历左子树
				}else
				{
					p=S->getTop()->getData();//获取栈顶结点
					if (p->getRchild()!=NULL&&p->getRchild()!=r)
						p=p->getRchild();
					else
					{
						S->PoplinkedStack(p);//获取当前子树根结点
						p->visit();//访问当前子树根结点
						r=p;
						p=NULL;
					}//-if
				}//if
			}//while
			if (S!=NULL) delete S;
		}
	}

	
	void InOrderThreaded(){
		ThreadNode* p=this->root;
		if (p!=NULL)
		{
			this->InOrderThread(p);//非空二叉树-线索化
		}
	}

	
	void InOrderThread(ThreadNode* p){
		if (p!=NULL)
		{
			//当前结点this不为空
			InOrderThread(p->getLchild());//线索化左子树
			//处理当前结点
			if (p->getLchild()==NULL)//左子树为空-指向前驱结点
			{
				std::cout<getData()<setLchild(this->preNode);
				p->setLTag(1);//标志阈置为-1
			}
			if (this->preNode!=NULL&&this->preNode->getRchild()==NULL)//右子树为空-指向后继结点
			{
				std::cout<preNode->getData()<preNode->setRchild(p);
				this->preNode->setRTag(1);
			}
			this->preNode=p;//修改前驱结点
			InOrderThread(p->getRchild());//线索化右子树
		}//if
	}


	
	void inOrderThread(){
		if (this->root!=NULL)
		{
			this->root->inOrderThread(this->root);
		}
	}

protected:

private:
	ThreadNode* root;//线索二叉树根节点
	ThreadNode* preNode;
};
 
3 代码测试 
#include "ThreadTree.h"

void ThreadTree_test(){
	//创建结点
	ThreadNode* A=new ThreadNode('A');
	ThreadNode* B=new ThreadNode('B');
	ThreadNode* C=new ThreadNode('C');
	ThreadNode* D=new ThreadNode('D');
	ThreadNode* E=new ThreadNode('E');
	ThreadNode* G=new ThreadNode('G');
	//设置结点间的关系
	B->setLchild(D);
	B->setRchild(E);
	C->setRchild(G);
	A->setLchild(B);
	A->setRchild(C);
	//创建线索二叉树
	ThreadTree* tTree=new ThreadTree;
	tTree->setRoot(A);
	//std::cout<
	//tTree->preOrder();//前序遍历
	//tTree->inOrder();//中序遍历
	//tTree->postOrder();//后序遍历
	//tTree->levelOrder();//层序遍历
	//tTree->inOrderWithStack();//中序遍历非递归实现
	//tTree->preOrderWithStack();//前序遍历非递归实现
	//tTree->postOrderWithStack();//后序遍历非递归实现
	tTree->InOrderThreaded();//中序遍历-线索化
	//tTree->preOrderThread();
	std::cout<<"前序遍历-线索化完毕！"<inOrderThread();
	tTree->inOrderThread();//中序遍历
	//打印结点
	//A->toString();
	//B->toString();
	//C->toString();
	//D->toString();
	//E->toString();
	//G->toString();

}


int main(int argc,char** argv){
	ThreadTree_test();

	return 0;
}
 
4 测试结果