bttest.h

二叉树

// 尝试自己写一个完整的二叉树的定义，主要是遍历函数的非递归实现

# ifndef SELDEF_BT
# define SELDEF_BT

#include<iostream.h>
# include<string.h>
#include"Stack.h"
#include"list.h"
#include"Queue.h"

template<class T>
class BSTNode {             // 一般搜索二叉树的节点定义
public:
    BSTNode() { 
        left = right = 0; 
    }
    BSTNode(const T& el, BSTNode<T> *l = 0, BSTNode<T> *r = 0) {
        key = el; left = l; right = r; 
    }
    T key;
    BSTNode<T> *left, *right;
};
//--------------------------------------------------------------------
template<class T>
class BinaryTree  {     //一般二叉树的类定义 
public:
    BinaryTree()
	{	root=0;  	}
	BinaryTree(BSTNode<T>* r)
	{	setRoot(r);   }
	void setRoot(BSTNode<T>* r)  {root=r;}
    BSTNode<T>* getRoot() const  { return root;}
	void makeBinaryTree() {root=makeBinaryTree(root);}
	BSTNode<T>* makeBinaryTree(BSTNode<T>* r);        //从根开始建树，从键盘输入，递归
	BSTNode<T>* makeBinaryTree(BSTNode<T>* r,T el);   //
	void makeBinaryTree(const T& el,BinaryTree<T>& left,BinaryTree<T>& right);  //从叶子开始建树，一直到根
	void levelOrder();
	void preOrder(BSTNode<T>* r);
	void iterativePreOrder();      //非递归
	void inOrder(BSTNode<T>* r);
	void iterativeInOrder();       //非递归
	void postOrder(BSTNode<T>* r);
	void iterativePostOrder();     //非递归
	BSTNode<T> * PreInToTree(BSTNode<T> *root,TNode<T>* ph,TNode<T>* ih);
	BSTNode<T> * InPostToTree(BSTNode<T> *r,TNode<T>* ih,TNode<T>* poh);

	//int countAllNode(BSTNode<T>* r);
    //int countLeafNode(BSTNode<T>* r);
	//int countRightNode(BSTNode<T>* r);
	//void deleteLeafNode(BSTNode<T>* r);
private:
	BSTNode<T>* root;
};

template<class T>
BSTNode<T>* BinaryTree<T>::makeBinaryTree(BSTNode<T>* r)
{
	T ch;
	cout<<"Input the root node\n";
	cin>>ch;
	if(ch=='#')
		return 0;
    else{
	r=new BSTNode<T>(ch,0,0);
    r->left=makeBinaryTree(r->left);
    r->right=makeBinaryTree(r->right);
	return r; 
	}
}

template<class T>
BSTNode<T>* BinaryTree<T>::makeBinaryTree(BSTNode<T>* r,T el)
{
	
	if(el=='#')
		return 0;
    else{
	root=new BSTNode<T>(el,0,0);
	makeBinaryTree(root->left);
	makeBinaryTree(root->right);
	return root; }
}
template<class T>
void BinaryTree<T>::makeBinaryTree(const T& el,BinaryTree<T>& left,BinaryTree<T>& right)  //递归建立树？
{
	root=new BinaryTreeNode<T>(el,left.root,right.root);
	left.root=right.root=0;
}
template<class T>
void BinaryTree<T>::levelOrder()
{
	ArrayQueue<BSTNode<T>*> Q;
	BSTNode<T>* t=root;
	Q.enqueue(t);
	while(!Q.isEmpty())
	{
		Q.dequeue(t);
		cout<<t->key<<" ";
		if(t->left!=0)
			Q.enqueue(t->left);
		if(t->right!=0)
			Q.enqueue(t->right);
	}
}

template<class T>
void BinaryTree<T>::preOrder(BSTNode<T>* r)
{
	if(r)
	{
		cout<<r->key<<' ';
		preOrder(r->left);
		preOrder(r->right);
	}
}
template<class T>
void BinaryTree<T>::iterativePreOrder()
{
 	BSTNode<T>* t=root;
    Stack<BSTNode<T>*> s(10);

	//s.push(t);
	while(t)                //不能以栈空作为判断条件
	{
		cout<<t->key<<"  ";
		if(t->right!=0)
			s.push(t->right);
		if(t->left!=0)
			t=t->left;
		else if(s.pop(t));
		else
			break;
	}
 /*   //课本上的
	Stack<BSTNode<T>*> travStack(10);
    BSTNode<T> *p = root;
    if (p != 0) {
        travStack.push(p);
        while (!travStack.isEmpty()) {
            travStack.pop(p);
            cout<<p->key<<' ';
            if (p->right != 0)
                 travStack.push(p->right);
            if (p->left != 0)             // left child pushed after right
                 travStack.push(p->left); // to be on the top of the stack;
        }
    }*/
}

