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

问题描述 投票:-2回答:2

我想创建一个具有特殊节点的二叉搜索树。应该有三类节点,内部节点,外部节点和根节点,每一个都继承一个公共的父节点,并且每种类型的节点都有一些独特的功能。是否有可能创建这样的BST。我面临的问题是假设我插入树中的第一个节点成为根节点。我插入的下一个节点将成为“外部节点”。现在,如果我插入另一个节点,则外部节点必须成为内部节点,而新节点将成为外部节点。我也找不到一种在树上从一个节点导航到另一个节点的方法,因为节点的类型不同。是否可以创建这种类型的树。如果是的话,请给我一些建议。

c++ static-typing duck-typing
2个回答
1
投票

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

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获取右孩子。然后使用一些标志(根,外部,内部等)确定要在二进制节点上调用的函数。我不会像我的代码示例中那样使用继承来提高速度或提高可读性。实际上,从外部确定要在节点上调用的函数可能更具可读性,并且不易出错。


2
投票

[如果我理解正确,您担心一类的对象-外部-如何成为另一类的对象-内部。当C ++是静态类型的语言时,这是这样的:类型(包括对象的类)在编译时确定。对吧?

嗯,您可以通过以下两种方法中的至少一种来实现:

  1. [当外部节点变为内部节点时,请删除该外部节点,然后将其替换为经过正确初始化的内部节点(例如,指向新的外部节点)。
  2. 放弃外部和内部为离散类型,只检查子代和父代以动态确定节点类型。

一些有关这些问题的相关阅读材料:

© www.soinside.com 2019 - 2024. All rights reserved.