您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

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

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

中序线索二叉树构造与遍历

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

1 线索二叉树结点定义

#include <iostream>
using namespace std;

/**
* 线索二叉树结点定义
*/
template <typename T>
class ThreadNode{
public:
	//setter
	void setData(T data){
		if (typeid(data)==typeid(char))
		{
			this->data=data;
			return;
		}
		std::cout<<"The Type is Wrong!"<<std::endl;
	}
	void setLchild(ThreadNode* lchild){
			this->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<T>* getLchild(){
		return this->lchild;
	}
	ThreadNode<T>* 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<<" "<<this->data<<" "<<std::endl;
		std::cout<<"data:"<<this->data<<"\tlchild:";
		if (this->lchild==NULL)
			std::cout<<"NULL"<<"\trchild:";
		else
			std::cout<<this->lchild->getData()<<"\trchild:";
		if (this->rchild==NULL)
			std::cout<<"NULL"<<"\tltag="<<this->ltag<<"\trtag="<<this->rtag<<std::endl;
		else
			std::cout<<this->rchild->getData()<<"\tltag="<<this->ltag<<"\trtag="<<this->rtag<<std::endl;
	}

	//前序遍历
	void preOrder(){
		this->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<T>* FirstNode(ThreadNode<T>* p){
		while (p->ltag==0) p=p->getLchild();//ltag为0-指向左子树
		return p;
	}

	/**
	 * 线索二叉树中结点p在中序序列下的后继结点
	 */
	ThreadNode<T>* NextNode(ThreadNode<T>* p){
		if (p->rtag==0) return this->FirstNode(p->getRchild());//rtag为0-指向右子树
		return p->getRchild();
	}

	/**
	 * 线索中序遍历
	 */
	void inOrderThread(ThreadNode<T>* tree){
		if (tree!=NULL)
		{
			for (ThreadNode<T>* p=FirstNode(tree);p!=NULL;p=NextNode(p))
				p->visit();
		}
	}

	//toString
	void toString(){
		std::cout<<"data:"<<this->data<<"\tlchild:"<<this->lchild<<"\trchild:"<<this->rchild<<"\tltag="<<this->ltag<<"\trtag="<<this->rtag<<std::endl;
	}

protected:

private:
	T data;//数据域
	ThreadNode* lchild;//左孩子结点
	ThreadNode* rchild;//右孩子结点
	int ltag;//左孩子结点-标志阈
	int rtag;//右孩子结点-标志阈
};


2 线索二叉树类定义

#include "ThreadNode.h"
#include "LinkedQueue.h"
#include "LinkedStack.h"

/**
* 线索二叉树定义
*/
template <typename T>
class ThreadTree{
public:
	//setter
	void setRoot(ThreadNode<T>* root){
		if (root!=NULL)
		{
			this->root=root;
			return;
		}
		std::cout<<"Root Is Not NULL!"<<std::endl;
	}
	//getter
	ThreadNode<T>* getRoot(){
		return this->root;
	}
	//constructor
	ThreadTree(){
		this->root=NULL;
		this->preNode=NULL;
	}
	ThreadTree(ThreadNode<T>* 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<ThreadNode<T>*>* Q=new LinkedQueue<ThreadNode<T>*>;//初始化队列
			//判断队列是否初始化成功
			if (Q==NULL) return;
			ThreadNode<T>* 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<ThreadNode<T>*>* S=new LinkedStack<ThreadNode<T>*>;//初始化栈
			if (S==NULL) return;
			ThreadNode<T>* 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<ThreadNode<T>*>* S=new LinkedStack<ThreadNode<T>*>;//初始化栈
			if (S==NULL) return;
			ThreadNode<T>* 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<ThreadNode<T>*>* S=new LinkedStack<ThreadNode<T>*>;//初始化栈
			ThreadNode<T>* p=this->root;//工作指针
			ThreadNode<T>* 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<T>* p=this->root;
		if (p!=NULL)
		{
			this->InOrderThread(p);//非空二叉树-线索化
		}
	}

	/**
	* 中序遍历线索化
	* 原来的方法定义-void InOrderThread(ThreadNode<T>* p,ThreadNode<T>* preNode)
	* 用原来的方法,无论怎么调试,结果就是不对
	*/
	void InOrderThread(ThreadNode<T>* p){
		if (p!=NULL)
		{
			//当前结点this不为空
			InOrderThread(p->getLchild());//线索化左子树
			//处理当前结点
			if (p->getLchild()==NULL)//左子树为空-指向前驱结点
			{
				std::cout<<p->getData()<<std::endl;
				p->setLchild(this->preNode);
				p->setLTag(1);//标志阈置为-1
			}
			if (this->preNode!=NULL&&this->preNode->getRchild()==NULL)//右子树为空-指向后继结点
			{
				std::cout<<this->preNode->getData()<<std::endl;
				this->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<T>* root;//线索二叉树根节点
	ThreadNode<T>* preNode;
};

3 代码测试

#include "ThreadTree.h"

void ThreadTree_test(){
	//创建结点
	ThreadNode<char>* A=new ThreadNode<char>('A');
	ThreadNode<char>* B=new ThreadNode<char>('B');
	ThreadNode<char>* C=new ThreadNode<char>('C');
	ThreadNode<char>* D=new ThreadNode<char>('D');
	ThreadNode<char>* E=new ThreadNode<char>('E');
	ThreadNode<char>* G=new ThreadNode<char>('G');
	//设置结点间的关系
	B->setLchild(D);
	B->setRchild(E);
	C->setRchild(G);
	A->setLchild(B);
	A->setRchild(C);
	//创建线索二叉树
	ThreadTree<char>* tTree=new ThreadTree<char>;
	tTree->setRoot(A);
	//std::cout<<A<<std::endl;
	//tTree->preOrder();//前序遍历
	//tTree->inOrder();//中序遍历
	//tTree->postOrder();//后序遍历
	//tTree->levelOrder();//层序遍历
	//tTree->inOrderWithStack();//中序遍历非递归实现
	//tTree->preOrderWithStack();//前序遍历非递归实现
	//tTree->postOrderWithStack();//后序遍历非递归实现
	tTree->InOrderThreaded();//中序遍历-线索化
	//tTree->preOrderThread();
	std::cout<<"前序遍历-线索化完毕!"<<std::endl;
	/*std::cout<<tTree->getRoot()->FirstNode(tTree->getRoot())->getData()<<std::endl;
	std::cout<<tTree->getRoot()->NextNode(tTree->getRoot())->getData()<<std::endl;*/
	//tTree->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 测试结果

在这里插入图片描述


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进