AI 助理
备案控制台
开发者社区 云计算 文章 正文

二叉树

2016-05-06 1011
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

今晚闲来无事，练练基本的数据结构吧

BinTreeNode.h 

template<typename Type> class BinaryTree;

template<typename Type> class BinTreeNode{
public:
	friend class BinaryTree<Type>;
	BinTreeNode():m_pleft(NULL),m_pright(NULL){}
	BinTreeNode(Type item,BinTreeNode<Type> *left=NULL,BinTreeNode<Type> *right=NULL)
		:m_data(item),m_pleft(left),m_pright(right){}

	Type GetData() const;		//get thd data
	BinTreeNode<Type> *GetLeft() const;		//get the left node
	BinTreeNode<Type> *GetRight() const;	//get the right node

	void SetData(const Type data);			//change the data
	void SetLeft(const BinTreeNode<Type> *left);	//change thd left node
	void SetRight(const BinTreeNode<Type> *right);	//change the right node

	void InOrder();		//inorder the tree with the root of the node
	void PreOrder();	//perorder the tree with the root of the node
	void PostOrder();	//postoder the tree with the root of the node
	
	int Size();			//get size
	int Height();		//get height
	BinTreeNode<Type> *Copy(const BinTreeNode<Type> *copy);	//copy the node
	void Destroy(){		//destroy the tree with the root of the node
		if(this!=NULL){
			this->m_pleft->Destroy();
			this->m_pright->Destroy();
			delete this;
		}
	}

	friend bool equal<Type>(const BinTreeNode<Type> *s,const BinTreeNode<Type> *t);	//is equal?

private:
	BinTreeNode<Type> *m_pleft,*m_pright;
	Type m_data;
};

template<typename Type> Type BinTreeNode<Type>::GetData() const{
	return this!=NULL?m_data:-1;
}

template<typename Type> BinTreeNode<Type>* BinTreeNode<Type>::GetLeft() const{
	return this!=NULL?m_pleft:NULL;
}

template<typename Type> BinTreeNode<Type>* BinTreeNode<Type>::GetRight() const{
	return this!=NULL?m_pright:NULL;
}

template<typename Type> void BinTreeNode<Type>::SetData(const Type data){
	if(this!=NULL){
		m_data=data;
	}
}

template<typename Type> void BinTreeNode<Type>::SetLeft(const BinTreeNode<Type> *left){
	if(this!=NULL){
		m_pleft=left;
	}
}

template<typename Type> void BinTreeNode<Type>::SetRight(const BinTreeNode<Type> *right){
	if(this!=NULL){
		m_pright=right;
	}
}

template<typename Type> BinTreeNode<Type>* BinTreeNode<Type>::Copy(const BinTreeNode<Type> *copy){
	if(copy==NULL){
		return NULL;
	}

	BinTreeNode<Type> *temp=new BinTreeNode<Type>(copy->m_data);
	temp->m_pleft=Copy(copy->m_pleft);
	temp->m_pright=Copy(copy->m_pright);
	return temp;
}

template<typename Type> bool equal(const BinTreeNode<Type> *s,const BinTreeNode<Type> *t){
	if(s==NULL&&t==NULL){
		return 1;
	}
	if(s&&t&&s->m_data==t->m_data&&equal(s->m_pleft,t->m_pleft)&&equal(s->m_pright,t->m_pright)){
		return 1;
	}
	return 0;
}

template<typename Type> void BinTreeNode<Type>::InOrder(){
	if(this!=NULL){
		this->m_pleft->InOrder();
		cout<<"--->"<<this->m_data;
		this->m_pright->InOrder();
	}
}

template<typename Type> void BinTreeNode<Type>::PreOrder(){
	if(this!=NULL){
		cout<<"--->"<<this->m_data;
		this->m_pleft->PreOrder();
		this->m_pright->PreOrder();
	}
}

template<typename Type> void BinTreeNode<Type>::PostOrder(){
	if(this!=NULL){
		this->m_pleft->PostOrder();
		this->m_pright->PostOrder();
		cout<<"--->"<<this->m_data;
	}
}

template<typename Type> int BinTreeNode<Type>::Size(){
	if(this==NULL){
		return 0;
	}
	return 1+this->m_pleft->Size()+this->m_pright->Size();
}

template<typename Type> int BinTreeNode<Type>::Height(){
	if(this==NULL){
		return -1;
	}
	int lheight,rheight;
	lheight=this->m_pleft->Height();
	rheight=this->m_pright->Height();
	return 1+(lheight>rheight?lheight:rheight);
}
下面是： BinaryTree.h 

#include "BinTreeNode.h"

