binarytree.h

用C++写的寻找公共祖先

//:BinaryTree.h
//************************************************************
//Designed by: Xinyun Yu	Date: 2006.4.16
//Head file for ADT BinaryTree
//************************************************************
#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <iostream>
#include <exception>
#include <string>

class TreeException : public std::exception{
public:
	TreeException(const std::string& msg = "") : std::exception(msg.c_str()) {}
};//end TreeException

class BinaryTree{
	//****************Struct TreeNode*****************
	struct TreeNode{
		char item;
		TreeNode* leftChild;
		TreeNode* rightChild;
	};//end TreeNode
	//************************************************
	TreeNode* root;//The pointer to the root of the tree
	bool findM, findN;//Determined whether to find character M and N, using in function findAncester
	bool setAn;//Determined whether have set ancester
public:
	//Constructor and destructor
	BinaryTree();
	~BinaryTree();
	//Public operations
	//Determined wheter the tree is empty, if empty return true
	bool isEmpty() const { return root == 0; }
	//Create a tree, an istream gives every node for the tree
	//Precondition: a valid istream, only one line
	//note: the tree should be empty
	virtual void createTree(std::istream& in) throw(TreeException);
	//Traverse every node of the tree in preorder using recursion(calling function preorder)
	//Calling function visit(TreeNode*) for each node
	//precondition: the visit function is inside the class implementation
	//note: the visit function may alter the tree
	virtual void preorderTraverse(void (BinaryTree::*visit)(TreeNode*)) throw(TreeException);
	//Traverse every node of the tree in inorder using recursion(calling function inorder)
	virtual void inorderTraverse(void (BinaryTree::*visit)(TreeNode*)) throw(TreeException);
	//Traverse every node of the tree in postorder using recursion(calling function postorder)
	virtual void postorderTraverse(void (BinaryTree::*visit)(TreeNode*)) throw(TreeException);
	//Traverse every node of the tree in level order
	virtual void levelTraverse(void (BinaryTree::*visit)(TreeNode*)) throw(TreeException);
	//Traverse every node of the tree not using recursion
	virtual void preorderTraverse2(void (BinaryTree::*visit)(TreeNode*)) throw(TreeException);
	virtual void inorderTraverse2(void (BinaryTree::*visit)(TreeNode*)) throw(TreeException);
	virtual void postorderTraverse2(void (BinaryTree::*visit)(TreeNode*)) throw(TreeException);
	//Print the whole tree in preorder
	virtual void prePrintTree();
	//Print the whole tree in inorder
	virtual void inPrintTree();
	//Print the whole tree in postorder
	virtual void postPrintTree();
	//Print the whole tree in level
	virtual void levelPrintTree();
	//Find the nearest ancester of two node, to save it into the third parameter
	//If find, return true, else return false
	//note: m should be different with n
	virtual bool findAncester(char m, char n, char& ancester);
protected:
	//Protected operations
	//Traverse every node of a tree, whose root given by the first parameter
	//In three orders, as follows
	void preorder(TreeNode* node, void (BinaryTree::*visit)(TreeNode*));
	void inorder(TreeNode* node, void (BinaryTree::*visit)(TreeNode*));
	void postorder(TreeNode* node, void (BinaryTree::*visit)(TreeNode*));
	//To create a tree
	//Precondition: a node to sepcify the root, and an istream to give the data
	void createTree(TreeNode* &node, std::istream& in);
	//To destroy a tree, whost root given by the first parameter
	void destroyTree(TreeNode* &node);
	//To print the item of a node
	void printNode(TreeNode* node);
	//Find the nearset ancester of two node, ancester given by the node
	bool findAncester(TreeNode* node, char m, char n, char& ancester);
};//end BinaryTree

//Overload the operator>>
//To input a tree, calling member function createTree in its implementation
std::istream& operator>>(std::istream& in, BinaryTree& T);

#endif //BINARYTREE_H
///:~