Insert/find 二叉树中的问题

Question

更新：只有当我对字符串使用二叉树时才会出现此问题。如果我用整数感觉它，一切正常！

几个月前，我用 C++ 编写了一个二叉树实现。一切似乎都正常（插入、删除、遍历、查找...）并且我通过了考试 :) 但是现在当我基于这个二叉树 class 编写一个新的 class 时，查找方法好像有bug，但是找不到原因

问题是：找到returns一个指向节点的指针，但由于某些原因，只有当这个节点是根节点时我才能访问它的成员变量。我不太明白为什么。与poiters有关吗？还是我的插入函数有问题？有人可以帮助我吗，因为我有点迷茫:)

这是我的二叉树界面：

template <class N>
class Node {
public:
  N data;
  Node* left;
  Node* right;
  Node* parent;
};

template <class B>
class BinaryTree {
protected:
  Node<B>* m_root;
  unsigned int m_height;  // longest path in tree
  unsigned int m_size;    // total number of nodes

  // methods that support public methods of below
  void __insert(Node<B>* element, B value);
  void __inorder(Node<B>* element);
  void __preorder(Node<B>* element);
  void __postorder(Node<B>* element);
  void __remove(Node<B>* element, B value);
  void __update_parent(Node<B> *element);
  void __destroy_tree(Node<B>* element);
  int __get_height(Node<B>* element);
  Node<B>* __find(Node<B>* element, B value);
  Node<B>* __find_minimal(Node<B> *element);

public:
  BinaryTree(); // Default constructor
  ~BinaryTree(); // Default deconstructor
  void insert(B value);
  void inorder();
  void preorder();
  void postorder();
  void remove(B value);
  int get_size();
  int get_height();
  bool is_empty();
  bool find(B value);
  bool check_find(B value);
};

插入：

template <class B>
void BinaryTree<B>::insert(B value) {      // Creates a new node in the tree with value
  if(m_root == NULL) {
    m_root = new Node<B>;   // creating the root if it's empty
    m_root->data = value;
    m_root->left = NULL;
    m_root->right = NULL;
    m_root->parent = NULL;
  }
  else {
    Node<B>* element = m_root;
    __insert(element, value);
  }
}

template <class B>
void BinaryTree<B>::__insert(Node<B>* element, B value) {
  if(value < element->data) {
    if(element->left != NULL)
      __insert(element->left, value);
    else {
      element = element->left;
      element = new Node<B>;
      element->data = value;
      element->left = NULL;
      element->right = NULL;
      element->parent = element;
      m_size++;
    }
  }
  else if(value >= element->data) {
    if(element->right != NULL)
      __insert(element->right, value);
    else {
        element = element->right;
        element = new Node<B>;
        element->data = value;
        element->left = NULL;
        element->right = NULL;
        element->parent = element;
        m_size++;
    }
  }
}

查找：

template <class B>
Node<B>* BinaryTree<B>::__find(Node<B>* element, B value) {
  if(element != NULL) {
    if(value == element->data)
      return element;
    else if(value < element->data)
      __find(element->left, value);
    else if(value > element->data)
      __find(element->right, value);
  }
  else
    return NULL;
}

最后，一个测试find的函数。即使值匹配，它 returns 只有当找到的节点是 m_root 时才为真。为什么？

template <class B>
bool BinaryTree<B>::check_find(B value) {
  Node<B>* node = __find(m_root, value);
  if(node != NULL && node->data == value)
    return true;
  return false;
}

为什么？

更多链接：我的二叉树实现的完整代码： https://github.com/vgratian/CS-121-Data-Structures/tree/master/graphs 我使用此二叉树的程序： https://github.com/vgratian/rate-ur-prof

Answer 1

在您的插入函数中，您实际上并没有将元素插入到树中。您创建一个新节点，并将其父节点设置为指向自身。另外，您没有更新指向新节点的父 left/right 指针。

看看添加的评论：

if(element->left != NULL)
  __insert(element->left, value);
else { // meaning element->left == NULL
  element = element->left; // element = NULL
  element = new Node<B>; // element = new node
  element->data = value;
  element->left = NULL;
  element->right = NULL;
  element->parent = element; // element->parent = new node.element parent point to himself

Answer 2

问题在于您的查找实现：

else if(value < element->data)
  __find(element->left, value);
else if(value > element->data)
  __find(element->right, value);

这仅适用于定义了关系运算符 < 和 > 的 types/classes（以相关方式）。因此，当 B 是 std::string 时它将不起作用。

对于字符串匹配，考虑使用 Trie。

Insert/find 二叉树中的问题

Insert/find issues in Binary Tree

c++

tree

binary-tree

binary-search-tree

data-structures