使用 C++ 创建特殊的二叉搜索树

Question

我想创建一个具有特殊节点的二叉搜索树。应该有三个类的Nodes，Internal Node，External Node和Root node，每一个都继承一个共同的parent Node，每一种节点都会有一些独特的功能。是否可以创建这样的 BST。我面临的问题是假设我插入树中的第一个节点成为根节点。我插入的下一个节点将成为外部节点。现在，如果我插入另一个节点，则外部节点必须成为内部节点，新节点将成为外部节点。此外，由于节点的类型不同，我无法找到一种方法从一个节点导航到另一个节点。可以创建这种类型的树。如果是，请给我一些如何做到这一点的建议。

Answer 1

如果我理解正确，您担心一个 class - 外部 - 中的对象如何成为另一个 class - 内部的对象。这一点，当 C++ 是静态类型语言时：类型（包括对象的 classes）在编译时确定。对吗？

好吧，您至少可以通过以下两种方式之一实现：

当外部节点变为内部节点时，删除外部节点并将其替换为正确初始化的内部节点（例如指向新的外部节点）。
放弃 External 和 Internal 是离散类型，只检查子节点和父节点以动态确定节点类型。

关于这些问题的更多相关阅读 material：

this 维基百科页面中的（编程语言）类型系统。
这个问题：What is duck typing?
Circle-vs-Eclipse problem，特别是希望将圆拉伸成椭圆。

Answer 2

您可以使用基本继承某些类型枚举和递归调用。这可能是一个起点：

enum NodeType
{
    eRoot,
    eInternal,
    eExternal
};

class BinaryNode
{
public:
   virtual NodeType GetType() = 0;
   virtual void UpdateTree() = 0;

protected:
   BinaryNode* ChildLeft;
   BinaryNode* ChildRight;
   BinaryNode* Parent;
};

class ExternalNode : public BinaryNode 
{
   NodeType GetType() override { return eExternal; }
   void UpdateTree() override 
   { 
      //... Replace node instances here(e.g. delete this node and construct the correct new one given this sub tree. call new InternalNode(this) for example) 
      // Call this towards the parent node so the tree will be transformed accordingly
   }
}
class InternalNode : public BinaryNode 
{ 
   NodeType GetType() override { return eInternal; }
   void UpdateTree() override { //... }
}
class RootNode : public BinaryNode 
{ 
   NodeType GetType() override { return eRoot; }
   void UpdateTree() override { //... }
}

这只是为了让您了解从哪里开始。您可以在运行时通过 GetType() 检查节点类型，并据此进行一些检查。

请注意，这种转变并不是特别快。如果你想让它更快，不要使用不同的类型和虚函数调用和指针。

将您的二叉树放在数组中并使用二进制索引，因此在给定索引处 "n" 使用 2*n+1 获取左子节点，使用 2*n+2 获取右子节点。然后使用一些标志（根、外部、内部等）来确定要在二进制节点上调用哪些函数。我不会像在我的代码示例中那样使用继承来提高速度或提高可读性。事实上，从外部决定在节点上调用什么函数可以更具可读性并且更不容易出错。

使用 C++ 创建特殊的二叉搜索树

Create special binary search tree using C++

c++

duck-typing

static-typing