时间：2014.03.15
地点：基地
----------------------------------------------------------------------------------
一、二叉树的数组实现
二叉树的数组实现很简单，几条原则如下
1.根节点总是存储在数组的位置[0]处。
2.如果一个非根节点的数据存储在数组位置[i]处，那么它的父节点存储在[(i-1)/2]位置上（整除）。
3.如果某个节点存储在数组位置[i]处，那么它的左子节点存储在[2i+1]上，右节点存储在[2i+2]上。
----------------------------------------------------------------------------------
二、二叉树的非顺序表示
这样的二叉树由包含链接，我们得先设计一个二叉树节点的类，BinaryTreeNode，它的节点包含数据域，指向左右子节点的指针。整棵树表示为一个指向根节点的指针。可以简单实现如下：
template<typename T>
class BinaryTreeNode{
public:
||......
private:
T data_field;
BinaryTreeNode* left_field_;
BinaryTreeNode* right_field_;
};
当然我们还可以包含更多的信息，这根据需要而定，但上述这是最基本的结构。
下面进一步完善这个类的设计，在二叉树中我们还需要一些应用，比如，可能希望访问某个节点的值，获得某个节点的链接域值，或者我们还需修改节点的某些值，这样我们需要对应的设置器和获取器，同时，因为获取器返回的是引用或者指针，我们需要提供普通版和常量版的获取器。这样，像以上类的设计一下子增加了3*2（获取）+3（设置）=9个成员函数，另外，我们还想判断节点是否是叶节点，于是还加上一个is_leaf的成员函数。
----------------------------------------------------------------------------------
三、二叉树的工具函数
构建好二叉树类后，有时我们需要对二叉树进行操作，比如销毁，复制二叉树等。于是我们在加上一些针对树操作的工具函数。
1.销毁二叉树
前面我们说过，根节点代表一颗这样的二叉树，所以对于树的操作也是打根节点着手的，而根节点下面又可视为子树，也就是说，如果你想销毁一个二叉树，可以递归实现，停止条件是树为空：
（1）清空左子树，将它的所有节点销毁
（2）清空右子树，将它的所有节点销毁
（3）将根节点销毁。
（4）将根节点悬空。
具体实现如下：
template<typename T>
void TreeClear(BinaryTreeNode<T>*& root_ptr){
if (root_ptr != nullptr){
TreeClear(root_ptr->get_left_field());
TreeClear(root_ptr->get_right_field());
delete root_ptr;
root_ptr = nullptr;
}
}
2.复制一棵树
同样也是递归实现，停止条件是树为空，否则不断复制树：
因为是复制树，所以相当于要建一颗一模一样的树，而建树要用到数据域，指针域等基本信息，即更节点的链接方式也要有，所以，我们每次递归要得到一个左右指针，然后用数据域信息和指针域值去构建节点并把它们链接起来。
(1)使的l_ptr指向左子树的副本
(2)使得r_ptr指向右子树的副本
(3)有了左右子树的副本后加上根节点形成新树，并返回新树即根节点的指针
实现如下：
BinaryTreeNode<T>* TreeCopy(const BinaryTreeNode<T>* root_ptr){
BinaryTreeNode<T>* l_ptr;
BinaryTreeNode<T>* r_ptr;
if (root_ptr == nullptr)
return nullptr;
else{
l_ptr = TreeCopy(root_ptr->get_left_field());
r_ptr = TreeCopy(root_ptr->get_right_field());
return new BinaryTreeNode<T>(root_ptr->get_data_field(), l_ptr, r_ptr);
}
}