二叉树的结构相比于链表而言复杂了很多，这里同样从最开始对它来进行抽丝拨茧地进行探讨。

1.1 二叉树节点

需要一棵树，首先就要把它打造出来。链表是由一个一个的节点组成的，而二叉树是由一个一个的树子节点构成的，在这方面它们极为类似。参考链表和节点的写法，要把树子节点放到二叉树中进行定义。

可以看到，一棵树的节点有4个数据

• parent：指向父节点的指针
• lchild：指向左子节点的指针
• rchild：指向右子节点的指针
• data：该节点的数据

class binary_tree {
    class tree_node;
private:
    struct tree_node {        // 定义树节点
        tree_node *parent, *lchild, *rchild;
        T data;
        tree_node() : data(T()),parent(NULL),lchild(NULL),rchild(NULL) { }        
        tree_node(const T& t) : data(t),parent(NULL),lchild(NULL),rchild(NULL) { }
    };
};

上述的第一个构造函数tree_node() : data(T()),parent(NULL),lchild(NULL),rchild(NULL) { }使用了data(T())临时对象T()对data进行赋值

1.2 二叉树构造函数

🌴 构造函数1（默认构造函数）

相比于链表的插入式增长，二叉树是一种迭代式的扩充，由一开始的一个根节点不断长出来别的叶子节点。所以，二叉树的构造函数中只需要有一个根节点即可

class binary_tree {
public:
    binary_tree(void) : root_(nullptr) { }            // 默认构造函数1


private:
    tree_node* root_;
};

🌴 构造函数2：利用数组创建一棵二叉树

解释一下为什么能够使用数组来创建二叉树，将数组看成是二叉树逆向旋转了45°后的结构即可。看起来很简单的一个操作，但是实现起来也是很有难度的

class binary_tree {
public:
    binary_tree(const T*, const int);        // 从数组构造一颗二叉树
};

下面看一下利用数组构建二叉树的实现

// 利用数组构建二叉树
template<typename T>
binary_tree<T>::binary_tree(const T* arr, const int length) : binary_tree() {
    for (int i=0; i<length; ++i) {
        insert(arr[i]);
    }
}

insert函数源码

🎭从上面可以看到上述的arr代表的是指向数组的首元素的指针，length表示的是数组的长度。对数组进行遍历，然后将数组的元素利用insert插入到二叉树中。

这个插入的动作是由insert来完成的，insert的代码如下

template<typename T>
void binary_tree<T>::insert(const T& data) {
  if (0 != root_) {
    tree_node *fast, *slow, *ptemp;
    fast = slow = ptemp = root_;

    while (fast != 0) {
      slow = fast;
      if (data < slow->data) {
        fast = slow->lchild;
      }
      else if (data > slow->data) {
        fast = slow->rchild;
      }
      else {
        fast = 0;
      }
      // else equal do nothing
    }

    if (data < slow->data) {
      slow->lchild = new tree_node(data);
      slow->lchild->parent = slow;
    }
    else if (data > slow->data) {
      slow->rchild = new tree_node(data);
      slow->rchild->parent = slow;
    }
    //esle equal do nothing
  }
  else {
    root_ = new tree_node(data);
  }

}

insert函数解释

关于这个insert函数需要解读一下，他做的工作为：判断父节点和子节点的大小关系，小的放左边，大的放右边。之前的链表是使用一个首指针和尾指针以及一个大小来管理节点的。

同理，树的扩展也需要一些辅助工具。这些辅助工具就是上述代码里的3个指针（实际代码里有用的只有fast和slow两个指针，这部分需要推敲一下原作者的意思）

• fast指针用来根据数据的大小指明方向，比父节点数据大的放到右子节点上，比父节点数据小的放到左子节点上，相等的就重新建立一棵树。
• slow指针跟在fast指针后面进行插入相对位置的节点（就好像种地的时候，一个人在刨坑一个人在撒种子一样）

// 3个辅助二叉树生长的指针
tree_node *fast, *slow, *ptemp;

现在，拿一个数组过来看一下这棵树生长过程

先生长出一颗根节点

在根节点的基础上生长第1个节点

在根节点的基础上生长第2个节点

在根节点的基础上生长第3个节点

🌴 构造函数3：拷贝构造和拷贝赋值（不严谨）

class binary_tree {
public:
    binary_tree(const binary_tree&);                        // 拷贝构造
    binary_tree& operator = (const binary_tree&);            // 拷贝赋值
};

下面看一下两种函数的实现

// 1.拷贝构造
template<typename T>
inline binary_tree<T>::binary(const binary_tree& from): root_(nullptr) {
    if (from.empty()) {
        return ;
    }
    // 使用层次遍历来进行拷贝
    list<tree_node*> listNode;
    listNode.push_back(from.root_);
    while(!listNode.empty()) {
        listNode.front();
    }
    tree_node* p = minmum(from.root_);
    insert(p->data);
    while (p=successor(p)) {
        insert(p->data);
    }
}


// 2.拷贝赋值
template<typename T>
inline binary_tree<T>& binary_tree<T>::operator=(const binary_tree& from) {
    if (this==&from) {
        return *this;
    }
    clear;

    tree_node* p = minmum(root_);
    cout << p->data << " ";
    while (p=successor(p)) {
        cout << p->data << " ";
    }
    return *this;
}

原作者的拷贝构造的代码有问题，所以这里需要更正一下，但是这部分涉及到后面的遍历函数（没有遍历怎么拷贝嘛 ），所以先耐心将后面的代码看一下

1.3 析构函数

析构函数代码如下，建议先看完后面的遍历后再看析构

~binary_tree(void) { clear(); }//析构函数

其中的clear函数代码如下

template<typename T>
void binary_tree<T>::clear(void) {
    // 先序遍历删除一颗树的全部结点值1,2,3,先根遍历
    if (root_) {
        stack<tree_node*> node_stack;
        node_stack.push(root_);
        tree_node* t;
        while (!node_stack.empty()) {
            t = node_stack.top();
            node_stack.pop();
            if (t->rchild != 0) {
                node_stack.push(t->rchild);
            }
            if (t->lchild != 0) {
                node_stack.push(t->lchild);
            }
            delete t;
        }
        root_ = NULL;
    }
}