快速二叉树操作

• 下载演示项目 - 85.1 KB
• 下载源文件 - 22.2 KB

目录

1. 引言
2. 背景
3. 代码描述
4. 类使用
5. 树的负载均衡
6. 示例演示
7. 源代码文件
8. 参考文献
9. 感谢...

简介

在本文中，我将向您展示如何使用二叉搜索树来存储数据。我使用了模板来处理键和数据值，以简化任何数据类型的用法。如果您对二叉搜索树背后的理论有丰富的经验，您可以跳过下一节（背景）。

背景

[1] 二叉搜索树是一种数据结构，它支持许多动态集合操作，包括搜索、插入、删除、最小值、最大值、前驱和后继。二叉搜索树的基本操作所需时间与树的高度成正比。对于具有 n 个节点的完全二叉树，此类操作在最坏情况下需要 O(log n) 时间，因为随机构建的二叉搜索树的高度与 log n 成正比。在某些情况下，对于排序输入，操作需要 O(n) 时间，因此树将类似于排序列表，因此我使用了红黑树的平衡技术，如树的负载均衡部分所述。

二叉搜索树组织在一棵二叉树中，如图 1 所示。这样的树可以用链式数据结构表示，其中每个节点都是一个对象。除了key字段外，每个节点还包含left、right和parent字段，分别指向其左子节点、右子节点和父节点所对应的节点。如果某个子节点或父节点不存在，则相应字段包含值NIL。

我不会在这里深入探讨所有**二叉树**函数，我将仅引用search函数，您可以查阅参考文献[1]了解更多详细信息，并且我将在代码描述中谈论其中一些函数，因为其中许多函数都非常复杂，例如Delete函数。

搜索

二叉搜索树中最常见的操作是搜索存储在树中的键，这可以通过两种方式完成

1. 递归

   Node Search(Node, key)
   {
       if Node = NIL or key = Node.key
           return Node
       if key < Node.key
           then return Search(Node.Left, key)
           else return Search(Node.Right, key)
   }

2. While循环

   Node Search(key)
   {
       Node = root
       while Node != NIL and key != Node.key 
           do if key < Node.key
               then Node = Node.Left
               else Node = Node.Right        
       return Node
   }

这两种方式都从根节点开始搜索，并在树中向下追踪路径，直到找到key或返回NIL（未找到的情况）。第一种方式的代码更简单，但第二种方式优化了堆栈使用，我倾向于在所有情况下都使用第二种方式来处理大量数据，而不会影响堆栈和性能。

代码描述

所有Tree函数都封装在模板类CBinaryTree和CBinaryTreeNode中。

GetCount	返回带有重复项的树节点计数（重复的键将分配给一个节点）
RemoveAll	删除所有树节点
Insert	将新的key插入树中
搜索	在树中搜索key
最小值	获取输入节点下方的最小节点键
最大值	获取输入节点下方的最大节点键
后继	获取节点的后继（在整体树排序中紧随其后的节点）
前驱	获取节点的前驱（在整体树排序中排在前面的节点）
删除	从树中删除节点并调整其子节点
保存	将所有树节点的顺序保存到整数向量中

在我所有的代码中，我避免使用递归函数以避免堆栈溢出，因为我处理的是大量数据，所以您会发现我的所有代码都使用while循环，有时代码会变得复杂，例如RemoveAll函数。

RemoveAll 函数

此函数删除所有树节点，它按顺序要求每个节点删除其left子节点，然后删除其right子节点，最后删除自身。这可以通过两种方式完成

1. While循环

   // remove all tree nodes
   void RemoveAll()
   {
       TREENODE *node = Root, *pTemp;
       while(node != Nil)
       {
           // check for left child
           if(node->Left != Nil)
               node = node->Left;
           // check for right child
           else    if(node->Right != Nil)
               node = node->Right;
           else    // node has no childs
           {    // save node pointer
               pTemp = node;
               // set node pointer at its parent to NULL
               if(node->Parent != Nil)
                   node->Parent->Childs[node != node->Parent->Left] = Nil;
               // update pointer node to its parent
               node = node->Parent;
               // delete the saved node
               delete pTemp;
           }
       }
       Count = Serial = 0;
       Root = Nil;
       Modified = false;
   }

   正如您所见，此部分（节点没有子节点）存在一些复杂性。

2. 递归方式

   它在每个节点析构函数中简单地放置delete left和right节点，并调用树根的delete。

   ~CBinaryTreeNode()
   {
       if(Childs[0])
           delete Childs[0];
       if(Childs[1])
           delete Childs[1];
   }
   // ...
   delete Tree.Root;

   所有节点都将通过堆栈使用自动删除，但如果您阅读第一种方式代码中的注释，您会发现它很容易理解，并且可以避免堆栈使用。

Min 函数

节点x的最小值可以通过从节点x开始沿着left子节点一直找到Nil为止来找到，如下面的代码所示

// return minimum key in the tree
TREENODE* Min(TREENODE* node) const
{    
    // iterate in the left branch
    while(node != Nil && node->Left != Nil)
        node = node->Left;
    return node;
}

Successor 函数

节点x的后继是键大于key[x]的最小节点。例如，如果您按顺序添加键（C I D H B F E G A J K），树将如图所示

