二叉树实现C++

我一直在尝试在C++中实现一个二叉搜索树以获得乐趣。我的问题是我遇到了插入功能问题。以下是我到目前为止：二叉树实现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){ 

     ?????? 

    } 

}

来源

2012-12-02 CoffeeIsProgramming

你到底有什么问题？ – h4ck3d

你想让任何组织到你的树吗？看起来你只是将元素放在任何地方，而不是使用数学逻辑为它找到一个位置。 – JustinDanielson

我想你想实现一个二进制搜索树。 – h4ck3d

您不应盲目插入，请按照以下逻辑进行操作。如果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(); 
}

来源

2012-12-02 09:19:43 JustinDanielson

只有当您需要二进制*搜索树时才需要。这不是要求。你可以盲目插入。 – axiom

OP问题的第一行是“我一直试图在C++中实现一个二叉搜索树来获得乐趣”。但他在代码中发布的逻辑与他相矛盾。 – JustinDanielson

如果你想在左右两边都不为空时插入，那么你可以通过递归地移动到树的最左边的节点来插入该项。而且，由于您只是以特定顺序插入值，因此很难跟踪。在这种情况下，实现一个二叉搜索树。

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

而最重要的是，插入一个BASE情况下退出递归。

来源

2012-12-02 09:12:30 h4ck3d

二叉树实现C++

回答

相关问题