template<typename Type> class BinaryTree{
public:
	BinaryTree():m_proot(NULL){}
	BinaryTree(const Type stop):m_stop(stop),m_proot(NULL){}
	BinaryTree(BinaryTree<Type>& copy);
	virtual ~BinaryTree(){
		m_proot->Destroy();
	}
	virtual bool IsEmpty(){		//is empty?
		return m_proot==NULL;
	}
	
	virtual BinTreeNode<Type> *GetLeft(BinTreeNode<Type> *current);	//get the left node
	virtual BinTreeNode<Type> *GetRight(BinTreeNode<Type> *current);//get the right node
	virtual BinTreeNode<Type> *GetParent(BinTreeNode<Type> *current);//ghe thd parent
	const BinTreeNode<Type> *GetRoot() const;	//get root
	
	virtual bool Insert(const Type item);		//insert a new node
	virtual BinTreeNode<Type> *Find(const Type item) const;	//find thd node with the data

	void InOrder();	
	void PreOrder();
	void PostOrder();

	int Size();		//get size
	int Height();	//get height

	BinaryTree<Type>& operator=(const BinaryTree<Type> copy);	//evaluate node

	friend bool operator== <Type>(const BinaryTree<Type> s,const BinaryTree<Type> t);//is equal?
	friend ostream& operator<< <Type>(ostream& ,BinaryTree<Type>&);	//output the data
	friend istream& operator>> <Type>(istream& ,BinaryTree<Type>&);	//input the data
		
private:
	Type m_stop;		//just using for input the data;
	BinTreeNode<Type> *m_proot;

	//find the parent of current in the tree with the root of start
	BinTreeNode<Type> *GetParent(BinTreeNode<Type> *start,BinTreeNode<Type> *current);
	void Print(BinTreeNode<Type> *start,int n=0);	//print the tree with the root of start
};

template<typename Type> BinaryTree<Type>::BinaryTree(BinaryTree<Type>& copy){
	if(copy.m_proot){
		this->m_stop=copy.m_stop;
	}
	m_proot=m_proot->Copy(copy.m_proot);
}
template<typename Type> BinTreeNode<Type>* BinaryTree<Type>::GetLeft(BinTreeNode<Type> *current){
	return m_proot&&current?current->m_pleft:NULL;
}

template<typename Type> BinTreeNode<Type>* BinaryTree<Type>::GetRight(BinTreeNode<Type> *current){
	return m_proot&&current?current->m_pright:NULL;
}

template<typename Type> const BinTreeNode<Type>* BinaryTree<Type>::GetRoot() const{
	return m_proot;
}

template<typename Type> BinTreeNode<Type>* BinaryTree<Type>::GetParent(BinTreeNode<Type> *start, BinTreeNode<Type> *current){
	if(start==NULL||current==NULL){
		return NULL;
	}
	if(start->m_pleft==current||start->m_pright==current){
		return start;
	}
	BinTreeNode<Type> *pmove;
	if((pmove=GetParent(start->m_pleft,current))!=NULL){//find the parent in the left subtree
		return pmove;
	}
	else{
		return GetParent(start->m_pright,current);	//find the parent in the right subtree
	}
}

template<typename Type> BinTreeNode<Type>* BinaryTree<Type>::GetParent(BinTreeNode<Type> *current){
	return m_proot==NULL||current==m_proot?NULL:GetParent(m_proot,current);	
}


template<typename Type> bool BinaryTree<Type>::Insert(const Type item){
	BinTreeNode<Type> *pstart=m_proot,*newnode=new BinTreeNode<Type>(item);
	if(m_proot==NULL){
		m_proot=newnode;
		return 1;
	}
	while(1){
		if(item==pstart->m_data){
			cout<<"The item "<<item<<" is exist!"<<endl;
			return 0;
		}
		if(item<pstart->m_data){
			if(pstart->m_pleft==NULL){
				pstart->m_pleft=newnode;
				return 1;
			}
			pstart=pstart->m_pleft;	//if less than the node then insert to the left subtree
		}
		else{
			if(pstart->m_pright==NULL){
				pstart->m_pright=newnode;
				return 1;
			}
			pstart=pstart->m_pright;//if more than the node then insert to the right subtree
		}
	}
}

template<typename Type> BinTreeNode<Type>* BinaryTree<Type>::Find(const Type item) const{
	BinTreeNode<Type> *pstart=m_proot;
	while(pstart){
		if(item==pstart->m_data){
			return pstart;
		}
		if(item<pstart->m_data){
			pstart=pstart->m_pleft;	//if less than the node then find in the left subtree
		}
		else{
			pstart=pstart->m_pright;//if more than the node then find in the right subtree
		}
	}
	return NULL;
}

