bitree.cpp

动态建立二叉树

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
const char max=100;

template <class T>
class BiTreeNode
{
	private:
		BiTreeNode <T> *leftchild;
		BiTreeNode <T> *rightchild;

	public:
		T data;

		BiTreeNode():leftchild(NULL),rightchild(Null){}
		BiTreeNode(T item,BiTreeNode<T> *left=NULL,BiTreeNode<T> *right=NULL)
		{
			data=item;
			leftchild=left;
			rightchild=right;
		}

		BiTreeNode<T> * &left(void)    //返回值为指针的引用类型
		{
			return leftchild;
		}
			BiTreeNode<T> * &right(void)  //返回值为指针的引用类型
			{
				return rightchild;
			}

};




template <class T>    //先序遍历建立二叉树
void PreOrdercreat(BiTreeNode<T> * &t)
{
	int x;
	cout<<"输入节点中的数据信息："<<endl;
	cin>>x;
	if(x==0) t=NULL;
	else
	{
		t=new BiTreeNode<T>(x);
		PreOrdercreat(t->left());
		PreOrdercreat(t->right());
	}
}

template <class T>                            
void InOrder(BiTreeNode<T> * &t)
{
	if(t!=NULL)
	{          
		InOrder(t->left());
	    cout<<t->data<<" ";
		InOrder(t->right());
                        
 	}
}

template <class T>                            
void PostOrder(BiTreeNode<T> * &t)
{
	if(t!=NULL)
	{          
		PostOrder(t->left());
		PostOrder(t->right());
        cout<<t->data<<" ";
 	}
}

template <class T> 
void  levelcreat(BiTreeNode<T> *&t)
{
	BiTreeNode<T> *s[20];
	int rear(0),front(0);
    BiTreeNode<T> *p,*q,*root;
	T ch,ch1,ch2;
	cout<<"输入根结点的数据信息：";
	cin>>ch;
	if(ch==0) exit(1);
		else
		{
			p=new BiTreeNode<T>(ch);
			root=p;
			s[++rear]=p;
		}
		while(front!=rear)
		{
			p=s[++front];
			cout<<"输入左右孩子信息，如果没有则输入空";
			cin>>ch1>>ch2;
			if(ch1!=0)
			{
				q=new BiTreeNode<T>(ch1);
				p=p->left();
				p=q;
				s[++rear]=q;
			}
			if(ch2!=0)
			{
				q=new BiTreeNode<T>(ch2);
				p=p->right();
				p=q;
				s[++rear]=q;
			}
			
		}
		t=root;
}

void main()
{
	BiTreeNode<int> *root;
	/*PreOrdercreat(root);
	cout<<"后序遍历二叉树的节点序列为："<<endl;
	PostOrder(root);
	cout<<endl;
	cout<<"中许遍历二叉树的节点序列为："<<endl;
	InOrder(root);
	cout<<endl;*/

	levelcreat(root);
	cout<<"后序遍历二叉树的节点序列为："<<endl;
	PostOrder(root);
	cout<<endl;
	cout<<"中许遍历二叉树的节点序列为："<<endl;
	InOrder(root);
	cout<<endl;

}