任何 BST 树中节点的正确结构是什么

Question

根据理论为二叉树创建节点的正确方法是什么？例如：

struct Node
{
    int data;
    Node *left;
    Node *right;
};

我目前面临的问题是我从多个来源（书籍、网站、在线讲座等）得到了 2 个不同的答案。

来自 "Introduction to Algorithms"，第 3 版，第 286,287 页："In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child,its right child, and its parent, respectively."

意思是这样的：

struct Node
{
   int data;
   Node *parent;
   Node *left;
   Node *right;
};

另一方面，我发现有几个 link 不遵循这种设计，例如：

http://algs4.cs.princeton.edu/32bst/

http://math.hws.edu/eck/cs225/s03/binary_trees/

http://www.cprogramming.com/tutorial/lesson18.html

这些实现不会将 link 保留到 parent 并且从一些在线讲座中可以看出树不会向后遍历（也就是看不到 parent ) 这与书中的概念相反！

例如，在 RedBlack 树中，您需要查看该节点的祖父 parent 和叔叔，以确定是否 re-colour and/or 旋转以重新平衡树。在 AVL 树中你不需要，因为焦点在 sub-trees 的高度上。四叉树和八叉树是一样的，你不需要 parent.

问题：

有人可以回答我这个问题并提供有效来源解释为二叉树或任何树（B-Trees，..等）设计节点的正确方法是什么？

还有向后遍历的规则是什么？我知道 Pre-order、In-order、Post-order、Breadth-First、Depth-First(Pre-order) 和其他用于遍历的 AI 启发式算法。

是否不允许您在树中向后移动，即从 child 到 parent？如果是这样，那为什么这本书建议 link 到 parent 节点？

Answer 1

没有硬性规定必须 link 返回到树数据结构中的父级。将 link 返回给父级类似于双重 linked 列表。没有 link 回到父级只是一个 linked 列表。使用 back link，显然你获得了更多的灵活性，但代价是（相对）更复杂的实现。许多问题可以用 linked 列表解决，而其他一些问题需要双重 linked 列表。

Answer 2

没有任何规范的定义。

一般来说，命令式语言（例如 C++）倾向于使用父级方法。它简化了高效再平衡的实现，并且正如 Thomas Matthews 指出的那样，促进了常量-space 迭代器。

函数式语言（例如 Haskell）倾向于使用无父方法（参见 Purely Functional Data Structures）。由于不可能进行任何修改，所有重新平衡都是通过沿搜索路径重新复制来完成的，因此不需要后向指针。由于是强递归导向的，常量 space 迭代器的设计也不是什么大问题。

Answer 3

基本的二叉树（基础）需要child个指针：

struct binary_tree_node
{
  binary_tree_node * left_child;
  binary_tree_node * right_child;
};

可以对有助于搜索或存储的基础进行许多修改。

这些可以包括（但不限于）：

parent指针
child 个指针数组
"color"指标
专门的叶节点 -- 无 child 链接

便利性取决于数据结构的使用。例如，child 个节点的数组可能有助于加快 I/O 访问速度，其中读取 "page" 个节点与读取单个节点一样高效（参见 B-Tree）。 "color" 指标可能有助于平衡的决定。专门的 "leaf" 节点减少了树占用的内存量。

至于遍历，任何方法都可以遍历一棵树。没有规则阻止从 child 到 parent 的遍历。一些遍历可能包括兄弟姐妹到兄弟姐妹。

一些书籍或网站可能会挑剔传统或基本的 "binary tree" 数据结构。我发现限制妨碍了。

Answer 4

struct tree_node
{
  tree_node* left_child;
  tree_node* right_child;
  int data;  // here you can use whatever type or data you want. Even generic type
};

Answer 5

这取决于你的任务

说实话binary search tree是一个概念，没有严格或标准的数据结构设计规则。但是要了解基本功能（例如插入、删除、查找等），人们会使用非常基本的数据结构，例如

struct Node
{
    int data;
    Node *left;
    Node *right;
};

但是您的任务可能会针对不同的目的进行不同的设计。例如，如果您需要在单个操作中找到它的 parent node，您可能会考虑将节点结构设计为

struct Node
{
    int data;
    Node *parent;
    Node *left;
    Node *right;
};

其他一些复杂的实现可能也需要存储同级列表。就像，

 struct Node
 {
     int data;
     Node *parent;
     Node *left;
     Node *right;
     list<Node> *siblings;
 };

所以，没有严格的标准

Answer 6

以下节点定义（在 Java 中）是针对平衡二叉树而不是 BST。

// Copyright (C) NNcNannara 2017

public class Node
{
    public Node Left;
    public Node Right;
    public Node Parent;
    public State Balance;

    public Node()
    {
        Left = this;
        Right = this;
        Parent = null;
        Balance = State.Header;
    }

    public Node(Node p)
    {
        Left = null;
        Right = null;
        Parent = p;
        Balance = State.Balanced;
    }

    public Boolean isHeader ()
    { return Balance == State.Header;  }
}

这针对平衡例程进行了优化。一个set节点派生Node的思路如下

// Copyright (C) NNcNannara 2017

public class SetNode<T> extends Node
{
    public T Data;

    public SetNode(T dataType, Node Parent)
    {
        super(Parent);
        Data = dataType;
    }
}

一个字典节点如下

// Copyright (C) NNcNannara 2017

public class DictionaryNode<K, T> extends Node
{
    public T Data;
    public K Key;

    public DictionaryNode(K keyType, T dataType, Node Parent)
    {
        super(Parent);
        Key = keyType;
        Data = dataType;
    }
}

平衡和迭代本质上是非通用的，并且是为基础 class 节点定义的。当然磁盘上也可能存在二叉树，其节点类型如下

package persistent;

public class Node
{
    public long Left;
    public long Right;
    public long Parent;
    public long Key;
    public calculus.State Balance;

    public Node()
    {
        Left = 0;
        Right = 0;
        Parent = 0;
        Balance = calculus.State.Header;
        Key = 0;
    }

    public Node(long p)
    {
        Left = 0;
        Right = 0;
        Parent = p;
        Balance = calculus.State.Balanced;
        Key = 0;
    }

    public Boolean IsHeader ()  { return Balance == calculus.State.Header; }
}

不是存在引用，而是存在节点和数据文件中的长整数偏移量。请注意，磁盘上的所有集合只有一种节点类型。

任何 BST 树中节点的正确结构是什么

What is the correct structure for a node in any BST Tree

c++

algorithm

binary-search-tree

这取决于你的任务

所以，没有严格的标准