將節點添加到二叉搜索樹隨機刪除節點

Question

堆棧。我有一個TYPE類型的二叉樹（TYPE是一個數據*的typedef），可以添加和刪除元素。但由於某些原因，添加的某些值會覆蓋以前的元素。這裏是我的代碼，它的插入示例不覆蓋元素，也不覆蓋元素。

數據我存儲：

struct data { 
int number; 
char *name; 
}; 

typedef struct data data; 

# ifndef TYPE 
# define TYPE  data* 
# define TYPE_SIZE sizeof(data*) 
# endif 

樹結構：

struct Node { 
TYPE   val; 
struct Node *left; 
struct Node *rght; 
}; 

struct BSTree { 
struct Node *root; 
int   cnt; 
}; 

的數據比較。

int compare(TYPE left, TYPE right) { 
    int left_len; int right_len; int shortest_string; 

    /* find longest string */ 
    left_len = strlen(left->name); 
    right_len = strlen(right->name); 
    if(right_len < left_len) { shortest_string = right_len; } else { shortest_string = left_len; } 

    /* compare strings */ 
    if(strncmp(left->name, right->name, shortest_string) > 1) { 
     return 1; 
    } 
    else if(strncmp(left->name, right->name, shortest_string) < 1) { 
     return -1; 
    } 
    else { 
     /* strings are equal */ 

     if(left->number > right->number) { 
      return 1; 
     } 
     else if(left->number < right->number) { 
      return -1; 
     } 
     else { 
      return 0; 
     } 
    } 
} 

而add方法

struct Node* _addNode(struct Node* cur, TYPE val) { 
    if(cur == NULL) { 
     /* no root has been made */ 
     cur = _createNode(val); 

     return cur; 
    } 
    else { 
     int cmp; 

     cmp = compare(cur->val, val); 
     if(cmp == -1) { 
      /* go left */ 

      if(cur->left == NULL) { 
       printf("adding on left node val %d\n", cur->val->number); 
       cur->left = _createNode(val); 
      } 
      else { 
       return _addNode(cur->left, val); 
      } 
     } 
     else if(cmp >= 0) { 
      /* go right */ 

      if(cur->rght == NULL) { 
       printf("adding on right node val %d\n", cur->val->number); 
       cur->rght = _createNode(val); 
      } 
      else { 
       return _addNode(cur->rght, val); 
      } 
     } 

     return cur; 
    } 
} 

void addBSTree(struct BSTree *tree, TYPE val) 
{ 
tree->root = _addNode(tree->root, val); 
tree->cnt++; 
} 

創建一個新的節點的方法：

struct Node* _createNode(TYPE val) { 
struct Node* new_node; 
new_node = (struct Node*)malloc(sizeof(struct Node*)); 
new_node->val = val; 
new_node->left = NULL; 
new_node->rght = NULL; 

return new_node; 
} 

功能打印樹：

void printTree(struct Node *cur) { 
    if (cur == 0) { 
     printf("\n"); 
    } 
    else { 
     printf("("); 
     printTree(cur->left); 
     printf(" %s, %d ", cur->val->name, cur->val->number); 
     printTree(cur->rght); 
     printf(")\n"); 
    } 
} 

下面是一個例子的一些數據將被覆蓋以前的元素：

struct BSTree myTree; 
struct data myData1, myData2, myData3; 

myData1.number = 5; 
myData1.name = "rooty"; 
myData2.number = 1; 
myData2.name = "lefty"; 
myData3.number = 10; 
myData3.name = "righty"; 

initBSTree(&myTree); 
addBSTree(&myTree, &myData1); 
addBSTree(&myTree, &myData2); 
addBSTree(&myTree, &myData3); 
    printTree(myTree.root); 

，它將打印：

((
righty, 10 
) 
lefty, 1 
) 

最後這裏的一些測試數據將在確切的同一地點之前的數據去，但這次沒有數據覆蓋：

struct BSTree myTree; 
struct data myData1, myData2, myData3; 

myData1.number = 5; 
myData1.name = "i"; 
myData2.number = 5; 
myData2.name = "h"; 
myData3.number = 5; 
myData3.name = "j"; 

initBSTree(&myTree); 
addBSTree(&myTree, &myData1); 
addBSTree(&myTree, &myData2); 
addBSTree(&myTree, &myData3); 
printTree(myTree.root); 

它打印：

((
j, 5 
) 
i, 5 (
h, 5 
) 
) 

有誰知道什麼可能會出錯？對不起，如果這篇文章很長。

Answer 1

它看起來像你的_addNode過程中有錯誤。它看起來像你沒有正確地在樹中存儲新的節點引用。

struct Node* _addNode(struct Node* cur, TYPE val) { 
if(cur == NULL) { 
    /* no root has been made */ 
    cur = _createNode(val); 
    return cur; 
} 
else { 
    int cmp; 

    cmp = compare(cur->val, val); 
    if(cmp == -1) { 
     /* go left */ 
     cur->left = _addNode(cur->left, val); 
    } 
    else if(cmp >= 0) { 
     /* go right */ 
     cur->left = _addNode(cur->right, val); 
    } 

    return cur; 
} 

_addnode函數有點令人困惑，因爲您使用的返回值不一致。我相信這個版本應該避免丟失任何節點。

Answer 2

我沒有看到明顯的缺陷。我會建議修改樹來保存int或比當前數據更簡單的東西。如果樹工作正常，那麼至少你知道在哪裏尋找，而不用擔心通用樹代碼。

我懷疑_createNode（），你可以添加代碼嗎？