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

Question

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

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

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

摘自“算法导论”，第 3 版，第 286,287 页:“除了键和卫星数据外，每个节点还包含属性 left、right 和 p，它们指向与其左 child 、右 child 相对应的节点, 和它的父级。”

意思是这样的:

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

另一方面，我发现了几个不遵循这种设计的链接，例如:

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

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

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

这些实现不保留到父级的链接，并且从一些在线讲座中说树不向后遍历(也就是看不到父级)，这与书中的概念相反!

例如，在 RedBlack 树中，您需要查看该节点的祖 parent 和叔叔以确定是否重新着色和/或旋转以重新平衡树。在 AVL 树中你不需要，因为重点是子树的高度。四叉树和八叉树是一样的，你不需要 parent 。

问题:

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

还有向后遍历的规则是什么？我知道预序、中序、后序、广度优先、深度优先(预序)和其他用于遍历的 AI 启发式算法。

你不能在树中向后移动，即从 child 到 parent ，这是真的吗？如果是这样，那为什么这本书建议链接到父节点？

Answer 1

基本的二叉树(基础)需要子指针:

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

可以对基础进行许多修改，以帮助促进搜索或存储。

这些可以包括(但不限于):

• 父指针
• 子指针数组
• “颜色”指标
• 专门的叶节点——没有子链接

便利性取决于数据结构的使用。例如，一个子节点数组可能有助于加速 I/O 访问，其中读取“页面”节点与读取单个节点一样高效(参见 B-Tree)。 “颜色”指标可能有助于平衡的决定。专门的“叶”节点减少了树占用的内存量。

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

一些书籍或网站可能会挑剔传统或基本的“二叉树”数据结构。我发现限制妨碍了一切。