c++ - 二叉树实现 C++

Question

为了好玩，我一直在尝试用 C++ 实现二叉搜索树。我的问题是我的插入功能有问题。以下是我到目前为止的内容：

class TreeNode{

public: 
    int data;          
    TreeNode *left;    
    TreeNode *right;  
    void Insert(int value, TreeNode *x);
    void TreeNode::Print(TreeNode *x);
    TreeNode();
};


TreeNode::TreeNode(){

left = NULL;
right = NULL;

}

.

void TreeNode::Insert(int value, TreeNode *x){

    if(x->left == NULL && x->right == NULL){
           TreeNode *tree = new TreeNode();                        
           tree->datavalue;                               
           x->left = tree;                                  
    }

    else if(x->left == NULL && x->right != NULL){

           TreeNode *tree = new TreeNode();                
           tree->data = value;                          
           x->left = tree;                                 
    }

    else if(x->left != NULL && x->right == NULL){

           TreeNode *tree = new TreeNode();                      
           tree->data = value;                            
           x->right = tree;                          
    }

    else if(x->left != NULL && x->right != NULL){

        ??????

    }

}

Answer 1

请勿盲目插入，请遵循以下逻辑。如果 x.value 小于根值，则尝试向左插入。如果 x.value >= root.value，则向右走。重复此逻辑，直到您遇到 NULL 值。那将是插入元素的正确位置。

你可以翻转逻辑，我只是​​在 < 上选择了左，因为不到有点向左箭头。<-：P

TreeNode *root = this;
TreeNode *parent = root;
//Traverse the tree, go left if x.val < , else go right(>=)
while(root) {
    parent = root;
    root = (root->value > x.value) ? root->left : root->right;
}
if(parent->value > x->value) 
    parent->left = x;
else
    parent->right = x;

如果您不关心排序，请使用队列进行深度优先搜索。

queue<TreeNode*> nodes;
nodes.push(this);
while(1)
{
    if(!nodes.front()->left)
    {
        nodes.front()->left = x;
        return;
    } 
    else if (!nodes.front()->right)
    {
        nodes.front()->right = x;
        return;
    }
    nodes.push(nodes.front()->left);
    nodes.push(nodes.front()->right);
    nodes.pop();
}

Answer 2

如果要在左右孩子都不是 null 时插入，则可以通过递归移动到树的最左侧节点来插入项目。而且由于您只是以没有特定顺序的方式插入值，因此很难跟踪。而是在这种情况下实现二叉搜索树。

else if(x->left != NULL && x->right != NULL){
         Insert(value,x->left);
         x-> data  = value;
         x->left = x->right = NULL;
}

最重要的是，插入一个 BASE 案例以退出递归。