温存温存9.1

描述
创建二叉树类。二叉树的存储结构使用链表。提供 *** 作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。

格式
输入格式
第一行为一个数字n (10<=n<=100000)，表示有这棵树有n个节点，编号为1~n。
之后n行每行两个数字，第 i 行的两个数字a、b表示编号为 i 的节点的左孩子节点为 a，右孩子节点为 b，-1表示该位置没有节点。
保证数据有效，根节点为1。

输出格式
第一行，n个数字，表示该树的层次遍历。
第二行，n个数字，第i个数字表示以 i 节点为根的子树的节点数目。
第三行，n个数字，第i个数字表示以 i 节点为根的子树的高度。

#include
using namespace std;
int counts[999999];//计算树的节点的数组 
int deep[999999];//计算树的高度的数组 
template
struct binaryTreeNode{//二叉树节点结构 
	T element;//元素的值 
	int leaves; 
	binaryTreeNode*leftChild,*rightChild; 
	binaryTreeNode():leftChild(NULL),rightChild(NULL){}
	binaryTreeNode(const T&theElement):element(theElement){
		leftChild=rightChild=NULL;
	} 
	binaryTreeNode(const T&theElement,binaryTreeNode* theLeftChild,binaryTreeNode* theRightChild){
		element=theElement;
		leftChild=theLeftChild;
		rightChild=theRightChild;
	} 
};
template
class BinaryTree{
	private:
		binaryTreeNode*root;//根节点指针
		int treeSize;//元素个数
	public:
		BinaryTree():root(NULL),treeSize(0){}//构造 
		~BinaryTree(){erase(root);}//析构 
		bool empty()const {return treeSize==0;}
		int size()const{return treeSize;} 
		binaryTreeNode** rootElement(){return &root;}//返回根节点 
		void preOrder(binaryTreeNode*);
		void inOrder(binaryTreeNode*);
		void postOrder(binaryTreeNode*);
		void levelOrder();
		void erase(binaryTreeNode*&proot);
		int height(binaryTreeNode*t);//高度 
		int treeCount(binaryTreeNode*t);//节点树 
		void makeTree(T* element,int n);
		void visit(binaryTreeNode*t);
};
template
void BinaryTree::visit(binaryTreeNode*t){//访问 
	cout<element<<" ";
}
template
void BinaryTree::erase(binaryTreeNode*&proot){
	if(proot!=NULL){
		erase(proot->leftChild);
		erase(proot->rightChild);
		delete proot;
		proot=NULL;
	}
}
template
void BinaryTree::preOrder(binaryTreeNode*t){//前序遍历 
	if(t!=NULL){//根左右 
	    //t->element代表第几个节点，与值一样 
		counts[(t->element)-1]=treeCount(t);//counts数组表示以第几个节点为跟的节点个数 
		deep[(t->element)-1]=height(t);//deep表示以第几个节点为跟的节点高度 
		//visit(t);
		preOrder(t->leftChild);
		preOrder(t->rightChild);
	}
}
template
void BinaryTree::inOrder(binaryTreeNode*t){//中序遍历 
	if(t!=NULL){
		inOrder(t->leftChild);
		visit(t);//访问根节点 
		inOrder(t->rightChild);
	}
}
template
void BinaryTree::postOrder(binaryTreeNode*t){//后序遍历
	if(t!=NULL){
		postOrder(t->leftChild);
		postOrder(t->rightChild);
		visit(t);
	} 
} 
template
void BinaryTree::levelOrder(){//层次遍历
	binaryTreeNode * q[treeSize];//数组型指针 
    q[0]=root;//指针指向头节点 
    cout<element<<" ";
    for(int i=1;ileaves==1){//当q【leave】被值1时，该节点完成任务，就代表需要++来转下一个值了
   			index++;
		}
   		if(i%2!=0){
   			q[i]=q[index]->leftChild;
   			if(q[i]!=NULL)
   				cout<element<<" ";
   		}else{//转到右节点就得转下一个节点了，所以leave值1 
   			q[i]=q[index]->rightChild;
   			q[index]->leaves=1;
   			if(q[i]!=NULL)
   				cout<element<<" ";
		}
   }
}
template 
int BinaryTree::height(binaryTreeNode *t){//递归求树的高度 
//hl,hr每次循环都更新 
   if (t == NULL)
      return 0;                    // 空
   int hl = height(t->leftChild);  // 左边高度 
   int hr = height(t->rightChild); // 右边高度 
   if (hl > hr)
      return ++hl;
   else
      return ++hr;
}
template
int BinaryTree::treeCount(binaryTreeNode*t){//递归求出树的节点的数目 
//深入到叶节点一个一个累加上来 
	int n=0;
	if(t!=NULL){
		n=treeCount(t->leftChild)+treeCount(t->rightChild)+1;
	}
	return n;
}
template
void BinaryTree::makeTree(T*elem,int n){
    binaryTreeNode * *(array[n/2])={};//binaryTreeNode类型的指针，且是一个数组型指针，既每个数都是一个指针 
    array[0]=&root;//起点 
    //array[0]是root的地址，既指向root 
    root=new binaryTreeNode;
	root->element=elem[0];
	root->leftChild=NULL;
	root->rightChild=NULL;
	root->leaves=0;
	for(int i=1;i* p=new binaryTreeNode;
		if(elem[i]!=-1){
			p->element=elem[i];
			p->leftChild=NULL;
			p->rightChild=NULL;
			p->leaves=0;
		}else
			p=NULL;
		if(i%2!=0){
			(*array[index])->leftChild=p;//代表当前节点的左孩子 
			//(*array[0])代表就是root本身 
			if(p!=NULL)
				//寻找下一个节点，eg:a[0]-->a[1]-->a[2] 
				array[(p->element)-1]=&((*array[index])->leftChild);//array[(p->element)-1]再指向 (*array[index])->leftChild
				                                        //因此当出现与 array[(p->element)-1]相同的array[index]便实现树的生长 
		}else{
			(*array[index])->rightChild=p;//当前节点的有孩子 
			if(p!=NULL)
				array[(p->element)-1]=&((*array[index])->rightChild);
		}	
    }
    treeSize=n;
}
int main(){
	BinaryTree tree;
    int n;cin>>n;
	int *num=new int[2*n+1];
	num[0]=1;
	for(int i=1;i<=(2*n);i++){//输入节点值，注意要符合节点的序号 
		cin>>num[i];
	}
	tree.makeTree(num,2*n+1);
	tree.levelOrder();
	cout<* node=*tree.rootElement();
	tree.preOrder(node);//为count和deep赋值 
	for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5504019.html