带有根子节点的 C++ 二叉搜索树错误

Question

我正在尝试用单词构建一个二叉搜索树。但是，当我使用上面的代码时，我只能到达我的根，根的左右 child 似乎都是空的。

代码:

void NgramTree::insert(std::string str)
{
    if(root==NULL)
    {
        root=new node(str,1);
    }
    else{
        // checkAndIncrease method checks if its already in tree and counts, this method works perfect too. I ve been sure , its going in if block below after first insertion.
        bool have=checkAndIncease(root,str);

    if(have==false)
    {
        node* cur=root;
        while(cur!=NULL)
        {

           // first method returns 1 if  first arg is smaller,0 if equal 1 if bigger  and works perfectly!
           int upper=first(cur->data,str,0);

           if(upper==1)
           {
               cur=cur->right;

           }
           if(upper==0)
           {
               std::cout<< " hata var";
           }
           if(upper==-1)
           {
               cur=cur->left;
                std::cout<< "cur=cur->left;\n";

           }
        }

        ///  WHEN I RUN PROGRAM, I CAN BE SURE  CUR== ROOT->LEFT
        if(cur==(root->left))
        {
            std::cout<< "cur==root->left DOGRUU\n";
        }
        // Although, cur==root->left,  if i use cur here
        // They arent connected, both childerens of root seems NULL
        // If i do root->left=new Node(str,1) instead of cur just for try
        // It works only for  one insertion.. 
        cur=new node(str,1);

    }

}

}

Answer 1

这是自定义二叉树代码示例。

// TreeNode.h

#include <stdlib.h>
#include <string>

#ifndef __TREE_NODE_H__
#define __TREE_NODE_H__

class CTreeNode
{
public:
    CTreeNode(std::string str);
    ~CTreeNode();
    ////////////////////////////////////////////////////////////
    const CTreeNode* GetLeft() const;
    const CTreeNode* GetRight() const;
    std::string         GetString() const;
    void       SetValue(std::string str);
private:
    CTreeNode* m_pLeft;
    CTreeNode* m_pRight;
    std::string m_Str;
};

#endif

CTreeNode 实现

#include "TreeNode.h"

CTreeNode::CTreeNode(int iValue, std::string str)
{
    m_pLeft = NULL;
    m_pRight = NULL;

    m_Str = str;
}

CTreeNode::~CTreeNode()
{
    delete m_pLeft;
    m_pLeft = NULL;

    delete m_pRight;
    m_pRight = NULL;
}

const CTreeNode* CTreeNode::GetLeft() const
{
    return m_pLeft;
}

const CTreeNode* CTreeNode::GetRight() const
{
    return m_pRight;
}


std::string CTreeNode::GetString() const
{
    return m_Str;
}

void CTreeNode::SetValue(std::string str)
{
    if (str.compare(m_Str) < 0)
    {
        if (m_pLeft != NULL)
            m_pLeft->SetValue(str);
        else
            m_pLeft = new CTreeNode(str);
    }
    else
    {
        if (m_pRight != NULL)
            m_pRight->SetValue(str);
        else
            m_pRight = new CTreeNode(str);
    }
}

CBinaryTree 声明

// BinaryTree.h

#include "TreeNode.h"
#include <iostream>


#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

class CBinaryTree
{
public:
    CBinaryTree();
    ~CBinaryTree();
    ////////////////////////////////////////////////////////////
    void Add(std::string str);
    void PrintLR() const;
private:
    void PrintLR(const CTreeNode* pNode) const;
    CTreeNode* m_pRoot;
};

#endif /* __BINARY_TREE_H__ */

CBinaryTree 实现

#include "BinaryTree.h"

using std::endl;
using std::cout;

CBinaryTree::CBinaryTree()
{
    m_pRoot = NULL;
}

CBinaryTree::~CBinaryTree()
{
    delete m_pRoot;
    m_pRoot = NULL;
}

void CBinaryTree::Add(std::string str)
{
    if (m_pRoot != NULL)
        m_pRoot->SetValue(str);
    else
        m_pRoot = new CTreeNode(str);
}

void CBinaryTree::PrintLR() const
{
    PrintLR(m_pRoot);
}

void CBinaryTree::PrintLR(const CTreeNode* pNode) const
{
    if (pNode == NULL)
        return;

    PrintLR(pNode->GetLeft());

    cout << pNode->GetString() << endl;

    PrintLR(pNode->GetRight());
}

你的情况

void NgramTree::insert(std::string str)
{
    if(root==NULL)
    {
        root=new node(str,1);
    }
    else{
        // checkAndIncrease method checks if its already in tree and counts, this method works perfect too. I ve been sure , its going in if block below after first insertion.
        bool have=checkAndIncease(root,str);

    if(have==false)
    {
        node* cur=root;
        while(cur!=NULL)
        {

           // first method returns 1 if  first arg is smaller,0 if equal 1 if bigger  and works perfectly!
           int upper=first(cur->data,str,0);

           if(upper==1)
           {
               if (cur->right == NULL)
               {
                   cur->right = new node(str, 1)
                   break;
               }
               cur=cur->right;
           }
           else if(upper==0)
           {
               std::cout<< " hata var";
           }
           else
           {
               if (cur->left == NULL)
               {
                   cur->left = new node(str, 1)
                   break;
               }
               cur=cur->left;
           }
        }
    }
}