数据结构 | 二叉树

一　二叉树的定义与特性

（一）二叉树的定义

  二叉树由结点的有限集合组成。这个集合：

• 可以为空；
• 可以由一个根结点和两棵不相交（指没有公共结点）的二叉树构成。

一些术语：

• 左子树和右子树-由一个结点引出的两棵不相交的二叉树。
• （结点$\mathbf{M}$的）子结点-（结点$M$的）各个子树的根结点。
• （结点$\mathbf{M}$的）父结点-若一个结点含有子结点$M$，则这个结点称为结点$M$的的父结点。
• 路径-如果一棵树的一串结点$n_1$，$n_2$，…，$n_k$有如下关系：结点$n_i$是$n_{i+1}$的父结点$(1 \leq i \lt k)$，就把$n_1$，$n_2$，…，$n_k$称为一条由$n_1$到$n_k$的路径。这条路径的长度是k-1。
• 祖先和子孙-如果有一条路径从结点$R$至结点$M$，那么$R$就称为$M$的祖先，$M$就称为$R$的子孙。因此，所有结点都是根结点的子孙，而根结点是它们的祖先。
• （结点$\mathbf{M}$的）深度-根结点到$M$的路径的长度。
• （树的）高度-最深结点的深度+1。
• （结点$\mathbf{M}$的）层数-（结点$M$的）深度。规定根结点层数为0，深度为0。
• 叶结点-没有非空子树的结点。
• 分支结点（内部结点）-至少有一个非空子树的结点。

  图F1形象地指出了上述术语以便理解。除了图中所指出的术语，还有

• 结点$A$、$C$、$E$是$G$的祖先；
• 结点$D$、$E$、$F$的层数是2，结点$A$的层数是0；
• 由$A$至$C$至$E$至$G$的这条边形成了一条长度为3的路径；
• 结点$D$、$G$、$H$、$I$是叶结点，结点$A$、$B$、$C$、$E$、$F$是内部结点；
• 结点$I$的深度是3；
• 这棵树的高度是4$\cdots$
  

  左子结点和右子结点需要明确区分，交换它们得到的新二叉树与原二叉树不同。

单击此处查看二叉树结点的抽象类声明

  下面是从教材中摘录的二叉树结点的抽象类声明。

// Binary tree node abstract class
template <typename E> class BinNode {
public:
  virtual ~BinNode() {} // Base destructor

  // Return the node's value
  virtual E& element() = 0;

  // Set the node's value
  virtual void setElement(const E&) = 0;

  // Return the node's left child
  virtual BinNode* left() const = 0;

  // Set the node's left child
  virtual void setLeft(BinNode*) = 0;

  // Return the node's right child
  virtual BinNode* right() const = 0;

  // Set the node's right child
  virtual void setRight(BinNode*) = 0;

  // Return true if the node is a leaf, false otherwise
  virtual bool isLeaf() = 0;
};

一些术语：

• 满二叉树-每一个结点或者是一个分支结点并且恰好有两个非空子结点，或者是叶结点。
• 完全二叉树-要求从根结点起每一层从左到右填充，一棵高度为$d$的完全二叉树除了$d-1$层以外，每一层都是满的。底层叶结点集中在左边的若干位置上。

  图F2展示了满二叉树（如图F2.a所示）和完全二叉树（如图F2.b所示）的示例。

（二）满二叉树定理

• 非空满二叉树的叶结点数等于其分支结点数加1；
• 一棵非空二叉树空子树的数目等于其结点数目加1。

  注意叶结点的两个空子树也要计入上述空子树的数目中。

---

二　遍历二叉树

（一）遍历方式

一些术语：

• 遍历-按照一定顺序访问二叉树的结点。
• 枚举-对每个结点都进行一次访问并将其列出。
• 前序遍历-先访问结点，然后访问其子结点。例如对图F1二叉树按照前序遍历枚举的结果是：ABDCEGFHI。
• 后序遍历-先访问结点的子结点（包括它们的子树），然后访问该结点。例如对图F1二叉树按照后序遍历枚举的结果是：DBGEHIFCA。
• 中序遍历-先访问左子结点（包括整棵子树），然后访问该结点，最后访问右子结点（包括整棵子树）。例如对图F1二叉树按照中序遍历枚举的结果是：BDAGECHFI。

  要将以上遍历方式用函数来实现，很自然想到递归函数。教材中列举了两种实现前序遍历的方法。

