Re: [問題] 把陣列數值丟進引線二元樹 並用inoder印出
※ 引述《ke60811 (胖臉嘎在哪?笑)》之銘言：
這是程式碼 執行會跳出錯誤 請大大幫忙解答
root為空節點---> root
---> O <--
| / |
( A ) |
| /| |\ |
| O | | O |
|-||-- -||--
#include<iostream>
using namespace std;
typedef struct treenode *tree_pointer;
typedef struct treenode{
int left_thread;
tree_pointer left_child;
int data;
int right_thread;
tree_pointer right_child;
};
void insert_node(tree_pointer *node,int num,tree_pointer *r);
tree_pointer modified_search(tree_pointer root,int key);
void Insert_right(tree_pointer parent, tree_pointer child);
void Insert_Left(tree_pointer parent, tree_pointer child);
tree_pointer insucc(tree_pointer tree);
void tinorder(tree_pointer tree);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
以上對於節點的基本操作都有了
怎麼沒有更基本的建立跟摧毀函式？
或者另外用個資料結構包裝root跟size
如果有個外覆結構體threadtree
你可以很清楚的把事情改成
"將key放入到threadtree"
"在threadtree找key"
"移除某個key"
"清除整個tree"
而且可以很清楚的知道樹的根以及總節點數
由總節點數可以知道該不該讓search,remove工作停止。
另外你還可以為search製作私有版本跟公開版本
私有版本如
tree_pointer tree_search_node(tree_pointer tree,int key); /* 回傳節點 */
公開版本
int* tree_search(tree_pointer tree,int key) /* 回傳資料位址 */
如此就可以定義樹的操作如
tree_pointer tree_create();
void tree_delete(tree_pointer tree);
void tree_insert(tree_pointer tree,int key);
int* tree_search(tree_pointer tree,int key);
void tree_clear(tree_pointer tree);
int tree_size(const tree_pointer tree);
int tree_empty(const tree_pointer tree);
int main(){
int a[11] = {7,4,1,5,16,8,11,12,15,9,2};
tree_pointer A,root;
A = (tree_pointer)malloc( sizeof(tree_pointer) );
root = (tree_pointer)malloc( sizeof(tree_pointer) );
A = NULL;
root = NULL;
for(int i=0;i<11;i++)
insert_node(&A,a[i],&root);
tinorder(root);
system("pause");
return 0;
}
void insert_node(tree_pointer *node,int num,tree_pointer *r){
tree_pointer ptr,temp;
(*r)->right_child=*r;
(*r)->left_child=*node;
ptr=(tree_pointer)malloc(sizeof(tree_pointer));
temp=modified_search(*node,num);
(*r)->left_thread=(*r)->right_thread=0;
temp->left_thread=temp->right_thread=1;
ptr->data=num;
ptr->left_child=ptr->right_child=NULL;
if(*node){
if(num<temp->data){
temp->left_child=*r;
Insert_Left(temp,ptr);
}
else{
temp->right_child=*r;
Insert_right(temp,ptr);
}
}
else *node = ptr;
}
tree_pointer modified_search(tree_pointer root,int key){
tree_pointer tree,p_tree;
/* 有必要建立一份記憶體區塊嗎？ */
tree=(tree_pointer)malloc(sizeof(tree_pointer));
p_tree=(tree_pointer)malloc(sizeof(tree_pointer));
if(root == NULL)
return NULL;
else
/* 這裡就把剛剛配置的tree指標覆蓋掉了 */
tree=root;
while(tree!=NULL){
/* 這裡就把剛剛配置的p_tree指標覆蓋掉了 */
p_tree=tree;
if(key == tree->data) /* 為什麼找到了卻是回傳NULL ?! */
return NULL;
if(key<tree->data)
tree=tree->left_child;
else
tree=tree->right_child;
}
return p_tree;
}
tree_pointer insucc(tree_pointer tree){
tree_pointer temp;
/* 這裡取得了一塊空間 */
temp=(tree_pointer)malloc(sizeof(tree_pointer));
/* 這裡卻又把剛剛的指標覆蓋掉 */
temp = tree->right_child;
if(!tree->right_thread)
while(!temp->left_thread)
temp = temp->left_child;
return temp;
}
void tinorder(tree_pointer tree){
tree_pointer temp;
/* 這裡取得了一塊空間 */
temp=(tree_pointer)malloc(sizeof(tree_pointer));
/* 這裡覆蓋掉剛取得的位址 */
temp=tree;
for(;;){
temp = insucc(temp);
if(temp==tree)
break;
cout<<" "<<temp->data;
}
}
void Insert_right(tree_pointer parent, tree_pointer child) {
tree_pointer temp;
temp=(tree_pointer)malloc(sizeof(tree_pointer));
child->right_child = parent->right_child;
child->right_thread = parent->right_thread;
child->left_child = parent;
child->left_thread = 1;
parent->right_child = child;
parent->right_thread = 0;
if (!child->right_thread) {
/* 這裡把配置給temp的記憶體位址覆蓋掉了 */
temp = insucc(child);
temp->left_child = child;
}
}
void Insert_Left(tree_pointer parent, tree_pointer child){
tree_pointer temp;
temp=(tree_pointer)malloc(sizeof(tree_pointer));
child->left_child = parent->left_child;
child->left_thread = parent->left_thread;
child->right_child = parent;
child->right_thread = 1;
parent->left_child = child;
parent->left_thread = 0;
if (!child->left_thread) {
/* 這裡把配置給temp的記憶體位址覆蓋掉了 */
temp = insucc(child);
temp->right_child = child;
}
}
一般來說
我們寫insert,不會是插入節點吧？！
應該是插入key。
不管怎麼樣，依照你的問題，最明顯的就是modified_search
找到了節點了卻還要回傳NULL
額外的問題，你的程式有很嚴重的memory leak。
更嚴重的是排版不佳
配置記憶體的工作已經混亂到哪裡都得配置了，建議你把函式參數的
責任關係給釐清
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.124.207
※ 編輯: sunneo 來自: 61.227.124.207 (04/09 03:58)
推
04/09 13:11, , 1F
04/09 13:11, 1F
→
04/09 13:11, , 2F
04/09 13:11, 2F
→
04/09 13:12, , 3F
04/09 13:12, 3F
→
04/09 13:35, , 4F
04/09 13:35, 4F
※ 編輯: sunneo 來自: 61.227.118.128 (04/09 13:37)