跳至主要內容

二叉树

二叉树

二叉树是计算机科学中的一种基本数据结构。二叉树是一种有用的数据结构，可以快速存储排序数据并快速检索存储数据。二叉树由父节点（或叶子节点）组成，每个节点存储数据，并链接到最多两个其他子节点（叶子节点），在空间上可以表示为第一个节点下方，一个放在左侧，一个放在右侧。正是叶子节点与链接节点的关联关系，也称为父节点，使得二叉树成为一种高效的数据结构。左侧的叶子节点具有较小的键值（即用于在树中搜索叶子节点的值），而右侧的叶子节点具有相等或更大的键值。因此，树中最左侧的叶子节点具有最小值，而树中最右侧的叶子节点具有最大值。更重要的是，每个叶子节点都连接到两个其他叶子节点，它是一个新的、更小的二叉树的开始。 由于这种特性，可以通过在连续的叶子节点上递归调用搜索和插入函数，轻松地在二叉树中访问和插入数据。

二叉树典型的图形表示本质上是一个倒置的树。它从一个根节点开始，该节点包含原始的键值。根节点有两个子节点；每个子节点可能有自己的子节点。理想情况下，树的结构应该是完全平衡的，即每个节点左右两侧的子节点数量相同。完全平衡的树允许数据插入或检索的平均速度最快。最坏的情况是每个节点只有一个子节点的树，因此从速度上看，它就像一个链表。典型的二叉树表示如下：

     10
   /    \
  6      14
 / \    /  \
5   8  11  18

存储 10 的节点，这里仅表示为 10，是根节点，连接到左子节点和右子节点，其中左子节点存储的值小于父节点，右子节点存储的值大于父节点。请注意，如果移除根节点和右子节点，那么存储值 6 的节点将等效于一个新的小型二叉树。

二叉树的结构使得插入和搜索功能通过递归实现起来非常简单。事实上，这两个插入和搜索函数也非常相似。将数据插入二叉树涉及一个函数在树中搜索一个未使用的节点，以在适当的位置插入键值。插入函数通常是一个递归函数，它继续沿着二叉树的层级向下移动，直到在符合节点放置规则的某个位置找到一个未使用的叶子节点。规则是：较低值应该在节点的左侧，较高或相等的值应该在节点的右侧。遵循这些规则，插入函数应该检查每个节点是否为空，如果是，则将数据连同键值一起插入（在大多数实现中，一个空节点只是一个来自父节点的 NULL 指针，因此函数也必须创建该节点）。 如果节点已经填充，插入函数应该检查要插入的键值是否小于当前节点的键值，如果是，则递归调用左子节点上的插入函数；或者如果键值要插入的值大于或等于当前节点的键值，则递归调用右子节点上的插入函数。搜索函数的工作方式与此类似。它应该检查当前节点的键值是否是要搜索的值。如果不是，它应该检查要搜索的值是否小于节点的值，如果是，则递归调用左子节点；或者如果它大于节点的值，则递归调用右子节点。当然，在调用节点上的函数之前，也需要检查左子节点或右子节点是否实际存在。

因为二叉树有 log2n 层，所以二叉树的平均查找时间为 log2n。要填充一个完整的二叉树并使其有序，大约需要 log2n * n 的时间。让我们来看看实现一个简单二叉树所需的代码。首先，需要定义一个结构体或类，将其作为节点。

struct node
{
  int key_value;
  struct node *left;
  struct node *right;
};

结构体能够存储 key_value，并包含两个子节点，这些子节点定义了节点作为树的一部分。实际上，节点本身与链表中的节点非常相似。对链表代码的基本了解将有助于理解二叉树的技术。本质上，指针是必要的，以允许在树中任意创建新的节点。

二叉树上有几种重要的操作，包括插入元素、查找元素、删除元素和删除整棵树。在本教程中，我们将查看这四种操作中的三种，将删除元素留待以后处理。

我们还需要跟踪二叉树的根节点，这将让我们能够访问其余的数据：

struct node *root = 0;

必须将 root 初始化为 0，以便其他函数能够识别树尚未存在。下面所示的下述 destroy_tree 函数将实际释放存储在 node leaf: tree 下的所有节点。

void destroy_tree(struct node *leaf)
{
  if( leaf != 0 )
  {
      destroy_tree(leaf->left);
      destroy_tree(leaf->right);
      free( leaf );
  }
}

destroy_tree 函数会到达树的每个部分的底部，即当存在非空节点时进行搜索，删除该叶节点，然后向上工作。该函数先删除最左边的节点，然后删除最左边的节点的父节点的右子节点，接着删除父节点，然后向上工作以删除刚刚删除的节点的父节点的另一个子节点，并继续这种删除操作，向上工作至最初调用 delete_tree 的树的节点。在上面的示例树中，节点的删除顺序将是 5 8 6 11 18 14 10。请注意，必须删除所有子节点以避免浪费内存。

以下插入函数会在必要时创建新树；它依赖于指向指针的指针来处理树不存在的情况（根指针指向 NULL）。特别是，通过获取指向指针的指针，如果根指针为 NULL，就可以分配内存。

insert(int key, struct node **leaf)
{
    if( *leaf == 0 )
    {
        *leaf = (struct node*) malloc( sizeof( struct node ) );
        (*leaf)->key_value = key;
        /* 将子节点初始化为null */
        (*leaf)->left = 0;    
        (*leaf)->right = 0;  
    }
    else if(key < (*leaf)->key_value)
    {
        insert( key, &(*leaf)->left );
    }
    else if(key > (*leaf)->key_value)
    {
        insert( key, &(*leaf)->right );
    }
}

插入函数会搜索，沿着子节点树向下移动，遵循规定规则，左子节点用于插入较小值，右子节点用于插入较大值，直到到达一个空节点——一个 NULL 节点——为其分配内存并使用键值初始化，同时将新节点的子节点指针设置为 NULL。创建新节点后，插入函数将不再调用自身。请注意，如果元素已在树中，则不会重复添加。

struct node *search(int key, struct node *leaf)
{
  if( leaf != 0 )
  {
      if(key==leaf->key_value)
      {
          return leaf;
      }
      else if(key<leaf->key_value)
      {
          return search(key, leaf->left);
      }
      else
      {
          return search(key, leaf->right);
      }
  }
  else return 0;
}

上述搜索函数会递归地沿着树向下移动，直到找到键值等于要搜索值的节点，或者直到函数到达一个未初始化的节点，这意味着要搜索的值未存储在二叉树中。它将指向节点的指针返回给调用它的函数的前一个实例。