C++实现二叉树的基本操作

1、首先要定义两个类：结点类和二叉树类

结点类要有

1. 要存储的数据

2. 指针类型的左孩子

3. 指针类型的右孩子

4. 相应的构造函数

2、二叉树类的组成：

1. 建立树的函数

2. 遍历函数

3. 删除函数

4. 求结点数函数

5. 求树高函数

注：以上函数都分为私有和共有（删除函数除外），私有函数从当前结点出发，共有函数则将私有函数的当前结点置为根结点

3、建立树的函数的思路：采用递归的思想，遇到标识符表示该结点为空，否则开辟空间创建新结点，同时调用递归开辟左结点和右结点

4、前序遍历函数的思路：

1. 如果当前结点为空，结束

2. 访问当前结点

3. 采用递归访问左结点

4. 采用递归访问右结点

（注：中序遍历：1324，后序遍历：1342）

5、删除函数的思路：

1. 如果当前结点不为空，采用递归访问左结点和右结点

2. 回收当前结点的空间

6、求结点数函数的思路：

1. 如果当前结点为空，返回0

2. 如果当前结点的左右孩子都为空，放回1

3. 返回  左孩子的结点数+右孩子的结点数+1（递归）

7、求树高函数的思路：

1. 如果当前结点为空，返回0

2. 递归访问左孩子和右孩子

3. 比较左右孩子的高度，返回 较大值+1