template <typename E>
void preorder(BinNode<E>* root) {
  if (root == NULL) return; // Empty subtree, do nothing
  visit(root);              // Perform desired action
  preorder(root->left());
  preorder(root->right());
}

template <typename E>
void preorder2(BinNode<E>* root) {
  visit(root);  // Perform whatever action is desired
  if (root->left() != NULL) preorder2(root->left());
  if (root->right() != NULL) preorder2(root->right());
}

  后者在递归前会检查空子树，如果为空，则不必递归。然而教材指出，这样只能有极少甚至没有任何性能改善，这是因为后者需要对结点的左右子结点连续访问两次。与此同时，当后者函数被传入空指针时，它将失败——这并不是一个安全可靠的设计。这意味着进行设计时，务必要使程序能够避免意外情况以提高安全性。此外，对于遍历算法的设计，好的设计要求只允许树类访问BinNode类。因此，可以为树类提供一个通用遍历函数，它把访问处理函数作为遍历函数的一个参数或者一个模板参数——这就是访问者模式。这种方法的主要问题是必须事先确定所有访问处理函数的“签名”，即它们的返回类型和参数。

（二）限制访问

  如何控制使用递归处理时只访问需要访问的数据呢？教材给出的方法是添加局部计算。也就是说，需要加入判断——一旦不满足需求条件，就立即返回而不进行下一步计算。

---

三　二叉树的实现

（一）使用指针实现二叉树

单击此处查看二叉树结点的实现

  下面是从教材中摘录的二叉树结点的实现。

// This is the file to include for access to the complete binary node
// template implementation

#include "BinNode.h"

// Simple binary tree node implementation
template <typename Key, typename E>
class BSTNode : public BinNode<E> {
private:
  Key k;                  // The node's key
  E it;                   // The node's value
  BSTNode* lc;            // Pointer to left child
  BSTNode* rc;            // Pointer to right child

public:
  // Two constructors -- with and without initial values
  BSTNode() { lc = rc = NULL; }
  BSTNode(Key K, E e, BSTNode* l =NULL, BSTNode* r =NULL)
    { k = K; it = e; lc = l; rc = r; }
  ~BSTNode() {}             // Destructor

  // Functions to set and return the value and key
  E& element() { return it; }
  void setElement(const E& e) { it = e; }
  Key& key() { return k; }
  void setKey(const Key& K) { k = K; }

  // Functions to set and return the children
  inline BSTNode* left() const { return lc; }
  void setLeft(BinNode<E>* b) { lc = (BSTNode*)b; }
  inline BSTNode* right() const { return rc; }
  void setRight(BinNode<E>* b) { rc = (BSTNode*)b; }

  // Return true if it is a leaf, false otherwise
  bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};

• 为了实现检索，在以上实现中加入了关键码。
• 像链表一样，二叉树的实现也可以使用可利用空间表，这需要重载new和delete操作符。

  注意到在以上实现中每一个结点都有两个指针，一个指向左子结点，另一个指向右子结点。但是二叉树中叶结点并不需要这样的两个指针。同时，在有的应用中，分支结点与叶结点被要求存储不同的数据。因此，为了节省空间、满足一些需求，区分叶结点和分支结点是必要的。
  教材介绍了两种实现方式，它们的区别是将traverse函数实现在树类还是结点子类。后者使用了复合设计模式（对象包含各种可能的动作处理），查看下面的代码以观察区别。

单击此处查看区分叶结点和分支结点的两种实现

  下面是从教材中摘录的区分叶结点和分支结点的两种实现。

// Test for variable nodes implemented with a composite design.
// The test vehicle is an expression tree.
// The program builds and traverses a simple tree.