template<typename Type> void BinaryTree<Type>::Print(BinTreeNode<Type> *start, int n){
	if(start==NULL){
		for(int i=0;i<n;i++){
			cout<<"     ";
		}
		cout<<"NULL"<<endl;
		return;
	}
	Print(start->m_pright,n+1);	//print the right subtree
	for(int i=0;i<n;i++){	//print blanks with the height of the node
		cout<<"     ";
	}
	if(n>=0){
		cout<<start->m_data<<"--->"<<endl;//print the node
	}
	Print(start->m_pleft,n+1);	//print the left subtree
}

template<typename Type> BinaryTree<Type>& BinaryTree<Type>::operator=(const BinaryTree<Type> copy){
	if(copy.m_proot){
		this->m_stop=copy.m_stop;
	}
	m_proot=m_proot->Copy(copy.m_proot);
    return *this;
}

template<typename Type> ostream& operator<<(ostream& os,BinaryTree<Type>& out){
	out.Print(out.m_proot);
	return os;
}

template<typename Type> istream& operator>>(istream& is,BinaryTree<Type>& in){
	Type item;
	cout<<"initialize the tree:"<<endl<<"Input data(end with "<<in.m_stop<<"!):";
	is>>item;
	while(item!=in.m_stop){	//m_stop is the end of input
		in.Insert(item);
		is>>item;
	}
	return is;
}

template<typename Type> bool operator==(const BinaryTree<Type> s,const BinaryTree<Type> t){
	return equal(s.m_proot,t.m_proot);
}

template<typename Type> void BinaryTree<Type>::InOrder(){
	this->m_proot->InOrder();
}

template<typename Type> void BinaryTree<Type>::PreOrder(){
	this->m_proot->PreOrder();
}

template<typename Type> void BinaryTree<Type>::PostOrder(){
	this->m_proot->PostOrder();
}

template<typename Type> int BinaryTree<Type>::Size(){
	return this->m_proot->Size();

}

template<typename Type> int BinaryTree<Type>::Height(){
	return this->m_proot->Height();
}

Test.cpp 
#include <iostream>

using namespace std;

#include "BinaryTree.h"

int main(){
	BinaryTree<int> tree(-1);
//	int init[10]={3,6,0,2,8,4,9,1,5,7};
	int init[30]={17,6,22,29,14,0,21,13,27,18,2,28,8
		,26,3,12,20,4,9,23,15,1,11,5,19,24,16,7,10,25};
	for(int i=0;i<30;i++){
		tree.Insert(init[i]);
	}
	//cin>>tree;
	cout<<tree<<endl;

	cout<<tree.GetParent(tree.Find(20))->GetData()<<endl;
	cout<<tree.Find(15)->GetRight()->GetData()<<endl;

	cout<<"size="<<tree.Size()<<endl;
	cout<<"height="<<tree.Height()<<endl;

	tree.InOrder();
	cout<<endl<<endl;
	tree.PreOrder();
	cout<<endl<<endl;
	tree.PostOrder();
	cout<<endl<<endl;
	

	BinaryTree<int> tree2=tree;
	cout<<tree2<<endl;

	cout<<tree2.GetParent(tree2.Find(20))->GetData()<<endl;
	cout<<tree2.Find(15)->GetRight()->GetData()<<endl;

	cout<<(tree==tree2)<<endl;
	return 0;
}
rollenholt
目录
相关文章
JYeontu
|
7月前
|
算法 前端开发
2583. 二叉树中的第 K 大层和
2583. 二叉树中的第 K 大层和
JYeontu
55 0
游客rcxtdbgrolahs
|
3月前
|
算法
22_最大二叉树
22_最大二叉树
游客rcxtdbgrolahs
25 1
aliyun0193839942-27807
|
7月前
|
存储
二叉树详解
二叉树详解
aliyun0193839942-27807
50 2
不是笨小孩i
二叉树的讲解
1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1. 3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为02 ,则有n0 ＝n2 ＋1 4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= . (ps： 是log以2为底，n+1为对数) 5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
不是笨小孩i
81 0
二叉树的讲解
-初生-
二叉树（详解）下
二叉树（详解）
-初生-
62 0
还在路上的秃头
|
7月前
|
算法 网络协议 NoSQL
认识二叉树（详细介绍）
认识二叉树（详细介绍）
还在路上的秃头
79 0
..清风
|
存储
浅谈二叉树
浅谈二叉树
..清风
51 1
დ旧言~
|
7月前
|
存储
二叉树的实现（下）
二叉树的实现（下）
დ旧言~
61 0
დ旧言~
|
7月前
|
存储 Java C++
二叉树的实现（上）
二叉树的实现
დ旧言~
70 0
阿甘兄
24 二叉树
24 二叉树
阿甘兄
50 0