08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://www.voidcn.com/article/p-srsfcefa-vo.html

?

二叉树

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树有几点重要的性质：

• ?性质1：在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1)
• 性质2：深度为 k 的二叉树上至多含2k-1 个结点（k≥1）。
• 性质3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。
• 性质4：具有 n 个结点的完全二叉树的深度为log2n+1
• 性质5：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
  (1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2? 的结点为其双亲结点；
  (2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；
  (3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。

采用链式存储结构实现二叉树

链式存储二叉树

?

1.首先我们要构造可以表示二叉树的节点的结构 Binary_node

2.构造类二叉树 Binary_tree，并编写其几个基本的成员函数：

Empty()-检查树是否为空；clear()-将树清空；size()-得到树的大小；leaf_count()-得到叶子数目；height()-得到树高；

以及几个重要的成员函数：

Binary_tree(const Binary_tree<Entry>&original); 拷贝构造成员函数
Binary_tree &operator=(const Binary_tree<Entry>&original);重载赋值操作符
~Binary_tree();析构函数

?

3.分别编写遍历算法的成员函数

void inorder(void(*visit)(Entry &)); 中序遍历（LVR）
void preorder(void(*visit)(Entry &)); 前序遍历（VLR）
void postorder(void(*visit)(Entry &)); 后续遍历（LRV）

因为二叉树的性质，三种遍历算法我们都用递归实现，所以分别编写其递归函数

void recursive_inorder(Binary_node<Entry>*sub_root,void (*visit)(Entry &));
void recursive_preorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &));
void recursive_postorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &));

?

4.作为辅助，我们再编写一个print_tree的函数，用以以括号表示法输出
同样使用递归，编写递归函数void recursive_print(Binary_node<Entry>*sub_root);
几个重要的函数代码如下：

template<class Entry>
void Binary_tree<Entry>::inorder(void(*visit)(Entry &))
//Post: The tree has been traversed in inorder sequence
//Uses: The function recursive_inorder
{
	recursive_inorder(root,visit);
}

template<class Entry>
void Binary_tree<Entry>::recursive_inorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &))
//Pre:  sub_root is either NULL or points to a subtree of the Binary_tree
//Post: The subtree has been traversed in inorder sequence
//Uses: The function recursive_inorder recursively
{
	if(sub_root!=NULL){
		recursive_inorder(sub_root->left,visit);
		(*visit)(sub_root->data);
		recursive_inorder(sub_root->right,visit);
	}
}

template<class Entry>
void Binary_tree<Entry>::preorder(void(*visit)(Entry &))
//Post: The tree has been traversed in preorder sequence
//Uses: The function recursive_preorder
{
	recursive_preorder(root,visit);
}

template<class Entry>
void Binary_tree<Entry>::recursive_preorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &))
//Pre:  sub_root is either NULL or points to a subtree of the Binary_tree
//Post: The subtree has been traversed in preorder sequence
//Uses: The function recursive_preorder recursively
{
	if(sub_root!=NULL){
		(*visit)(sub_root->data);
		recursive_preorder(sub_root->left,visit);
		recursive_preorder(sub_root->right,visit);
	}
}

template<class Entry>
void Binary_tree<Entry>::postorder(void(*visit)(Entry &))
//Post: The tree has been traversed in postorder sequence
//Uses: The function recursive_postorder
{
	recursive_postorder(root,visit);
}

template<class Entry>
void Binary_tree<Entry>::recursive_postorder(Binary_node<Entry>*sub_root,void(*visit)(Entry &))
//Pre:  sub_root is either NULL or points to a subtree fo the Binary_tree
//Post: The subtree has been traversed in postorder sequence
//Uses: The function recursive_postorder recursively
{
	if(sub_root!=NULL){
		recursive_postorder(sub_root->left,visit);
		recursive_postorder(sub_root->right,visit);
		(*visit)(sub_root->data);
	}
}
template<class Entry>
void Binary_tree<Entry>::print_tree()
{
	recursive_print(root);
	cout<<endl;
}

template<class Entry>
void Binary_tree<Entry>::recursive_print(Binary_node<Entry>*sub_root)
{
	if(sub_root!=NULL){
		cout<<sub_root->data;
		cout<<"(";
		recursive_print(sub_root->left);
		cout<<",";
		recursive_print(sub_root->right);
		cout<<")";
	}

}
//其他函数见源码

程序结果

插入二叉树并实现中序、前序和后序遍历

?

AVL树

（编辑：ASP站长网）