#include "book.h"

typedef char Operator;
typedef string Operand;

// Node implementation with simple inheritance
class VarBinNode {   // Node abstract base class
public:
  virtual ~VarBinNode() {}
  virtual bool isLeaf() = 0;    // Subclasses must implement
};

class LeafNode : public VarBinNode { // Leaf node
private:
  Operand var;                       // Operand value

public:
  LeafNode(const Operand& val) { var = val; } // Constructor
  bool isLeaf() { return true; }     // Version for LeafNode
  Operand value() { return var; }    // Return node value
};

class IntlNode : public VarBinNode { // Internal node
private:
  VarBinNode* left;                  // Left child
  VarBinNode* right;                 // Right child
  Operator opx;                      // Operator value

public:
  IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
    { opx = op; left = l; right = r; } // Constructor
  bool isLeaf() { return false; }    // Version for IntlNode
  VarBinNode* leftchild() { return left; }   // Left child
  VarBinNode* rightchild() { return right; } // Right child
  Operator value() { return opx; }           // Value
};

void traverse(VarBinNode *root) {    // Preorder traversal
  if (root == NULL) return;          // Nothing to visit
  if (root->isLeaf())                // Do leaf node
    cout << "Leaf: " << ((LeafNode *)root)->value() << endl;
  else {                             // Do internal node
    cout << "Internal: "
         << ((IntlNode *)root)->value() << endl;
    traverse(((IntlNode *)root)->leftchild());
    traverse(((IntlNode *)root)->rightchild());
  }
}

// Test for variable nodes implemented with a composite design.
// The test vehicle is an expression tree.
// The program builds and traverses a simple tree.

#include "book.h"

typedef char Operator;
typedef string Operand;

// Node implementation with the composite design pattern
class VarBinNode {   // Node abstract base class
public:
  virtual ~VarBinNode() {}      //Generic destructor
  virtual bool isLeaf() = 0;
  virtual void traverse() = 0;
};

class LeafNode : public VarBinNode { // Leaf node
private:
  Operand var;                       // Operand value

public:
  LeafNode(const Operand& val) { var = val; } // Constructor
  bool isLeaf() { return true; }     // isLeaf for LeafNode
  Operand value() { return var; }    // Return node value
  void traverse() { cout << "Leaf: " << value() << endl; }
};

class IntlNode : public VarBinNode { // Internal node
private:
  VarBinNode* lc;                    // Left child
  VarBinNode* rc;                    // Right child
  Operator opx;                      // Operator value

public:
  IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
    { opx = op; lc = l; rc = r; } // Constructor

  bool isLeaf() { return false; }    // isLeaf for IntlNode
  VarBinNode* left() { return lc; }  // Left child
  VarBinNode* right() { return rc; } // Right child
  Operator value() { return opx; }   // Value

  void traverse() { //Traversal behavior for internal nodes
      cout << "Internal: " << value() << endl;
      if (left != NULL) left->traverse();
      if (right != NULL) right->traverse();
  }
};

// Do a preorder traversal
void traverse(VarBinNode *root) {
  if (root != NULL) root->traverse();
}

  两种实现各有千秋：

• 前者容易给树类添加新的方法；traverse函数需要枚举所有子类，这要求对子类很熟悉；添加子类时需要修改traverse函数；
• 后者添加新的方法时需要在涉及的子类中添加；traverse函数在子类中，由子类自行负责遍历的处理工作；添加子类时，无需修改过往的子类中的traverse函数，也无需关注其他子类（这是复合设计模式所赋予的优点）。同时，后者在使用时不能用NULL指针来调用，因为没有办法捕捉它——这个问题可以用享元模式实现空结点的方式来避免。

  如果结点子类对用户透明，应选用前者；如果有意将结点和树相互分开，不让树的用户知道结点的存在，则应选用后者。

（二）空间代价

