字符串二叉搜索树

Question

字符串二叉搜索树

binary-treebinary-search-tree

3

我有一本书，讲解二叉搜索树的理论非常糟糕。我知道左右子节点的顺序有关系，但我仍然不能理解一个子节点比前一个级别的子节点大的概念。

以这个字符串树为例：

Binary tree of names

（抱歉我画得不好）这个例子直接摘自我的书。

谁能向我解释这个顺序？这背后的逻辑是什么？

- Marc Rasmussen

2

如果示例树中确实有两个“Karen”节点，则从技术上讲它不是BST，因为不允许重复节点。 - mellamokb

6个回答

2

对于任何一个节点（例如根节点Karen），左子树中的每个节点（Bob，Alan，Ellen）在字典序上都比Karen小，右子树中的每个节点（Tom，Wendy）都比Karen大。

正如@mellamokb在评论中指出的那样，第二个Karen不应该存在。

因此，您可以像对待排序数组一样，在O(log N)时间内对该树进行二进制搜索。

- irrelephant

1

第二个条件不一定从第一个条件中得出。例如，如果根是“Karen”，那么从“Karen”向左的是“Bob”，然后从“Bob”向右的是“Tom”，它将满足您的第一个条件，但不满足第二个条件。BST必须被定义为具有所有节点在左/右子树中小于/大于父节点。 - mellamokb

1

在字符串的二叉搜索树实现中，字符串按字典顺序存储。例如，如果有三个字母（'K'、'I'和'N'）以不同的字符串数据类型存储，并按相同的顺序插入，则'K'将成为父节点，其左子节点为'I'，右子节点为'N'，因为在字母表顺序中，'I'在'K'之前，'N'在'K'之后（图1）。对于单词也是如此：“Linked”将作为“List”的左子节点存储，或者“List”将作为“Linked”的右子节点存储，具体取决于我们将它们插入到树中的顺序。

C# 实现以更好地理解：

using System;
using System.Collections.Generic;

namespace BSTString
{
    public class BinaryStringSearchTree
    {
        // Private class so that it cannot be accessed outside of parent class
        private class Node
    {
        // Data field of the node 
        public string _data;

        // Stores address of left child
        public Node _leftNode;

        // Stores address of right child
        public Node _rightNode;

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="data"></param>
        public Node(string data)
        {
            this._data = data;          // String is stored in the data field of the node
            this._rightNode = this._leftNode = null;    // Right and left child are set to null
        }
    }

    // Stores the root of the tree
    private Node root;

    /// <summary>
    /// Constructor 
    /// Root is set as null
    /// </summary>
    public BinaryStringSearchTree()
    {
        root = null;
    }

    /// <summary>
    /// Constructor 
    /// </summary>
    /// <param name="value"></param> // Value which is to be stored in root
    public BinaryStringSearchTree(string value)
    {
        // Creates a new node with value and stores into root
        root = new Node(value);
    }

    /// <summary>
    /// Function to call insertString() function
    /// </summary>
    /// <param name="data"></param>
    public void insert(string data)
    {
        // Inserting data into tree
        root = insertString(root, data);
    }

    /// <summary>
    /// Private recursive function which is called to insert data into the tree
    /// </summary>
    /// <param name="root"></param>
    /// <param name="data"></param>
    /// <returns></returns>
    private Node insertString(Node root, string data)
    {
        // Base Case: 
        // If the tree is empty
        if (root == null)
        {
            // Data is stored at root
            root = new Node(data);

            // root node is returned 
            return root;
        }

        /*
         * string.Compare(a, b) function will return 
         * 0 if a is equal to b
         * 1 if a is greater than b
         * -1 if a is smaller than b
         */

        // -- Recursively moving down the tree --
        // If data stored at root is greater then the data
        if (string.Compare(root._data, data) > 0)
        {
            root._leftNode = insertString(root._leftNode, data);
        }
        // If data stored at root is smaller then the data
        else if (string.Compare(root._data, data) < 0)
        {
            root._rightNode = insertString(root._rightNode, data);
        }

        return root;
    }

