btree.cpp

关于数据结构中二叉树的实验源代码

// BTree.cpp : Defines the entry point for the console application.
//
/* 实验六：
1、写一函数，计算树的结点数目；
2、完善两个函数：
	（1）计算树的高度；
	（2）对树的所有子树交换左右孩子；
3、自己添加层次遍历的函数并在主程序中调用；
*/

#include "BTree.h"
#include "iostream.h"
template<class T>
int Depth(BTNode<T>* &root)////////////////////////////////计算树的高度
{
	int depthleft,depthright,depthval;
	if(root==NULL)depthval=-1;//////////////////./////////////////////////////* 填空 */;
	else 
	{
		depthleft=Depth(root->Left());
		depthright=Depth(root->Right());
		depthval=1+(depthleft>depthright?depthleft:depthright);///////////////////////////////////////* 填空 */;
	}
	return depthval;
}

template<class T>
int CountLeaf(BTNode<T>* &t)
{
	if(t==NULL) return 0;
	else 
		if(t->Left()==NULL&&t->Right()==NULL)
			return 1;
		else return	CountLeaf(t->Left())+CountLeaf(t->Right());
}

template<class T>

int CountNode(BTNode<T>* &t)
{
	int static count=0;
	if(t!=NULL)
	{
		CountNode(t->Left());
		CountNode(t->Right());
		if(t->Left()==NULL&&t->Right()==NULL)
		   	cout<<'\0';
		count++;
	}
	return count;
}

		
// 输入您自己编写的语句


template<class T>
void swapsons(BTNode<T>* &t)
{
	if (t==NULL) return;
	else
	{
		swapsons(t->Left()/* 填空 */);
		swapsons(t->Right())/* 填空 */;
		BTNode<T>* temp;
		temp=t->Left()/* 填空 */;
		t->Left()=t->Right()/* 填空 */;
		t->Right()=temp/* 填空 */;
	}
}


void main(void)
{
	BTNode<char> d('D'),f('F'),g('G'),e('E',&f,&g),c('C'),b('B',&d,&e),a('A',&b,&c);
	BTree<char> t(&a);
	cout<<endl<<"先序遍历："<<endl;
	t.PreOrder();
	cout<<endl<<"中序遍历："<<endl;
	t.InOrder();
	cout<<endl<<"后序遍历："<<endl;
	t.PostOrder();

	cout<<" 树的深度是："<<Depth(t.BTRoot())<<endl<<endl;
     cout<<" 叶片的数目是："<<CountLeaf(t.BTRoot())<<endl<<endl;

    cout<<" 结点的数目是："<<CountNode(t.BTRoot())<<endl<<endl;
   

 	swapsons(t.BTRoot());
	cout<<"左右儿子交换之后："<<endl;
	cout<<endl<<"先序遍历："<<endl;
	t.PreOrder();
	cout<<endl<<"中序遍历："<<endl;
	t.InOrder();

}