• 在简单的基于指针的二叉树中，每个结点都有两个指针指向其子结点。对于有$n$个结点的这样的二叉树，设一个指针所占空间的大小为$P$，一个数据值所占的空间大小为$D$，那么总空间合计为$n(2P+D)$，结构性开销为$2Pn$。这样，结构性开销所占比例就是$2P/(2P+D)$。
• 在更加常见的实现方法中，结点不存储数据而仅存储指向这个数据的指针。也就是说，结点处存储三个指针，并且其中一个指针指向数据，另外两个指针指向子结点——这三个指针都是结构性开销，即$3P$；总空间则合计为$3P+D$——因此，结构性开销所占的比例就是$3P/(3P+D)$。
• 如果只有叶结点存储数据，就可以采用分支结点只存储两个指针，没有数据区，叶结点则只包含一个数据区，这样一来，总空间合计为$2Pn+D(n+1)$，结构性开销所占比例就是$2P/(2Pn+D(n+1))$。

  针对只有叶结点存储数据的情况，教材上有诸多关于区分叶结点和分支结点的讨论。注意到在上面的实现中，采用了虚函数isLeaf来标志结点类型，但是这样就有一个严重的缺陷——每个结点都增加了额外的空间开销，它的解决办法之一是用一位的空间区别：

• 使用结点值区域的一位来表示结点类型；
• 使用结点指针的一个空闲位存储结点类型（前提是编译器要求结构与类必须从字的边界开始，使得指针值的最后一位总是为0）；

  解决办法之二是使用叶结点数据代替指向叶结点的指针（如果叶结点的数据区比一个指针小）。这种办法（称为位压缩）用于空间非常有限的时候，但通常应该避免——它降低了可读性。

（三）使用数组实现完全二叉树

  由于完全二叉树的特性，有n个结点的完全二叉树只可能有一种形状。因此，每个结点的亲属在数组中的位置关系总是确定的（如图F3所示，图中数字就是这个结点在数组中的下标）。这样一来，就不需要指向左右子结点的指针了。

  设完全二叉树结点的总数为n，某结点的下标为r（介于0到n-1之间）。

• Parent(r)=⌊(r-1)/2⌋，当r ≠ 0时；
• Leftchild(r)=2r+1，当2r+1 < n时；
• Rightchild(r)=2r+2。当2r+2 < n时；
• Leftsibling(r)=r-1，当r为偶数时；
• Rightsibling(r)=r+1，当r为奇数并且r+1 < n时。

---

三　二叉检索树

  二叉检索树能够兼备插入与检索都很快的优点，它的时间代价取决于树的形状——对于平衡二叉树（高度尽可能小），它在平均情况下的插入时间代价和检索时间代价都是$\Theta(\log n)$；对于严重不平衡二叉树，它在最差情况下的插入时间代价是$\Theta(n)$，检索时间代价是$\Theta(n)$——因而优于线性表。它具有这样的条件：对于二叉检索树的任何一个结点，设其值为K，则该结点左子树中任意一个结点的值都小于K；该结点右子树中任意一个结点的值都大于或等于K。这样一来，如果按照中序遍历打印各个结点，就会发现它们是按从小到大的顺序排列的。
  基于这样的特点，从根结点开始检索K值，那么就应该遵循这样的流程：如果K等于根结点存储的值，则检索结束，否则就应该检索更深一层。如果K小于根结点的值，检索左子树；如果K大于根结点的值，检索右子树。以上过程重复直至K被找到或者遇到叶结点为止。如果遇到叶结点仍未找到K，则K不在该二叉检索树中。

单击此处查看二叉检索树的声明

  下面是从教材中摘录的二叉树检索树的声明。

// This file includes all of the pieces of the BST implementation

// Include the node implementation
#include "BSTNode.h"

// Include the dictionary ADT
#include "dictionary.h"

// Binary Search Tree implementation for the Dictionary ADT
template <typename Key, typename E>
class BST : public Dictionary<Key,E> {
private:
  BSTNode<Key,E>* root;   // Root of the BST
  int nodecount;         // Number of nodes in the BST

