二叉搜索樹節點插入不正常

Question

我有一個家庭作業分配來實現二叉搜索樹（創建，刪除，搜索）。我使用了老師提供的例子，但我無法使其工作。

這裏是到目前爲止我的代碼：

void insert_node(int k){ 
    struct node *nodnou,*flow,*parent; 

    nodnou = (struct node*)malloc(sizeof(node)); 
    nodnou->st = NULL; 
    nodnou->dr = NULL; 
    nodnou->nr = k; 

    if (root==NULL) 
    { 
     root = (struct node*)malloc(sizeof(node)); 

     root = nodnou; 
    } 
    else 
    { 
     flow = (struct node*)malloc(sizeof(node)); 
     parent = (struct node*)malloc(sizeof(node)); 
     flow = root; 
     parent = root; 
     while (((flow->st!=NULL) || (flow->dr!=NULL)) && flow!=NULL) 
     { 
      if (k<flow->nr) 
      { 
       parent = flow; 
       flow = flow->st; 
      } 
      else 
      { 
       parent = flow; 
       flow = flow->dr; 
      } 
     } 

     if (k<flow->nr) 
     { 
      parent->st = nodnou; 
     } 
     else 
     { 
      parent->dr = nodnou; 
     } 
    } 
} 

思維方式：該函數獲得我們要插入的參數k的節點的值。該函數只會插入樹的根（根是全局變量）。

我認爲我最大的問題是while循環掃過樹找到新節點的位置。

如果我使用while (flow!=NULL)它將無法工作，因爲流指針會獲得一個不存在的內容。請幫助我瞭解我的錯誤（家庭作業）。

Answer 1

我認爲你應該使用while（flow！= NULL），然後在你的元素之後插入流。現在它的方式會在不應該的情況下停止，並且在停止時做出奇怪的事情。嘗試用筆和紙做一些例子。

Answer 2

你差不多了。趕上！

首先您需要了解更好的內存分配。實際上，您只需要在您的功能中調用第一個malloc()。這是您在每次調用insert_node()期間爲您附加到樹上的節點分配的內存。所有其餘的malloc你正在執行是不需要的。看起來，你直觀地感覺到需要爲正在使用的其他指針分配內存，但它們都是臨時的，不需要任何分配，只是在嘗試去引用它們之前分配給有效節點。事實上，那些unnecesary分配將創建所謂的內存泄漏（內存，你要求而無法釋放），在這樣的代碼：

root = (struct node*)malloc(sizeof(node)); 
root = nodnou; 

第二assignmet（root = nodnou）會覆蓋前malloc()調用的結果並且由於您沒有將覆蓋的指針值保存在任何其他位置，您將不能再釋放該內存，它將被標記爲用於應用程序的整個生命週期！

接下來，您可以簡化漫遊樹中查找插入點的代碼。 您似乎擔心流量變爲NULL，但這並不重要。重要的節點是父母。 while循環結束後，它將指向插入節點需要鏈接的實際節點。這是您的代碼的修改版本。

void insert_node(int k) { 
    struct node *nodnou, *flow, *parent; 
    // this is the only memory allocation that should be done 
    nodnou = (struct node*)malloc(sizeof(node)); 
    nodnou->st = NULL; 
    nodnou->dr = NULL; 
    nodnou->nr = k; 

    parent = NULL; 

    if(root == NULL) { 
     root = nodnou; 
    } else { 

     flow = root; 
     // We will walk the tree in order until we reach the bottom of the 
     // tree (flow becomes null). What we are trying to do is to find out 
     // the node that will become the parent of the new node we are inserting 
     // It doesn't matter if flow becomes NULL, the important value after the 
     // while loop ends is parent 
     while(flow != NULL) { 
     // update the current potential parent node 
     parent = flow; 
     if(k < flow->nr) { 
      // the number we are inserting is lower than the flow node, walk to the left 
      flow = flow->st; 
     } else { 
      // the number we are inserting is greater or equal than the flow node, 
      // walk to the right 
      flow = flow->dr; 
     } 
     } 

     // We have reached the bottom, now compare number again with the node that 
     // will become parent, to find out if we need to link this node to the left 
     // or to the right of the parent node 

     if(k < parent->nr) { 
     parent->st = nodnou; 
     } else { 
     parent->dr = nodnou; 
     } 
    } 

} 

就是這樣。嘗試編碼其餘的樹操作，並毫不猶豫地詢問你是否感到困惑。 =）

Answer 3

你的代碼中有幾個重要的缺陷，而不是其中最重要的是在C. 分配是如何工作的動態內存不要跟隨這樣一個模式的誤區：

Type *pointer = malloc(sizeof(Type)); 
pointer = <<something else>> 

它的字面泄漏內存並在兩條短線中獲得沒有任何。這不是像Java或C＃這樣的基於對象引用的語言。指針是保存內存地址的變量。就像一個int可以容納一個整數，一個指針保存一個地址。就如同下面的例子：

int n = 6; 
n = 5;  //Hmm. Where did the 6 go? Oh yeah, We overwrote it with 5. 

，您將會失去分配環節做同樣的事情與指針：

struct node *root = malloc(sizeof(*root)); 
root = nodnou; // memory allocated above is gone. forever leaked. 

---

指針是變量。就像任何其他變量一樣，它們持有價值。但是，在指針的情況下，其值是地址。你可以擁有幾乎所有C語言的指針，包括指向指針的指針;包含指針變量地址的變量。我將它們提出來，因爲它們爲您的插入要求提供了一個特別優雅的解決方案。

以下是在樹中不支持重複的二叉樹插入的一般實現（如果允許重複，則代碼會變得更短）。此外，它使用超出所提供的函數參數的局部變量，並且我挑戰你剖析它並確定它是如何工作的。它甚至在最初NULL樹根指針，無需特殊外殼if (root) {} else {}邏輯：

void insert_node(struct node **pp, int k) 
{ 
    while (*pp) 
    { 
     if (k < (*pp)->nr)  // move down left side? 
      pp = &(*pp)->st; 

     else if ((*pp)->nr < k) // move down right side? 
      pp = &(*pp)->dr; 

     else return;    // found the key, no dupes. leave 
    } 

    // pp contains the address of the pointer we need to set. 
    *pp = malloc(sizeof(**pp)); 
    (*pp)->st = (*pp)->dr = NULL; 
    (*pp)->nr = k; 
} 

如果你的樹應該支持你需要了解他們是插在哪個方面是一致的重複，但它縮短了上面的算法相當：

void insert_node(struct node **pp, int k) 
{ 
    while (*pp) 
     pp = (k < (*pp)->nr) ? &(*pp)->st : &(*pp)->dr; 

    // pp contains the address of the pointer we need to set. 
    *pp = malloc(sizeof(**pp)); 
    (*pp)->st = (*pp)->dr = NULL; 
    (*pp)->nr = k; 
} 

在任一種情況下，調用該主叫側這樣的：

struct node *root = NULL; 

insert(&root, 5); 
insert(&root, 10); 
insert(&root, 7); 
...etc...