    /// <summary>
    /// Function to call deleteString() function
    /// </summary>
    /// <param name="data"></param>
    public void delete(string data)
    {
        root = deleteNode(root, data);
    }

    /// <summary>
    /// Private recursive function which is called to delete data from the tree
    /// </summary>
    /// <param name="root"></param>
    /// <param name="data"></param>
    /// <returns></returns>
    private Node deleteNode(Node root, string data)
    {
        // Base case: 
        // If the tree is empty
        if (root == null)
        {
            return root;
        }

        // -- Recursively moving down the tree --
        // If data stored at root is greater then the data
        if (string.Compare(root._data, data) > 0)
        {
            root._leftNode = deleteNode(root._leftNode, data);
        }
        // If data stored at root is smaller then the data
        else if (string.Compare(root._data, data) < 0)
        {
            root._rightNode = deleteNode(root._rightNode, data);
        }
        // If data stored at root is same as the data
        else
        {
            // Base case 
            // If the node does not have right or left child 
            if (root._leftNode == null && root._rightNode == null)
            {
                return null;
            }

            // Node with only one child
            if (root._rightNode == null)
            {
                return root._leftNode;
            }
            else if (root._leftNode == null)
            {
                return root._rightNode;
            }

            // Node which has two children 
            // Finds In-Order Sucessor - smallest in the right subtree
            Node inodrsuc = inOrderSucessor(root._rightNode);

            // Replacing the In-Order sucessor of root with data of root
            root._data = inodrsuc._data;

            // Delete the In-Order Sucessor 
            root._rightNode = deleteNode(root._rightNode, root._data);
        }

        return root;
    }


    /// <summary>
    /// Function to find smallest element in the left subtree
    /// </summary>
    /// <param name="root"></param>
    /// <returns></returns>
    private Node inOrderSucessor(Node inOrder)
    {
        // Loop runs till leaf node
        while (inOrder._leftNode != null)
        {
            inOrder = inOrder._leftNode;
        }

        return inOrder;
    }

    /// <summary>
    /// Function to call searchTree() function 
    /// </summary>
    /// <param name="data"></param> String which is to be searched
    /// <returns></returns>
    public string search(string data)
    {
        Node result = searchTree(root, data);

        // Data does not exist int the tree
        if (result == null)
        {
            return "Not Found";
        }

        return result._data;
    }

    /// <summary>
    /// Private recursive function to search for a particular node in a tree  
    /// </summary>
    /// <param name="root"></param> Root of the tree
    /// <param name="data"></param> String which is to be searched
    /// <returns></returns>
    private Node searchTree(Node root, string data)
    {
        // Base Case: root is null
        // or data stored at root is equal to string which is to be searched 
        if (root == null || string.Compare(root._data, data) == 0)
        {
            return root;
        }

        // -- Recursively moving down the tree --
        // Data stored at root is smaller than the string which is to be searched 
        if (string.Compare(root._data, data) < 0)
        {
            return searchTree(root._rightNode, data);
        }
        // Data stored at root is greater than the string which is to be searched 
        else
        {
            return searchTree(root._leftNode, data);
        }
    }

    /// <summary>
    /// Function to call private inOrder() function 
    /// </summary>
    public void inOrder()
    {
        inOrder(root);
    }

    /// <summary>
    /// -- In-Order traversal --
    /// Traverse left subtree recursively
    /// Visite root node
    /// traverse right subtree resursively
    /// </summary>
    /// <param name="root"></param>
    private void inOrder(Node root)
    {
        if (root != null)
        {
            inOrder(root._leftNode);
            Console.WriteLine(root._data);
            inOrder(root._rightNode);
        }
    }

    /// <summary>
    /// Function to call private preOrder() function 
    /// </summary>
    public void preOrder()
    {
        preOrder(root);
    }

    /// <summary>
    /// -- Pre-Order Traverse --
    /// Visit root node
    /// Traverse left subtree recursively
    /// Traverse right subtree resursively 
    /// </summary>
    /// <param name="root"></param>
    private void preOrder(Node root)
    {
        if (root != null)
        {
            Console.WriteLine(root._data);
            preOrder(root._leftNode);
            preOrder(root._rightNode);
        }
    }