  // Private "helper" functions
  void clearhelp(BSTNode<Key, E>*);
  BSTNode<Key,E>* inserthelp(BSTNode<Key, E>*,
                              const Key&, const E&);
  BSTNode<Key,E>* deletemin(BSTNode<Key, E>*);
  BSTNode<Key,E>* getmin(BSTNode<Key, E>*);
  BSTNode<Key,E>* removehelp(BSTNode<Key, E>*, const Key&);
  E findhelp(BSTNode<Key, E>*, const Key&) const;
  void printhelp(BSTNode<Key, E>*, int) const;

public:
  BST() { root = NULL; nodecount = 0; }  // Constructor
  ~BST() { clearhelp(root); }            // Destructor

  void clear()   // Reinitialize tree
    { clearhelp(root); root = NULL; nodecount = 0; }

  // Insert a record into the tree.
  // k Key value of the record.
  // e The record to insert.
  void insert(const Key& k, const E& e) {
    root = inserthelp(root, k, e);
    nodecount++;
  }

  // Remove a record from the tree.
  // k Key value of record to remove.
  // Return: The record removed, or NULL if there is none.
  E remove(const Key& k) {
    E temp = findhelp(root, k);   // First find it
    if (temp != NULL) {
      root = removehelp(root, k);
      nodecount--;
    }
    return temp;
  }
  // Remove and return the root node from the dictionary.
  // Return: The record removed, null if tree is empty.
  E removeAny() {  // Delete min value
    if (root != NULL) {
      E temp = root->element();
      root = removehelp(root, root->key());
      nodecount--;
      return temp;
    }
    else return NULL;
  }

  // Return Record with key value k, NULL if none exist.
  // k: The key value to find. */
  // Return some record matching "k".
  // Return true if such exists, false otherwise. If
  // multiple records match "k", return an arbitrary one.
  E find(const Key& k) const { return findhelp(root, k); }

  // Return the number of records in the dictionary.
  int size() { return nodecount; }

  void print() const { // Print the contents of the BST
    if (root == NULL) cout << "The BST is empty.\n";
    else printhelp(root, 0);
  }
};

  在该类的私有域中包含了若干帮助函数。注意到当调用公有域的函数时，总是需要这些帮助函数来实现相应的功能。这是因为这些函数都含有将根结点迭代的函数递归操作。但是，我们无从得知根结点——它被置于私有域中，外部无法直接访问——也就无法在这些公有域的函数传参时加入根结点这一参数。这样一来，仅凭公有域的函数本身是无法实现递归的。因此，在私有域中定义一些帮助函数（将在下面呈现，可以观察到它们都有递归操作），这些函数都可以访问根结点。这样一来，利用这些帮助函数就能在公有域的函数中实现相应的功能。

  下面是7个帮助函数的实现。
clearhelp函数：递归地从最后一个结点开始上移释放，这是因为一个结点的子结点必须先于结点本身释放。

// Clean up BST by releasing space back free store
template <typename Key, typename E>
void BST<Key, E>::
clearhelp(BSTNode<Key, E>* root) {
  if (root == NULL) return;
  clearhelp(root->left());
  clearhelp(root->right());
  delete root;
}

inserthelp函数：递归地从根结点开始下移，将值插入到合适的位置。在整个插入过程中，每一次递归都将返回一个指针。除了表层的递归，其余递归所返回的指针都作为函数setLeft和setRight的参数；表层的递归返回的指针则赋予root = inserthelp(root, k, e);。实际上，从根结点到被插入结点的父结点，该路径上的各个结点都被赋予了相应的子结点指针值，这是不必要的（因为改变的只有被插入结点的父结点的子结点指针值），但由于该方法的简洁性，这些额外的赋值是值得的。

// Insert a node into the BST, returning the updated tree
template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::inserthelp(
    BSTNode<Key, E>* root, const Key& k, const E& it) {
  if (root == NULL)  // Empty tree: create node
    return new BSTNode<Key, E>(k, it, NULL, NULL);
  if (k < root->key())
    root->setLeft(inserthelp(root->left(), k, it));
  else root->setRight(inserthelp(root->right(), k, it));
  return root;       // Return tree with node inserted
}

