下面是其他函数的一个详解，+表示是public函数，-表示private

函数 作用
+ insert 插入一个元素
+ empty 二叉树是否为空
+ exists 判断元素是否存在
+ clear 非递归清空二叉树
+ erase 清除指定根节点及其所有子节点
+ size 元素数量
+ minmum 最小值
+ maxmum 最大值
+ max_length_between_node 最大节点距离
+ hight 树高度
- print_binary_tree 二叉树形式打印二叉树
- count_node 元素个数
- find 查找
- maxmum 最大节点
- minmum 最小节点
- successor 后继节点
- hight

3.1 insert

insert函数在二叉树的构造函数里已经用到了一次，利用数组构建一个二叉树。在那里对insert函数所作的行为进行了讲解，所以这里只放上函数

  1. template<typename T>
  2. void binary_tree<T>::insert(const T& data) {
  3.     if (0 != root_) {
  4.         tree_node* fast, * slow, * ptemp;
  5.         fast = slow = ptemp = root_;
  7.         while (fast != 0) {
  8.             slow = fast;
  9.             if (data < slow->data) {
  10.                 fast = slow->lchild;
  11.             }
  12.             else if (data > slow->data) {
  13.                 fast = slow->rchild;
  14.             }
  15.             else {
  16.                 fast = 0;
  17.             }
  18.             // else equal do nothing
  19.         }
  20.         if (data < slow->data) {
  21.             slow->lchild = new tree_node(data);
  22.             slow->lchild->parent = slow;
  23.         }
  24.         else if (data > slow->data) {
  25.             slow->rchild = new tree_node(data);
  26.             slow->rchild->parent = slow;
  27.         }
  28.         // else equal do nothing
  29.     }
  30.     else {
  31.         root_ = new tree_node(data);
  32.     }
  33. }

3.2 empty

检查二叉树是否为空，只需要判断是否存在根节点root_即可

  1. // 二叉树是否为空
  2. bool empty(void) const { 
  3.     return (NULL == root_); 
  4. }

3.3 exists

exists用来判断某个值是否存在，这个和insert的过程很类似，根据大小来判断，直到找到该值

  1. template<typename T>
  2. bool binary_tree<T>::exists(const T& data) const {
  3.     bool result = false;
  4.     tree_node* ptr = root_;
  5.     while (ptr != 0 && !result) {
  6.         if (ptr->data == data) {
  7.             result = true;                // 这里不再使用break来跳出循环
  8.         }
  9.         else if (ptr->data < data) {
  10.             ptr = ptr->rchild;
  11.         }
  12.         else {
  13.             ptr = ptr->lchild;
  14.         }
  15.     }
  16.     return result;
  17. }

3.4 clear

clear用来清空二叉树，既然用来清空二叉树，那就需要遍历。前面学习到了，遍历的3种方式中，最简单的方式就是先序遍历，所以这里就是用先序遍历的套路。

  1. template<T>
  2. void binary_tree<T>::clear(void) {
  3.     stack<tree_node *> node_stack;
  4.     node_stack.push(root_);
  5.     tree_node* tmp_node;
  6.     while (!node_stack.empty() ) {                // 先序遍历
  7.         tmp_node = node_stack.top();
  8.         node_stack.pop();
  9.         if (tmp_node->rchild!=0) {
  10.             node_stack.push(tmp_node->rchild);
  11.         }
  12.         if (tmp_node->lchild!=0) {
  13.             node_stack.push(tmp_node->lchild);
  14.         }
  15.         delete tmp_node;                    // 删除节点
  16.     }
  17. }

3.5 erase

关于这个函数，可能是作者写的时候思路太清晰，不知道这个erase到底应该实现什么样的功能，其源代码如下

  1. template<typename T>
  2. void binary_tree<T>::erase(const T& data) {
  3.     tree_node* iter = find(data);
  4.     //delete iter;
  5. }

上述的代码只找到了data所对应的根节点的位置，但是没有删除。我们在抹除一个节点的时候，要将它的所有子节点一并抹除掉，就像下面这幅图所示

三、二叉树其他函数 - 图1

所以，这部分的代码应该和clear类似，只不过此时的根节点是从find函数找到的根节点开始的了

  1. template<typename T>
  2. void binary_tree<T>::erase(const T& data) {
  3.     tree_node* iter = find(data);
  4.     stack<tree_node *> node_stack;
  5.     node_stack.push(iter);
  6.     tree_node* tmp_node;
  8.     while (!node_stack.empty() ) {                // 先序遍历
  9.         tmp_node = node_stack.top();
  10.         node_stack.pop();
  11.         if (tmp_node->rchild!=0) {
  12.             node_stack.push(tmp_node->rchild);
  13.         }
  14.         if (tmp_node->lchild!=0) {
  15.             node_stack.push(tmp_node->lchild);
  16.         }
  17.         delete tmp_node;                    // 删除节点
  18.     }
  19. }

3.6 size

size是计算元素数量的函数，内部使用count_node函数来实现

  1. template<typename T>
  2. int binary_tree<T>::size(void) const {
  3.     return count_node(root_);
  4. }

3.7 minmum

minmum：得到元素的最小值

之前已经说过了，这棵树是按照大小顺序排好的树了，所以其最左边的节点的值就是最小值

  1. template<typename T>
  2. T binary_tree<T>::minmum(void) const {
  3.     const tree_node* p = root_;
  4.     while (p->lchild) {
  5.         p = p->lchild;
  6.     }
  7.     return p->data;
  8. }

3.8 maxmum

