binarytree.cpp

1) 以二叉链表为存储结构

// BinaryTree.cpp: implementation of the BinaryTree class.
//
//////////////////////////////////////////////////////////////////////

#include "BinaryTree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
BinaryTree::BinaryTree()
{
	root=NULL;
}

BinTreeNode*BinaryTree::create1()
{
	int s;
	BinTreeNode *r;
	cin>>s;
	if(s==0){return NULL;}
	r=new BinTreeNode(s);
	r->leftchild=create1();
	r->rightchild=create1();
	return r;
}
void BinaryTree::preorder(BinTreeNode*r)
{
	cout<<r->data<<' ';
	if(r->leftchild!=NULL)preorder(r->leftchild);
	if(r->rightchild!=NULL)preorder(r->rightchild);
}
void BinaryTree::inorder(BinTreeNode*r)
{
	if(r->leftchild!=NULL)inorder(r->leftchild);
	cout<<r->data<<' ';
	if(r->rightchild!=NULL)inorder(r->rightchild);
}
void BinaryTree::postorder(BinTreeNode*r)
{
	if(r->leftchild!=NULL)postorder(r->leftchild);
	if(r->rightchild!=NULL)postorder(r->rightchild);
	cout<<r->data<<' ';
}
int BinaryTree::size(BinTreeNode*r)
{
	if(r==NULL)return 0;
	return 1+size(r->leftchild)+size(r->rightchild);
}
int BinaryTree::leaf(BinTreeNode*r)
{
	if(r==NULL)return 0;
	if(r->leftchild==NULL&&r->rightchild==NULL)return 1;
	return leaf(r->leftchild)+leaf(r->rightchild);
}
int BinaryTree::height(BinTreeNode*r)
{
	if(r==NULL)return 0;
	int a=(height(r->leftchild)>height(r->rightchild))?height(r->leftchild):height(r->rightchild);
	return 1+a;
}
template<class T>
void BinaryTree::levelOrder()
{
	LinkedQueue<BinTreeNode*> a;
	a.EnQueue(root);
	BinTreeNode*b;
	for(;a.DeQueue(b);)
	{
		cout<<b->data<<' ';
		if(b->leftchild!=NULL)a.EnQueue(b->leftchild);
		if(b->rightchild!=NULL)a.EnQueue(b->rightchild);
	}
}