二叉树

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

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();
}

二叉树的相关文章

递归实现前序遍历二叉树的前序遍历是指从根节点出发,按照先根节点,再左子树,后右子树的方法遍历二叉树中的所有节点,使得每个节点都被访问一次. 当调用遍历算法的时候前序遍历的具体过程如下: 首先访问根节点,如果根节点不为空,执行输出语句,打印根节点的值. 如果左子树不为空,则访问根节点的左孩子,并输出根节点做孩子的值继续访问根节点的左孩子的左孩子,如果不为空则继续输出该左孩子的值: 如果这时左孩子为空,说明该节点是叶子节点,则按照先左孩子后右孩子的访问方式访问其左右孩子,如果不为空就打印输出左

ZOJ3805Machine(二叉树左右子树变换)

/* 题意:建立一棵二叉树,左子树和父节点占一个宽度,右子树另外占一个宽度! 使任意左右子树交换顺序,使得整个树的宽度最小! 思路:递归交换左右子树 ! 开始写的代码复杂了,其实左右子树不用真的交换,只要返回交换与不交换最小的宽度值就好了,下次不用在查询了! */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 10005 using na

不用递归遍历一颗二叉树

问题描述不用递归遍历一颗二叉树用递归遍历二叉树很简单,但是现在的问题是,能不能不用递归去遍历呢?用C#或者Java给出代码更好. 解决方案简单来说有两个思路 (1)使用后序遍历的方法.也就是说对于一个节点,先找它的左子节点,再找右子节点,最后找它本身.(深度优先) (2)使用线形表来存储二叉树.二叉树是可以直接用线形表表达的.(广度优先) 解决方案二: 给出C++代码吧!把递归改为非递归,一般都是通过栈来实现.函数递归的原理也是利用了栈. 首先来看前序遍历:前序遍历是先访问当前结点,再访问

检查一个二叉树是否平衡的算法分析与C++实现

今天面试一个实习生,就想既然是未出校园,那就出一个比较基础的题吧,没想到答的并不如人意,对于树的操作完全不熟悉,因此此题算是未作答.原来我想看一下他分析问题的思路,优化代码的能力.接下来会把最近半年我出的面试题整理出来,以来share给其它同事,而来算是自己校园记忆的一个总结,毕竟自己在项目中已经很久未用到这些知识.其实很多题目都是来源于CareerCup.com.这上面汇集了许多IT名企的面试笔试题目,非常值得找工作的人学习. 言归正传,什么是二叉树是否平衡的定义,如果面试者不知道,那肯定要提

纸上谈兵: 树, 二叉树, 二叉搜索树[转]

树的特征和定义树(Tree)是元素的集合.我们先以比较直观的方式介绍树.下面的数据结构是一个树: 树有多个节点(node),用以储存元素.某些节点之间存在一定的关系,用连线表示,连线称为边(edge).边的上端节点称为父节点,下端称为子节点.树像是一个不断分叉的树根. 每个节点可以有多个子节点(children),而该节点是相应子节点的父节点(parent).比如说,3,5是6的子节点,6是3,5的父节点:1,8,7是3的子节点, 3是1,8,7的父节点.树有一个没有父节点的节点,称为根节点(

二叉树学习笔记之树的旋转

树旋转(Tree rotation)是二叉树中的一种子树调整操作,每一次旋转并不影响对该二叉树进行中序遍历的结果. 树旋转通常应用于需要调整树的局部平衡性的场合. 左旋和右旋树的旋转有两种基本的操作,即左旋(逆时针方向旋转)和右旋(顺时针方向旋转). 树旋转包括两个不同的方式,分别是左旋转(以P为转轴)和右旋转(以Q为转轴).两种旋转呈镜像,而且互为逆操作. 下图示意了两种树旋转过程中, 子树的初态和终态 +---+ +---+ | Q | | P | +---+ +---+ / \ righ

非递归方式创建二叉树

好长时间没摸过二叉树了,纯属练手我发现功能描述发布出来就乱了,还是贴图吧 #include <iostream> using namespace std; #define Type char #define MAX_BUFF 30 #define INC_BUFF 20 typedef struct _TreeNode { Type data; struct _TreeNode *lchild; struct _TreeNode *rchild; }TreeNode; TreeNode *c

表达式求值、表达式转二叉树

1.后序表达式求值: 后续表达式(逆波兰式)的特点:没有括号. 求值方法: 从前向后扫, 遇到操作数压栈: 遇到操作符,从栈中取出2个操作数运算,结果压栈. 最终栈中所剩的数为结果. 2.中序表达式求值我们先来定义运算符的优先级: ( +,- *,/,% 从上到下依次升高准备2个栈,一个专门存放运算符,另一个专门存放操作数. 1.遇到),那么退栈计算到(为止.结果压栈. 2.遇到运算数.那么压栈. 3.如果当前运算符优先级低于栈顶运算符.那么计算栈顶运算符并将结果压栈. 4.否则压栈. 计算

二叉树求结点个数-c++编程，，跪求大神解答

问题描述 c++编程,,跪求大神解答 #include using namespace std; template struct BiNode { BiNode *lchild; datatype data; BiNode *rchild; }; template struct element { BiNode *ptr; int flag; }; BiNode *first,*bt,*q,*temp,stack[20],queue[20]; element s[20]; int count=0

遍历二叉树

一.基础知识 1. 遍历二叉树概念:如何按某条搜索路径寻访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次. 2.遍历二叉树限定先左后右,则有三种情况先(根)序遍历,中(根)序遍历和后(根)序遍历先序遍历二叉树定义操作若二叉树为空,则空操作:否则: a.访问根节点 b.先序遍历左子树 c.先序遍历右子树 //先序遍历 void

二叉树