binarytree.h

数据结构二叉树实验

// BinaryTree.h: interface for the BinaryTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BINARYTREE_H__786398F0_058C_48FA_96CB_CB83F4139475__INCLUDED_)
#define AFX_BINARYTREE_H__786398F0_058C_48FA_96CB_CB83F4139475__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class BinaryTreeNode
{
    //友员函数
	friend class BinaryTree;
	friend class LinkedQueue;
public: 
	BinaryTreeNode(){
		LeftChild = RightChild = 0;//初始为空
	}
    BinaryTreeNode(const int& e){
	    data = e;
        LeftChild = RightChild = 0;//初始为空
	}
	BinaryTreeNode(const int& e, BinaryTreeNode *l, BinaryTreeNode *r){
	    data = e;
		LeftChild = l;
		RightChild = r;
	}
private:
	int data;
	BinaryTreeNode *LeftChild, *RightChild;
};



class BinaryTree  
{
public:
	BinaryTree();
	virtual ~BinaryTree();

    bool IsEmpty(){
		if(!root) return false;
	    return true;
	}
	BinaryTreeNode* Root() 
	{ return root;}
	void Delete(BinaryTreeNode *t); //删除整个二叉树

	 
	void PreOrder(BinaryTreeNode *s) const;  //前序输出,s为根节点
    void InOrder(BinaryTreeNode *s) const;   //中序输出
	void PostOrder(BinaryTreeNode *s) const;  //后序输出
	void LevelOrder(BinaryTreeNode *s) const; //逐层输出
	BinaryTreeNode* PreOrderInput();  //前序输入二叉树

	int Height(BinaryTreeNode *s) const;
	int NumberOfNode(BinaryTreeNode *s) const;
    BinaryTreeNode* MakeTree(int *pre, int *in, int length); //通过前中序创建树


	BinaryTreeNode *root; //根节点
	

};

//*************************************队列节点和类的声明****************************************
//此用法见程序5-4
class Node  
{
     friend class LinkedQueue;
     
public:
	Node(){}
	virtual ~Node(){}
private:
	BinaryTreeNode *element;
	Node *link; 

};


class LinkedQueue{
public:
	LinkedQueue(){front = last = 0;}
	~LinkedQueue(){}

	bool IsEmpty() const{
		return (front == 0);
	}
	bool IsFull() const;
	LinkedQueue& Add(BinaryTreeNode *t); //向队列最后插入一个节点
	BinaryTreeNode* Delete();//删除队列第一个节点，并返回删除节点的数据域BinaryTreeNode

private:
	Node *front, *last; //分别指向队列第一个节点和最后一个节点


};

#endif // !defined(AFX_BINARYTREE_H__786398F0_058C_48FA_96CB_CB83F4139475__INCLUDED_)