每个箭头表示从每个节点到其后继的方向。Successor函数中的代码包含两个路径

1. 如果节点有右子节点，则返回右子树中最左侧的节点。
2. 否则，它从节点向上移动，直到找到一个节点，该节点在其父节点的左侧。

TREENODE* Successor(TREENODE* node) const
{
       // return the left most node in the right sub tree
    if(node->Right != Nil)
        return Min(node->Right);
    // go up from node until we find a node that is the left of its parent
    TREENODE* Parent = node->Parent;
    while(Parent != Nil && node == Parent->Right)
    {
        node = Parent;
        Parent = node->Parent;
    }
    return Parent;
}

您可以将Successor函数与Min函数一起使用，以升序迭代树节点。

Delete 函数

Delete函数有三种情况，我发现它非常复杂，我希望我能描述它，这三种情况是

1. 节点没有子节点，所以我们直接删除它。如图 2 所示，节点 K 可以通过简单地重置节点J的指针来删除。
2. 节点只有一个子节点，所以我们需要将其“剪接”掉，如图 2 中的节点H所示，我们应该使节点D指向节点F作为其右子节点，并设置节点F的父节点指向节点D。
3. 节点有两个子节点，所以我们选择其后继来取代其位置，并“剪接”掉其后继（连接后继的父节点和子节点，如前一种情况）。例如，如果我们删除图 2 中的节点C，我们会得到节点C的后继（D），因此我们将“剪接”掉节点D，使得节点I和H直接连接，而节点C将取代节点C的位置，如图 3 所示。

   

Delete中的代码经过优化，可以一次处理三种情况，所以我觉得在这里很难描述它，但您可以尝试将代码应用到每种情况中并仔细阅读注释，您会发现它工作得很好。

void Delete(TREENODE* node)
{    
    TREENODE *pSplice = (node->Left == Nil || 
              node->Right == Nil)?node:Successor(node);
    TREENODE *pChild = pSplice->Childs[pSplice->Left == Nil];
    // connect child to spliced node parent
    if(pChild != Nil)
        pChild->Parent = pSplice->Parent;
    // connect spliced node parent to child
    if(pSplice->Parent == Nil)
        Root = pChild;
    else
        pSplice->Parent->Childs[pSplice !=
                   pSplice->Parent->Childs[0]] = pChild;
    // put spliced node in place of node (if required)
    if(pSplice != node)
    {    // copy spliced node
        *node = *pSplice;
        // delete the spliced node
        delete pSplice;
    }
    else
        // delete the node
        delete node;
    Count--;
}

迭代树节点

您可以调用Min(Tree.Root)，然后在一个循环中调用Successor来按升序检索所有节点。

TREENODE* node = Min(Root);
while(node)
{ 
    // use node here then get next one
    node = Successor(node);
}

同样，您可以调用Max(Tree.Root)，然后在一个循环中调用Predecessor来按降序检索所有节点。

TREENODE* node = Max(Root);
while(node)
{ 
    // use node here then get next one
    node = Predecessor(node);
}

类使用

CBinaryTree的使用非常简单，我们只需要决定KEY和DATA的数据类型，然后您可以定义类，但您必须选择一个支持compare函数的KEY，因为它在Insert和Search函数中使用。例如

CBiaryTree<string, LPCSTR, int, int> tree;
tree.NoRepeat = true;
for(...)
{
    // ... fill str in some way
    tree.Insert(str);
}

STL 的class String支持compare函数，但在某些情况下，您必须自己添加它，例如整数排序。

class CInt
{
public:
    int m_nKey;
    int compare(int nKey) 
    { return nKey == m_nKey ? 0 : (nKey >= m_nKey ? -1 : 1); }
    void operator=(int nKey) { m_nKey = nKey; }
    bool operator==(int nKey) { return m_nKey == nKey; } 
}; 

CBiaryTree<CInt, int, int, int> tree;
tree.NoRepeat = true;
for(...)
{
    // ... fill n in some way
    tree.Insert(n);
}

树的负载均衡

树的平衡可以使用多种技术来实现。在我的类中，我使用了红黑树函数来进行树的插入。红黑树主要依赖于使树的高度尽可能短，因为搜索和插入操作的时间取决于树的高度。如图所示，如果按顺序（C, A, B）向树中添加元素，则高度将是情况 1，但如果我们有一个操作将其更改为情况 3 中的有效树，这将是好的，因为树的高度减小了。

因此，我包含了LeftRotate、RightRotate和RBInsert函数来平衡树函数。

示例演示

随文章一起附带的源 zip 文件包含一个示例，该示例以递归函数解析任何文件夹，并解析其扩展名为扩展编辑器（任何文本文件格式）的所有文件，然后将所有文件令牌添加到二叉树中。然后，您可以通过树控件导航所有树令牌。您可以在 VC6 或 7.1 中测试它，或者直接运行附带的 EXE，如有任何帮助，请随时给我发邮件。

源文件

1. BinaryTree.h：二叉树代码
2. RBTree.h：红黑树代码

参考文献

• [1] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Algorithms 1990

鸣谢

我非常感谢我的同事们在实现和测试此代码方面提供的帮助。（JAK）

许可证

本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。

作者可能使用的许可证列表可以在此处找到。