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

看板C_and_CPP作者cat99961 (阿湯)時間4年前 (2020/05/04 17:53)推噓5(5推 0噓 19→)

留言24則, 2人參與討論串1/1

我要將二元搜尋樹的迴圈改成遞迴(改原程式的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

05/04 18:34, 4年前 , 1^F

05/04 18:34, 1^F

推

firejox

05/04 18:37, 4年前 , 2^F

05/04 18:37, 2^F

感謝你!但可能是我學得不好，是否要改寫insert_node(current->left,value)這句呢?我不知道這句要怎麼改才能有結果可以幫幫我嗎? ※ 編輯: cat99961 (114.42.19.41 臺灣), 05/04/2020 21:25:53

推