main.cpp

以输入的正整数的值作为二叉排序树中的结点的数据场之值

#include <iostream>

template <class Type> 
struct BSTNode{  //二叉排序树的结点的表示。
 	Type data;  // 结点的数据场。 
	BSTNode *left;  //给出结点的左儿子的地址。 
	BSTNode *right;  //给出结点的右儿子的地址。
	BSTNode():left(NULL), right(NULL) {}
	BSTNode(const Type x):data(x), left(NULL), right(NULL) {}
	BSTNode(const Type x, BSTNode *L, BSTNode *R):data(x), left(L), right(R) {}
	~BSTNode() {}
};	

template <class Type>
class BinarySearchTree{
public:
	BinarySearchTree():Root(NULL) {}
	~BinarySearchTree() {FreeTree(Root);}
	int Insert(const Type & x) {return Insert(x, Root);}
	void FreeTree(BSTNode<Type> *T);
	void PrintInOrder () const;
protected:
	void PrintInOrder (const BSTNode<Type> *T) const;
	BSTNode<Type> *Root;
	int Insert(const Type & x, BSTNode<Type> *& T);
};

template <class Type>
void BinarySearchTree<Type>::FreeTree(BSTNode<Type> *T) {
	if (T != NULL) {
		FreeTree (T->right);
		FreeTree (T->left);
		delete T;
	}
}

template <class Type>
void BinarySearchTree<Type>::PrintInOrder() const {
	PrintInOrder (Root);
}

template <class Type>
void BinarySearchTree<Type>::PrintInOrder (const BSTNode<Type> *T) const {
	if (T->left != NULL) PrintInOrder(T->left);
	cout << T->data << ", " << endl;
	if (T->right != NULL) PrintInOrder(T->right);
}

template <class Type> 
int BinarySearchTree<Type>::Insert (const Type & x, BSTNode<Type> *& T) {
	if (T == NULL) {T = new BSTNode<Type> (x); return 1;}  //新结点插入。
   	else if (x < T->data) return Insert(x, T->left);  //转向左子树。   
	else if (x > T->data) return Insert(x, T->right);  //转向右子树。
 	return 0;  //若结点已经存在，返回不必重复插入标志。
}  //插入结点到以T为根的二叉排序树中去。插入成功返回1，插入失败返回0。



int main () 
{
	BinarySearchTree<int> bst;
	int elem, flag, k = 1, i = 1;

	cout << "input the number one by one, and input -1 to end." << endl;
	while (1) {
		cout << "Plese input " << i << "th number: ";
		cin >> elem;
		if (elem != -1) {
			flag = bst.Insert(elem);
			if (flag == 0) cout << "This number has been in the tree!" << endl;
			else i++;
		}
		else break;
	}

	cout << "Numbers in inorder:" << endl;
	bst.PrintInOrder();

	return 0;
}