[問題] 二元搜尋樹插入節點的迴圈改遞迴

[cat99961 (阿湯)]

我要將二元搜尋樹的迴圈改成遞迴(改原程式的insert_node函數)
原程式如下:
#include <stdlib.h>

struct tree                       /* 樹的結構宣告       */
{
   int data;                      /* 節點資料           */
   struct tree *left;             /* 指向左子樹的指標   */
   struct tree *right;            /* 指向右子樹的指標   */
};
typedef struct tree treenode;     /* 樹的結構新型態     */
typedef treenode *btree;          /* 宣告樹節點指標型態 */

/* ---------------------------------------- */
/*  插入二元樹的節點                        */
/* ---------------------------------------- */
btree insert_node(btree root,int value)
{

   btree newnode;                 /* 樹根指標           */
   btree current;                 /* 目前樹節點指標     */
   btree back;                    /* 父節點指標         */

   /* 建立新節點記憶體 */
   newnode = ( btree ) malloc(sizeof(treenode));
   newnode->data = value;         /* 建立節點內容       */
   newnode->left = NULL;          /* 設定指標初值       */
   newnode->right = NULL;         /* 設定指標初值       */
   if ( root == NULL )            /* 是否是根節點       */
   {
      return newnode;             /* 傳回新節點位置     */
   }
   else
   {
      current = root;             /* 保留目前樹指標     */
      while ( current != NULL )
      {
         back = current;          /* 保留父節點指標     */
         if ( current->data > value )    /* 比較節點值  */
            current = current->left;     /* 左子樹      */
         else
            current = current->right;    /* 右子樹      */
      }
      if ( back->data > value )   /* 接起父子的鏈結     */
         back->left = newnode;    /* 左子樹             */
      else
         back->right = newnode;   /* 右子樹             */
   }
   return root;                   /* 傳回樹根指標       */
}

/* ---------------------------------------- */
/*  建立二元樹                              */
/* ---------------------------------------- */
btree create_btree(int *data,int len)
{
   btree root = NULL;             /* 樹根指標           */
   int i;

   for ( i = 0; i < len; i++ )    /* 用迴路建立樹狀結構 */
      root = insert_node(root,data[i]);
   return root;
}

/* ---------------------------------------- */
/*  二元樹後序走訪                          */
/* ---------------------------------------- */
void postorder(btree ptr)
{
   if ( ptr != NULL )             /* 終止條件           */
   {
      postorder(ptr->left);       /* 左子樹             */
      postorder(ptr->right);      /* 右子樹             */
      printf("[%2d]\n",ptr->data);  /* 列印節點內容     */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立二元樹且用後序走訪列印出來. */
/* ---------------------------------------- */
void main()
{
   btree root = NULL;             /* 樹根指標           */

   /* 二元樹節點資料 */
   int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   root = create_btree(data,9);   /* 建立二元樹         */
   printf("樹的節點內容 \n");
   postorder(root);               /* 後序走訪二元樹     */
}

後來我自己改成遞迴程式(改了insert_node函數)如下:

#include <stdlib.h>
#include <stdio.h>
struct tree                       /* 樹的結構宣告       */
{
   int data;                      /* 節點資料           */
   struct tree *left;             /* 指向左子樹的指標   */
   struct tree *right;            /* 指向右子樹的指標   */
};
typedef struct tree treenode;     /* 樹的結構新型態     */
typedef treenode *btree;          /* 宣告樹節點指標型態 */

/* ---------------------------------------- */
/*  插入二元樹的節點                        */
/* ---------------------------------------- */
btree insert_node(btree root,int value)
{

   btree newnode;                 /* 樹根指標           */
   btree current;                 /* 目前樹節點指標     */
   btree back;                    /* 父節點指標         */

   /* 建立新節點記憶體 */
   newnode = ( btree ) malloc(sizeof(treenode));
   newnode->data = value;         /* 建立節點內容       */
   newnode->left = NULL;          /* 設定指標初值       */
   newnode->right = NULL;         /* 設定指標初值       */
   current = root;
   if ( root == NULL )            /* 是否是根節點       */
   {
      return newnode;             /* 傳回新節點位置     */
   }
  else if(current->data>value) {
insert_node(current->left,value);
return root;
}
  else {;
insert_node(current->right,value);

}
}

/* ---------------------------------------- */
/*  建立二元樹                              */
/* ---------------------------------------- */
btree create_btree(int *data,int len)
{
   btree root = NULL;             /* 樹根指標           */
   int i;

   for ( i = 0; i < len; i++ )    /* 用迴路建立樹狀結構 */
      root = insert_node(root,data[i]);
   return root;
}

/* ---------------------------------------- */
/*  二元樹後序走訪                          */
/* ---------------------------------------- */
void postorder(btree ptr)
{
   if ( ptr != NULL )             /* 終止條件           */
   {
      postorder(ptr->left);       /* 左子樹             */
      postorder(ptr->right);      /* 右子樹             */
      printf("[%2d]\n",ptr->data);  /* 列印節點內容     */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立二元樹且用後序走訪列印出來. */
/* ---------------------------------------- */
void main()
{
   btree root = NULL;             /* 樹根指標           */

   /* 二元樹節點資料 */
   int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   root = create_btree(data,9);   /* 建立二元樹         */
   printf("樹的節點內容 \n");
   postorder(root);               /* 後序走訪二元樹     */
}

 但改成遞迴後，程式結果不一樣
請問我哪裡錯了呢?
我搞了超久了
希望各位高手幫幫忙
拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託
拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託
拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託拜託
拜託拜託拜託拜託拜託拜託拜託拜託拜託.....




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.19.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1588586024.A.B65.html
推 firejox: 沒接上回傳的結點當然會失敗
推 firejox: 你是用指標不是用參考，所以需要加上賦值
感謝你!但可能是我學得不好，是否要改寫insert_node(current->left,value)這句呢?我不知道這句要怎麼改才能有結果可以幫幫我嗎?
※ 編輯: cat99961 (114.42.19.41 臺灣), 05/04/2020 21:25:53
推 elysium5290: 樓上正解，你改寫遞迴但你遞迴的部分怎麼會沒有處理r
→ elysium5290: eturn node呢？
推 firejox: current->left= insert_node(current->left,value) 這樣
推 elysium5290: 稍微回一下大概
→ elysium5290: btree insert_node(btree root, int value)
→ elysium5290: {
→ elysium5290:     if(NULL != root){
→ elysium5290:          If(root->data > value)
→ elysium5290:               root->left = insert_node(root->left
→ elysium5290: , value);
→ elysium5290:          else
→ elysium5290:               root->right = insert_node(root->rig
→ elysium5290: ht, value);
→ elysium5290:         return root;
→ elysium5290:      }
→ elysium5290:      else{
→ elysium5290:            btree newnode;
→ elysium5290:            //以下大概
→ elysium5290:            newnode = malloc()
→ elysium5290:            return newnode;
→ elysium5290:      }
→ elysium5290: }
太感謝了!!我做出來了@@~~太熱心了....弄了超久的...我要來好好地把我一些基礎給搞好
※ 編輯: cat99961 (114.42.19.41 臺灣), 05/05/2020 23:39:30