二叉排序树_二叉树的遍历算法_平衡二叉树

最近复习了一下C语言，复习的过程中顺带重温了下数据结构的一些内容，一石二鸟呀！下面是类模板实现二叉排序树。二叉排序树

先定义节点类型和二叉树类型：

template<typename T>
class BinaryTree;

template<typename T>   //节点类的定义
class Node
{private:
	Node<T>*lchild, *rchild;
	T info;
 public:
	 Node()
	 {
		 lchild = NULL;
		 rchild = NULL;
	 }
	 Node(T data, Node<T>*left = NULL, Node<T>*right = NULL)
	 {
		 info = data;
		 lchild = left;
		 rchild = right;
	 }
	 friend class BinaryTree < T > ;
};

template<typename T>                 //二叉排序树类的定义     
class BinaryTree
{
	Node<T>*root;
	void Inorder(Node<T>*current);              
	void Insert(const T &data,Node<T>* &b);
	void Remove(const T &data, Node<T>* &a, Node<T>* &b);
	void Destory(Node<T>*current);                           //删除二叉排序树
public:
	BinaryTree(){ root = NULL; }
	~BinaryTree(){ Destory(root); }
	void Create(T*data, int n);                      //由数组创建二叉排序树，n是数组大小
	void InOrder(){ Inorder(root); }                  //中序遍历
	void Remove(const T&data){ Remove(data,root,root); }  //删除节点
};

上面定义的二叉排序树类中，涉及的一些简单操作：

template<typename T>
void BinaryTree<T>::Insert(const T &data, Node<T>* &b)  //递归法在二叉排序树中插入一个节点
{
	if (b == NULL)          //递归终止条件
	{
		b = new Node<T>(data);
		if (!b)
		{
			cout << "out of space!" << endl;
		}
	}
	else if (data < b->info)
		Insert(data, b->lchild);
	else
		Insert(data, b->rchild);
}

template<typename T>
void BinaryTree<T>::Inorder(Node<T>*current)  //中序遍历
{
	if (current != NULL)
	{
		Inorder(current->lchild);
		cout << current->info<<" ";
		Inorder(current->rchild);
	}
}

template<typename T>
void BinaryTree<T>::Create(T*data, int n)         //由数组创建二叉排序树，n是数组大小
{
	for (int i = 0; i < n; i++)
	{
		Insert(data[i],root);
	}
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-21929-1.html