maxmum：和minmum相对。最右边的值是其最大值

  1. template<typename T>
  2. T binary_tree<T>::maxmum(void) const {
  3.     const tree_node* p = root_;
  4.     while (p->rchild) {
  5.         p = p->rchild;
  6.     }
  7.     return p->data;
  8. }

3.9 height

height：树的高度

  1. template<typename T>
  2. int binary_tree<T>::hight(void) const {
  3.     return hight(root_);
  4. }

其中的height(root_)这句代码中的height是私有函数的height，其定义如下

  1. template<typename T>
  2. int binary_tree<T>::hight(const tree_node* _t) const {
  3.     if (_t == nullptr) {
  4.         return 0;
  5.     }
  6.     if (_t->lchild == nullptr && _t->rchild == nullptr) {
  7.         return 1;
  8.     }
  9.     return 1 + std::max<int>(hight(_t->lchild), hight(_t->rchild));
  10. }

三、二叉树其他函数 - 图2 上面的代码非常巧妙地利用了递归来计算树的高度，这部分是可以被记住的，因为之前的遍历都是利用的循环，而没有用到递归。现在用了递归以后，可以更加容易理解树的高度的计算过程。

三、二叉树其他函数 - 图3

3.10 max_length_between_node

max_length_between_node：节点之间的最大距离

还是上面那幅图的例子，看一下节点之间的距离如何计算，就像下面这幅图，节点c和节点g的距离是如何计算的？

节点距离6 = c的高度+g的高度

三、二叉树其他函数 - 图4

  1. template<typename T>
  2. int binary_tree<T>::max_length_between_node(void) const {
  3.     int max_length = 0;
  5.     const tree_node* ptree = root_;
  7.     list<tree_node*> listNode;
  9.     listNode.push_back(root_);
  10.     while (!listNode.empty()) {
  11.         auto pnode = listNode.front();
  12.         listNode.pop_front();
  13.         if (pnode->lchild != nullptr) {
  14.             listNode.push_back(pnode->lchild);
  15.         }
  16.         if (pnode->rchild != nullptr) {
  17.             listNode.push_back(pnode->rchild);
  18.         }
  19.         int tempBetween = hight(pnode->lchild) + hight(pnode->rchild);
  21.         max_length = std::max<int>(tempBetween, max_length);
  22.     }
  25.     return max_length;
  26. }

上述代码，只需要给定一个根节点，便可以根据height函数递归地找到其下面的最高的左子节点和右子节点，然后计算它们的高度之和

3.11 count_node

使用递归形式来进行计算节点数量

  1. template<typename T>
  2. int binary_tree<T>::count_node(const tree_node* ptree) const {
  3.     int num1, num2;
  4.     if (ptree == NULL)
  5.         return 0;
  6.     else {
  7.         num1 = count_node(ptree->lchild);
  8.         num2 = count_node(ptree->rchild);
  9.         return (num1 + num2 + 1);
  10.     }
  11. }

3.12 find

find函数和exists函数基本一样

  1. template<typename T>
  2. typename binary_tree<T>::tree_node* binary_tree<T>::find(const T& data) {
  3.     if (root_) {
  4.         tree_node* pfind = root_;
  5.         while (pfind) {
  6.             if (pfind->data == data) {
  7.                 return pfind;
  8.             }
  9.             else if (data < pfind->data) {
  10.                 pfind = pfind->lchild;
  11.             }
  12.             else
  13.                 pfind = pfind->rchild;
  14.         }
  15.     }
  16.     return NULL;
  17. }

3.13 minmum和maxmum

和之前的共有函数的minmum和maxmum一样

3.14 successor

目前不知道这个函数拿来干什么用，用处不算很大

  1. template<typename T>
  2. typename binary_tree<T>::tree_node* binary_tree<T>::successor(tree_node* t) const {
  3.     if (t->rchild) {
  4.         return minmum(t->rchild);
  5.     }
  6.     else
  7.     {
  8.         tree_node* fast = t->parent, * slow = t;
  9.         while (fast && fast->rchild == slow) {
  10.             slow = fast;
  11.             fast = fast->parent;
  12.         }
  13.         return fast;
  14.     }
  15. }

3.15 输出二叉树

下面的函数print_binary_tree是用来输出二叉树的，从bt作为根节点开始输出其子树

  1. template<typename T>
  2. void binary_tree<T>::print_binary_tree(ostream& out, const tree_node* bt, int depth) const {
  3.     // 用右左孩子的方式输出一颗树,先输出右孩子后输出左孩子
  4.     if (bt) {
  5.         print_binary_tree(out, bt->rchild, depth + 1);
  7.         if (depth == 0) {
  8.             out << bt->data << endl;
  9.         }
  10.         else if (depth == 1) {
  11.             out << " --" << bt->data << endl;
  12.         }
  13.         else {
  14.             int n = depth;
  15.             while (--n) {
  16.                 cout << "    ";
  17.             }
  18.             out << " --" << bt->data << endl;
  19.         }
  21.         print_binary_tree(out, bt->lchild, depth + 1);
  22.     }
  23. }

上述代码中有一个有趣的句子：out << bt->data << endl

这个out可不是cout写错了，而是本身就是一个ostream&类型的数据。这些ostream类型的数据通过符号<<连接起来向屏幕输出。

从上面的print_binary_tree衍生的函数是从根节点开始输出整棵树的

  1. template<typename T>
  2. void binary_tree<T>::print(ostream& out) const {
  3.     print_binary_tree(out, root_, 0);
  4. }

另外，涉及到输出的话一般要对<<进行重载，这个重载<<的代码如下

  1. template<typename T>
  2. ostream& operator<<(ostream& out, const binary_tree<T>& tree) {
  3.     tree.print(out);
  4.     return out;
  5. }