线索二叉树

简介:
ThreadNode.h

template<typename Type> class ThreadTree;
template<typename Type> class ThreadInorderIterator;

template<typename Type> class ThreadNode{
public:
	friend class ThreadTree<Type>;
	friend class ThreadInorderIterator<Type>;
	ThreadNode():m_nleftthread(1),m_nrightthread(1){
		m_pleft=this;
		m_pright=this;
	}
	ThreadNode(const Type item):m_data(item),m_pleft(NULL),m_pright(NULL)
		,m_nleftthread(0),m_nrightthread(0){}

private:
	int m_nleftthread,m_nrightthread;
	ThreadNode<Type> *m_pleft,*m_pright;
	Type m_data;
};

ThreadTree.h

#include "ThreadNode.h"

template<typename Type> class ThreadInorderIterator;

template<typename Type> class ThreadTree{
public:
	friend class ThreadInorderIterator<Type>;
	ThreadTree():m_proot(new ThreadNode<Type>()){}

ThreadInorderIterator.h

#include "ThreadTree.h"

template<typename Type> class ThreadInorderIterator{
public:
	ThreadInorderIterator(ThreadTree<Type> &tree):m_ptree(tree),m_pcurrent(tree.m_proot){
		//InThread(m_ptree.m_proot->m_pleft,m_ptree.m_proot);
	}
	
	ThreadNode<Type> *First();
	ThreadNode<Type> *Prior();
	ThreadNode<Type> *Next();

	void Print();
	void Print(ThreadNode<Type> *start, int n=0);
	void InOrder();
	void InsertLeft(ThreadNode<Type> *left);
	void InsertRight(ThreadNode<Type> *right);
	ThreadNode<Type> *GetParent(ThreadNode<Type> *current);

	
private:
	ThreadTree<Type> &m_ptree;
	ThreadNode<Type> *m_pcurrent;
	void InThread(ThreadNode<Type> *current,ThreadNode<Type> *pre);
};

template<typename Type> void ThreadInorderIterator<Type>::InThread(
	ThreadNode<Type> *current, ThreadNode<Type> *pre){
	if(current!=m_ptree.m_proot){
		InThread(current->m_pleft,pre);
		if(current->m_pleft==NULL){
			current->m_pleft=pre;
			current->m_nleftthread=1;
		}
		if(pre->m_pright==NULL){
			pre->m_pright=current;
			pre->m_nrightthread=1;
		}

		pre=current;
		InThread(current->m_pright,pre);
	}
}

template<typename Type> ThreadNode<Type>* ThreadInorderIterator<Type>::First(){
	while(m_pcurrent->m_nleftthread==0){
		m_pcurrent=m_pcurrent->m_pleft;
	}
	return m_pcurrent;
}

template<typename Type> ThreadNode<Type>* ThreadInorderIterator<Type>::Prior(){
	ThreadNode<Type> *pmove=m_pcurrent->m_pleft;
	if(0==m_pcurrent->m_nleftthread){
		while(0==pmove->m_nrightthread){
			pmove=pmove->m_pright;
		}
	}
	m_pcurrent=pmove;
	if(m_pcurrent==m_ptree.m_proot){
		return NULL;
	}
	return m_pcurrent;
}

template<typename Type> ThreadNode<Type>* ThreadInorderIterator<Type>::Next(){
	ThreadNode<Type> *pmove=m_pcurrent->m_pright;
	if(0==m_pcurrent->m_nrightthread){
		while(0==pmove->m_nleftthread){
			pmove=pmove->m_pleft;
		}
	}
	m_pcurrent=pmove;
	if(m_pcurrent==m_ptree.m_proot){
		return NULL;
	}
	return m_pcurrent;
}

template<typename Type> void ThreadInorderIterator<Type>::InOrder(){
	ThreadNode<Type> *pmove=m_ptree.m_proot;
	while(pmove->m_pleft!=m_ptree.m_proot){
		pmove=pmove->m_pleft;
	}
	m_pcurrent=pmove;
	cout<<"root";
	while(pmove!=m_ptree.m_proot&&pmove){
		cout<<"--->"<<pmove->m_data;
		pmove=this->Next();
	}
	cout<<"--->end";
}

template<typename Type> void ThreadInorderIterator<Type>::InsertLeft(ThreadNode<Type> *left){
	left->m_pleft=m_pcurrent->m_pleft;
	left->m_nleftthread=m_pcurrent->m_nleftthread;
	left->m_pright=m_pcurrent;
	left->m_nrightthread=1;
	m_pcurrent->m_pleft=left;
	m_pcurrent->m_nleftthread=0;
	if(0==left->m_nleftthread){
		m_pcurrent=left->m_pleft;
		ThreadNode<Type> *temp=First();
		temp->m_pright=left;
	}
	m_pcurrent=left;
}

template<typename Type> void ThreadInorderIterator<Type>::InsertRight(ThreadNode<Type> *right){
	right->m_pright=m_pcurrent->m_pright;
	right->m_nrightthread=m_pcurrent->m_nrightthread;
	right->m_pleft=m_pcurrent;
	right->m_nleftthread=1;
	m_pcurrent->m_pright=right;
	m_pcurrent->m_nrightthread=0;
	if(0==right->m_nrightthread){
		m_pcurrent=right->m_pright;
		ThreadNode<Type> *temp=First();
		temp->m_pleft=right;
	}
	m_pcurrent=right;
}

template<typename Type> ThreadNode<Type>* ThreadInorderIterator<Type>::GetParent(
	ThreadNode<Type> *current){
	ThreadNode<Type> *pmove=current;
	while(0==pmove->m_nleftthread){
		pmove=pmove->m_pleft;
	}
	pmove=pmove->m_pleft;
	if(pmove==m_ptree.m_proot){
		if(pmove->m_pleft==current){
			return NULL;
		}
	}
	if(pmove->m_pright==current){
		return pmove;
	}
	pmove=pmove->m_pright;
	while(pmove->m_pleft!=current){
		pmove=pmove->m_pleft;
	}
	return pmove;
}

template<typename Type> void ThreadInorderIterator<Type>::Print(ThreadNode<Type> *start, int n){
	if(start->m_nleftthread&&start->m_nrightthread){
	for(int i=0;i<n;i++){
		cout<<"     ";
	}
	if(n>=0){
		cout<<start->m_data<<"--->"<<endl;
	}

		return;
	}
	if(start->m_nrightthread==0){
		Print(start->m_pright,n+1);
	}
	for(int i=0;i<n;i++){
		cout<<"     ";
	}
	if(n>=0){
		cout<<start->m_data<<"--->"<<endl;
	}
	if(start->m_nleftthread==0){
		Print(start->m_pleft,n+1);
	}
}

template<typename Type> void ThreadInorderIterator<Type>::Print(){
	Print(m_ptree.m_proot->m_pleft);
}

test.cpp

 

 

int main(){
	ThreadTree<int> tree;
	ThreadInorderIterator<int> threadtree(tree);
	int init[10]={3,6,0,2,8,4,9,1,5,7};
	for(int i=0;i<10;){
		threadtree.InsertLeft(new ThreadNode<int>(init[i++]));
		threadtree.InsertRight(new ThreadNode<int>(init[i++]));
	}
	threadtree.Print();
	cout<<endl<<endl;

	threadtree.InOrder();
	return 0;
}
目录
相关文章
|
Web App开发 前端开发
《HTML 5+CSS 3入门经典》——2.5 小结
本节书摘来自华章计算机《HTML 5+CSS 3入门经典》一书中的第2章,第2.5节,作者:管媛辉 潘凯华著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1206 0
|
数据挖掘 大数据
大数据导论之为何需要引入大数据
一、引言   最近各种客户咨询项目中,往往涉及大数据引入必要性和价值意义的深层次挖掘,客户有数据,有平台,但是不知到底要不要上大数据,为何要上大数据和大数据可以带来哪些价值和意义。本文关于大数据的必要性进行阐述,来源实际项目,算是分享吧。
817 0
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1273 5
|
2天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1290 87