C-树插入到特定位置

Question

我想写一个函数，将一个节点添加到一个树中，该树以根、节点的值、我想添加新节点的节点的值和一个数字作为参数，根据该数字我将节点添加为左或右子节点（偶数=右子节点，奇数=左子节点）。我不明白我错在哪里，这与BST的概念相同，只是其他条件。如果有任何帮助，我将不胜感激。

例如：

                             6
                            / \
                          3    20

Tnode*insert（Tnode*root，int data，int father，int leftOrRight）；插入（根，50，6，2）树将：

                           6
                          / \
                         3   50
                              \
                               20

Tnode* insert(Tnode* root, int data , int father , int leftOrRight)
{
    /* If the tree is empty, return a new node */
    if (root == NULL)
        return newNode(data);
    if (root->data == father)
            if (leftOrRight % 2 == 0)
                root->right = insert(root->right , data , father , leftOrRight);
            else
                root->left = insert(root->left , data , father , leftOrRight) ;
    return root ;
}

 Tnode* newNode(int data)
{
    Tnode* node = (Tnode*)malloc(sizeof(Tnode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

Answer 1

首先，您编写的代码只检查树的根是父亲。我假设您正在尝试检查整棵树。因此，您需要递归调用其左右子级的插入函数来搜索整棵树的父亲。

Tnode* insert(Tnode* root, int data , int father , int leftOrRight)
{
    /* If the tree is empty, return a new node */
    if (root == NULL)
        return newNode(data);
    if (root->data == father)
            if (leftOrRight % 2 == 0)
                root->right = insert(root->right , data , father , leftOrRight);
            else
                root->left = insert(root->left , data , father , leftOrRight) ;
    insert(root->left , data , father , leftOrRight);
    insert(root->right, data , father , leftOrRight); 
    return root; 
}

 Tnode* newNode(int data)
{
    Tnode* node = (Tnode*)malloc(sizeof(Tnode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

Answer 2

如果已经找到了应该输入数据的节点，则不需要递归。

Tnode* insert(Tnode* root, int data , int father , int leftOrRight)
{
    /* If the tree is empty, return a new node */
    if (root == NULL)
        return newNode(data);
    if (root->data == father)
    {
        Tnode * node = newNode(data);
        if (leftOrRight % 2 == 0)
        {
           node -> left = root -> right; // can be node -> right as well
           root -> right = node;
        }
        else
        {
           node -> left = root -> left; // can be node -> right as well
           root -> left = node;
        }
    }
    else
    {
       // if the current node is not the required node check the leaves
       insert(root->left , data , father , leftOrRight);
       insert(root->right, data , father , leftOrRight);
    }
    return root; 
}