template<class T>
void BinaryTree<T>::inOrder(BSTNode<T>* r)
{
	if(r)
	{
		inOrder(r->left);
		cout<<r->key<<' ';
		inOrder(r->right);
	}
}
template<class T>
void BinaryTree<T>::iterativeInOrder() //非递归的中序树确实麻烦，我的程序还很不成熟
{
	//课件上的，太强了
	Stack<BSTNode<T>*>  s(10);
	BSTNode<T> *p=root;
	while(p||!s.isEmpty())
	{
		if(p){s.push(p);p=p->left;}
		else{
			s.pop(p);
			cout<<p->key<<"  ";
			p=p->right;  }
	}
/*  //课本上的，
    Stack<BSTNode<T>*> travStack(10);
    BSTNode<T> *p = root;
    while (p != 0) {
        while (p != 0) {                 // stack the right child (if any)
            if (p->right)                // and the node itself when going
               travStack.push(p->right); // to the left;
            travStack.push(p);
            p = p->left;
        }
        p = travStack.pop();             // pop a node with no left child
        while (!travStack.empty() && p->right == 0) { // visit it and all nodes
            visit(p);                                 // with no right child;
            p = travStack.pop();
        }
        visit(p);                        // visit also the first node with
        if (!travStack.empty())          // a right child (if any);
             p = travStack.pop();
        else p = 0;
    }*/

/*	我写的，有问题
    BSTNode<T>* t=root;
	int flag=0;
    Stack<BSTNode<T>*> s(10);

	while(t)
	{
		if(t->left!=0&&flag==0)
		{
			if(t->right!=0)
			{
			    s.push(t->right);
			    s.push(t);
				t=t->left;
			}
		}
		else
		{
			if(t->right!=0)
			{
			    flag=0;
			    cout<<t->key<<"   ";  
				t=t->right;
			}
			else 
				cout<<t->key<<"  ";
				
			if(t->right==0&&s.pop(t))                 //弹出来根节点          
			{
				if(t==root)
					flag=1;
				cout<<t->key<<"   ";    //打印根节点
			}
			else
			{
				t=t->right;
			}
			if(s.pop(t))                 
			{
				if(t==root)
					flag=1;
				continue;
			}
		}
	}*/
}

template<class T>
void BinaryTree<T>::postOrder(BSTNode<T>* r)
{
	if(r)
	{	
		postOrder(r->left);
		postOrder(r->right);
		cout<<r->key<<' ';
	}
}

template <class T>
void BinaryTree<T>::iterativePostOrder() //比较难啊
{
	Stack<BSTNode<T>*> s(20);
	BSTNode<T>* p=root,*q=root;
	
	while(p!=0)
	{
		for(;p->left!=0;p=p->left)
		s.push(p);
		while(p!=0&&(p->right==0||p->right==q))
		{
		    cout<<p->key<<"  ";
		    q =p;
		    if(s.isEmpty())
			    return;
		    s.pop(p);
	    }
		    s.push(p);
		    p = p->right;
     }
}

template<class T>
BSTNode<T> * BinaryTree<T>::PreInToTree(BSTNode<T> *r,TNode<T>* ph,TNode<T>* ih)
{
	if(ih==0)
		return 0;

	T pRootKey=ph->info,iRootKey;         //所有的都是p代表前序，i代表中序
	TNode<T>* pLeftHead=ph->next,*pRightHead=ph->next;
	TNode<T>* iLeftHead=ih,*iRightHead=ih->next,*iRoot=ih;
    
	if(iRoot->info==pRootKey)
	{
		iLeftHead=0;
	}
    else
	{
	    for(;;iRoot=iRoot->next,iRightHead=iRightHead->next)
		{
		    if(iRightHead->info==pRootKey)
			{
			    iRootKey=iRightHead->info;
			    iRoot->next=0;
			    iRoot=iRightHead;
			    if(iRightHead->next!=0)
			        iRightHead=iRightHead->next;
		    	else
				    iRightHead=0;

		    	iRoot->next=0;
		    	delete iRoot;
		    	break;
			}
		}
	}
	int iLeftLength=0,iRightLength=0;
	TNode<T>* t;
	for( t=iLeftHead;t!=0;t=t->next)
	{
		iLeftLength++;
	}

	t=ph;
	for(int i=0;i<iLeftLength;i++)
	{
		pRightHead=pRightHead->next;
		t=t->next;
	}
	t->next=0;

    r=new BSTNode<T>(pRootKey);

	r->left=PreInToTree(r->left,pLeftHead,iLeftHead);
	r->right=PreInToTree(r->right,pRightHead,iRightHead);

	return r;
}

template<class T>
BSTNode<T> * BinaryTree<T>::InPostToTree(BSTNode<T> *r,TNode<T>* ih,TNode<T>* poh)
{
	if(ih==0)
		return 0;

	T poRootKey=poh->info,iRootKey;         //所有的都是p代表前序，i代表中序
	TNode<T>* poRightHead=poh->next,*poLeftHead=poh->next;
	TNode<T>* iLeftHead=ih,*iRightHead=ih->next,*iRoot=ih;
    
	if(iRoot->info==poRootKey)
	{
		iLeftHead=0;
	}
    else
	{
	    for(;;iRoot=iRoot->next,iRightHead=iRightHead->next)
		{
		    if(iRightHead->info==poRootKey)
			{
			    iRootKey=iRightHead->info;
			    iRoot->next=0;
			    iRoot=iRightHead;
			    if(iRightHead->next!=0)
			        iRightHead=iRightHead->next;
		    	else
				    iRightHead=0;
		    	iRoot->next=0;
		    	delete iRoot;
		    	break;
			}
		}
	}
	int iLeftLength=0,iRightLength=0;
	TNode<T>* t;
	for( t=iRightHead;t!=0;t=t->next)
	{
		iRightLength++;
	}

	t=poh;
	for(int i=0;i<iRightLength;i++)
	{
		poLeftHead=poLeftHead->next;
		t=t->next;
	}
	t->next=0;

    r=new BSTNode<T>(poRootKey);
	
	r->right=InPostToTree(r->right,iRightHead,poRightHead);
    r->left=InPostToTree(r->left,iLeftHead,poLeftHead);
	
	return r;
}
# endif