    /// <summary>
    /// Function to call private postOrder() function 
    /// </summary>
    public void postOrder()
    {
        postOrder(root);
    }

    /// <summary>
    /// -- Post-Order Traversal -- 
    /// Traverse left subtree recursively
    /// Traverse right subtree recursively
    /// Visite root node
    /// </summary>
    /// <param name="root"></param>
    private void postOrder(Node root)
    {
        if (root != null)
        {
            postOrder(root._leftNode);
            postOrder(root._rightNode);
            Console.WriteLine(root._data);
        }
    }

    /// <summary>
    /// Printing level order traversal using iterative approach
    /// Referenced from: https://www.geeksforgeeks.org/print-level-order-traversal-line-line/
    /// </summary>
    public void printTree()
    {
        // Base Case 
        // Tree is empty
        if (root == null)
        {
            return;
        }

        // Empty queue for level
        Queue<Node> queue = new Queue<Node>();

        queue.Enqueue(root);

        while (true)
        {
            int nodeCount = queue.Count;    //number of nodes at current level
            if (nodeCount == 0)
            {
                break;
            }

            while (nodeCount > 0)
            {
                Node node = queue.Peek();
                Console.Write(node._data + " ");
                queue.Dequeue();
                if (node._leftNode != null)
                {
                    queue.Enqueue(node._leftNode);
                }
                if (node._rightNode != null)
                {
                    queue.Enqueue(node._rightNode);
                }
                nodeCount--;
            }
            Console.WriteLine();
        }
    }
}

class Test
{
    static void Main(string[] args)
    {
        // Creating an instance of BinaryStringSearchTree class
        BinaryStringSearchTree tree = new BinaryStringSearchTree();

        // Inserting element
        tree.insert("Karen");
        tree.insert("Bob");
        tree.insert("Tom");

        // Print tree
        Console.WriteLine("Printing tree");
        tree.printTree();
        Console.WriteLine();
    }
}

}

- Charanpreet Singh

0

对于任何节点：

左分支中的所有内容按字母顺序排序 < 当前节点。
右分支中的所有内容按字母顺序排序 > 当前节点。

这提供了一些独特的属性

您可以通过简单地向左或向右移动来查找任何节点，具体取决于您正在搜索的键是按字典顺序 < 还是 > 当前节点。您将到达目的地或非匹配叶节点（在这种情况下，该键不存在），并且在 O(Log n) 时间内完成。
按顺序遍历会按字母顺序给出所有键。

- mellamokb

0

在你的例子中，它们指的是每个名字中第一个符号的顺序。

如果你看一下，从左到右的名字顺序是从ABC的第一个字符到最后一个字符。

此外，KAREN名称的第二次出现有一个特殊情况 - 在这棵树中的默认行为是，如果输入相同的数据，则“向右移动”，然后将Karen与Tom进行比较 -> K“小于”T，因此它在其左侧。

无论如何，这里有一个更好的示例，您可以从中看到二叉树中的顺序数字： http://www.codeproject.com/Articles/4647/A-simple-binary-tree-implementation-with-VB-NET

- Stas Sl

-1

我认为下面这篇文章将对你理解二叉树的概念非常有帮助，它还提供了C/C++和Java中常见的代码示例：

http://cslibrary.stanford.edu/110/BinaryTrees.html

- dotminer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- thedan · Accepted Answer

在二叉搜索树中，每个节点最多有一个左子节点和一个右子节点。在给定节点的左侧的每个节点都比它小，在给定节点的右侧的每个节点都比它大。这意味着您不能有重复的值，因此我不确定示例是否完全符合书中的要求。

在您提供的示例中，字符串按字母顺序排序。以根节点为例，Bob在Karen之前，因此Bob放在Karen的左边。Tom在Karen之后，因此Tom放在Karen的右边。查看整个树，您会发现Karen左侧的每个节点（Bob，Alan，Ellen）在字母表中都排在Karen之前，而Karen右侧的每个节点（Tom，Wendy）在字母表中都排在Karen之后。无论查看哪个节点，这种模式都是相同的。