getmin函数：根据二叉检索树的特性，寻找最小值只需要沿着左边的链不断向下移直到无法再向下移。

// Get the minimum value from the BST, returning a pointer to the node
template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::
getmin(BSTNode<Key, E>* rt) {
  if (rt->left() == NULL)
    return rt;
  else return getmin(rt->left());
}

deletemin函数：（注意到在这个函数的实现中，指向最小值结点min的指针被修改为指向结点min的右子结点，这样做没有改变二叉检索树的特性）

// Delete the minimum value from the BST, returning the revised BST
template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::
deletemin(BSTNode<Key, E>* rt) {
  if (rt->left() == NULL) // Found min
    return rt->right();
  else {                      // Continue left
    rt->setLeft(deletemin(rt->left()));
    return rt;
  }
}

removehelp函数：如果要删除一个特定的值为k的结点R，就需要先检索到R。如果它存在，那么就要分情况讨论：

• R没有子结点。将R的父结点指向R的指针改为NULL。
• R只有一个子结点。将R的父结点指向R的指针改为指向R的子结点。
• R有两个子结点。从某棵子树中找出一个能代替R的值。为了不改变二叉检索树的特性，这个值应当是大于（或等于）k的最小者，或者小于k的最大者。

为什么要选择大于（或等于）k的最小者，或者小于k的最大者？
  大于（或等于）k的最小者一定在被删除结点的右子树，小于k的最大者一定在被删除结点的左子树。它们都处于叶结点处，删除其一并不会改变二叉检索树的特性。将其一代替被删除结点——这个结点的值一定大于左子树的其它结点（因为它或者是左子树的最大者，或者是右子树（右子树的结点值一定都大于左结点)的结点），也一定小于或等于右子树的其它结点（同理）——因此代替并不会改变二叉检索树的特性。
  注意，如果这个代替值有重复，不能用左子树的结点来代替，因为会破坏二叉检索树的特性——它只允许右子树中有与根结点相等的值。因此，总是优先选取右子树中的结点，也就是大于（或等于）k的最小者进行代替。

// Remove a node with key value k
// Return: The tree with the node removed
template <typename Key, typename E>
BSTNode<Key, E>* BST<Key, E>::
removehelp(BSTNode<Key, E>* rt, const Key& k) {
  if (rt == NULL) return NULL;    // k is not in tree
  else if (k < rt->key())
    rt->setLeft(removehelp(rt->left(), k));
  else if (k > rt->key())
    rt->setRight(removehelp(rt->right(), k));
  else {                            // Found: remove it
    BSTNode<Key, E>* temp = rt;
    if (rt->left() == NULL) {     // Only a right child
      rt = rt->right();         //  so point to right
      delete temp;
    }
    else if (rt->right() == NULL) { // Only a left child
      rt = rt->left();          //  so point to left
      delete temp;
    }
    else {                    // Both children are non-empty
      BSTNode<Key, E>* temp = getmin(rt->right());
      rt->setElement(temp->element());
      rt->setKey(temp->key());
      rt->setRight(deletemin(rt->right()));
      delete temp;
    }
  }
  return rt;
}

findhelp函数：

// Find a node with the given key value
template <typename Key, typename E>
E BST<Key, E>::findhelp(BSTNode<Key, E>* root,
                              const Key& k) const {
  if (root == NULL) return NULL;          // Empty tree
  if (k < root->key())
    return findhelp(root->left(), k);   // Check left
  else if (k > root->key())
    return findhelp(root->right(), k);  // Check right
  else return root->element();  // Found it
}

printhelp函数：

// Print out a BST
template <typename Key, typename E>
void BST<Key, E>::
printhelp(BSTNode<Key, E>* root, int level) const {
  if (root == NULL) return;           // Empty tree
  printhelp(root->left(), level+1);   // Do left subtree
  for (int i=0; i<level; i++)         // Indent to level
    cout << "  ";
  cout << root->key() << "\n";        // Print node value
  printhelp(root->right(), level+1);  // Do right subtree
}