main.cpp

通用二叉搜索树

#include <iostream>
#include <string>
#include "genBST.h"
using namespace std;

int main()
{
	BST<int> intTree;
	int intVal;
	BST<char> PreInTree, PostInTree;
	string preorder, inorder, postorder;	// 前序、中序、后序遍历结果
//-------------------------------------------------------------------------
	cout << "Enter the values you want to insert the tree,enter end-of-file to end:\n";
	while ( cin >> intVal )
	{
		intTree.insertNode( intVal );
	}
	cout << "Display the tree(root on the left,leaves on the right):\n";
	intTree.displayTree();							  // 打印树
//-------------------------------------------------------------------------
	cout << "Breadth First traversal: ";              // 广度优先遍历
	intTree.breadthFirst();
//-------------------------------------------------------------------------
	cout << "\nPreorder traversal: ";                   // VLR——前序树遍历
	intTree.preOrderTraversal();
//-------------------------------------------------------------------------
	cout << "\nInorder traversal: ";                    // LVR——中序树遍历
	intTree.inOrderTraversal();
//-------------------------------------------------------------------------
	cout << "\nPostorder traversal: ";                  // LRV——后序树遍历
	intTree.postOrderTraversal();
//-------------------------------------------------------------------------
	cout << "\nThe number of the total nodes: ";                 // 统计节点数
	cout << intTree.nodesCount();
//-------------------------------------------------------------------------
	cout << "\nThe number of leaf nodes: ";                      // 统计叶子节点数
	cout << intTree.leafCount();
//-------------------------------------------------------------------------
	cout << "\nThe number of right children: ";                  // 统计右子节点数
	cout << intTree.rightChildCount();
//-------------------------------------------------------------------------
	cout << "\nThe height of the tree: ";                   // 计算树的高度
	cout << intTree.height();
//-------------------------------------------------------------------------
	cout << "\nDelete all leaves!\n";                        // 删除所有叶子节点
	intTree.deleteLeaves();
	cout << "All leaves have been deleted.Now display the tree:\n";
	intTree.displayTree();
//-------------------------------------------------------------------------
	cout << "Enter the element you want to search: ";   // 查找指定元素对应的节点
	cin.clear();
	cin >> intVal;
	if( intTree.search(intVal) )
		cout << "Data " << intVal << " has been found." << endl;
	else
		cout << "Data " << intVal << " hasn't been found." << endl;
//-------------------------------------------------------------------------
	cout << "Enter the element you want to delete: ";   // 查找节点并删除
	cin >> intVal;
	if ( intTree.findAndDeleteByMerging( intVal ) ){
		cout << "The value " << intVal << " has been deleted.Now display the tree:\n";
		intTree.displayTree();
	}
//-------------------------------------------------------------------------
	cout << "Enter preorder sequence: ";                  // 根据先序中序创建树
	cin >> preorder;					                                       
	cout << "Enter inorder sequence: ";
	cin >> inorder;		
    PreInTree.preInCreateTree( preorder, inorder );
	cout << "\nTree has been created by your preorder and inorder sequence.\n"
		 << "To validate,display the tree(root on the left,leaves on the right):\n";
	PreInTree.displayTree();
//-------------------------------------------------------------------------
	cout << "Enter postorder sequence: ";                  // 根据后序中序创建树
	cin >> postorder;                           
	cout << "Enter inorder sequence: ";
	cin >> inorder;		
    PostInTree.postInCreateTree( postorder, inorder );
	cout << "Tree has been created by your postorder and inorder sequence.\n"
		 << "To validate,display the tree(root on the left,leaves on the right):\n";
	PostInTree.displayTree();
//-------------------------------------------------------------------------
    cout << endl;
	return 0;
}