Re: [問題] 二元樹插入節點

看板C_and_CPP (C/C++)作者Lizstlin (Lizst)時間16年前 (2010/06/14 09:47)推噓3(3推 0噓 11→)

留言14則, 4人參與討論串2/2 (看更多)

※ 引述《Lizstlin (Lizst)》之銘言： : 遇到的問題： : 插入節點的基本架構已經寫好了, 這是我拙劣的code : http://gist.github.com/435574 : input檔的內容如下： : 1,10,0,0 : 2,20,1,0,3,40,1,1 : 4,30,2,0,5,50,3,0,6,60,3,1 : 7,70,5,1 : 這四行數字代表右圖的tree : 每行代表tree的每個level : 每4個數代表一個node : 第一個數是id，第二個數是data，第三個數是parent的id : 第四個數代表自己是左子樹（0）或是右子樹（1） : 比方node 6, id是6，data是60，parent id是3，是右子樹 : 所以在input檔裡的第三行（level 3）的第四組數字就是6,60,3,1 : 不過, 小弟不知道應該加什麼條件才能在正確的地方插入節點 : 目前得到的樹狀圖就是個剪刀刃形狀 : (是有想到利用parent 的id 來做插入, 但是不知道如何指向父節點) : 希望得到的的樹狀圖如下 : 10 : / \ : 20 40 : / / \ : 30 50 60 : \ : 70 : 插入節點的順序是 10, 20, 40, 30, 50, 60 ,70 : 這是錯誤的執行結果: : prefix：10 20 30 50 40 60 70 : infix：50 30 20 10 40 60 70 : postfix：50 30 20 70 60 40 10 : 希望得到的正確結果： : prefix：10 20 30 40 50 70 60 : infix：30 20 10 50 70 40 60 : postfix：30 20 70 50 60 40 10 : 希望高人指點, 謝謝^^" 不好意思, 又來請教各位了. 我修改之後變這樣 class BinaryTree { TreeNode *root; void showInOrder(TreeNode *); void showPreOrder(TreeNode *); void showPostOrder(TreeNode *); public: TreeNode *StoreNode[150]; BinaryTree() { root = NULL; } void insertNode(int, int, int, int); void coutInOrder() { showInOrder(root); } void coutPreOrder() { showPreOrder(root); } void coutPostOrder() { showPostOrder(root); } }; void BinaryTree::insertNode (int id, int num, int parent, int LR) { TreeNode *NewNode = new TreeNode; TreeNode *TempNode; NewNode->left = NewNode->right = NULL; NewNode->data = num; if (root == NULL) { root = NewNode; StoreNode[0] = NewNode; } else { int i = id; while (i) { if (i != parent) { i--; } else { TempNode = StoreNode[i-1]; break; } } while (TempNode) { if (LR == 0) { if (TempNode->left) { TempNode = TempNode->left; } else { TempNode->left = NewNode; StoreNode[id-1]->left = NewNode; break; } } else if (LR == 1) { if(TempNode->right) { TempNode = TempNode->right; } else { TempNode->right = NewNode; StoreNode[id-1]->right = NewNode; break; } } } } } 但是執行的時候會爆掉 ~"~ 不知道哪裡出問題了, 希望有人可以替我解答謝謝. 感激不盡 T~T -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.202.31