January 5, 2008

binary tree

/*
* 姓名:紀欣亞
* 學號:495430046
* 系級:通訊工程學系二年級
* 程式名稱:二元樹的各項操作
* 程式功能與描述:做各式的二元樹操作(such as insert,delete,represent,search)
* 變數名稱:(標示在宣告旁邊)
* sample in: 一個指令搭配一個操作變數
* 防呆: 1.不允許輸入未列出的指令
* 2.不允許重複數字在樹中
* 3.樹被刪空時,提出警語
* 4.不允許刪除不在樹裡的數字
* 心得:花了好幾天來測試,本來以為完成了,結果不小心又測到bug。
* 就是刪除根節點問題。本來以為是副函式判斷式的錯誤,結果
* 是因為宣告問題。不小心在副函式中又宣告相同名稱,結果把
* global蓋掉了。一回傳就會發生錯誤,這種錯誤好難發現唷 !
* 在使用全域變數時,真的要很小心!!! 還有原來VC的debug
* step by step的功能可以直接用滑鼠點一點,就可以知道樹的
* 分支,進而可以知道有沒有連壞掉的地方,真的還挺方便的!!
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct data* pointer;
struct data
{
int node; //欲操作的變數
struct data *right; //連向右子樹指標
struct data *left; //連向左子樹指標
};
pointer head=NULL; //根節點
/*=========二元樹的生長===========*/
void add(struct data **head,int da)
{
if((*head)==NULL)//一開始根節點無東西時
{ /*配置記憶體*/
struct data* temp=(pointer)malloc(sizeof(struct data));
temp->node=da; //置入資料(temp接收資料)
temp->left=NULL; //接地
temp->right=NULL;//接地
*head=temp; //傳遞給head
}
else//至少有一元素在樹裡時
{
if((*head)->node>da)//把較小的元素接到左子樹
add(&(*head)->left,da);
else //把較大的元素接到右子樹
add(&(*head)->right,da);
}
}
/*=========inorder traversal==========*/
void inorder(struct data* head)
{
if(head!=NULL)
{
inorder(head->left);
printf(" %d",head->node);
inorder(head->right);
}
}
/*================delete================*/
void deletetree(int number)
{
pointer parent; /*父節點指標 */
pointer ptr; /*刪除節點指標*/
pointer child; /*子節點指標 */
int isfound=0; /*是否找到刪除節點*/
parent=ptr=head;
while(ptr!=NULL&&!isfound )
{
if(ptr->node==number )
isfound=1;//找到刪除節點
else
{
parent=ptr; //保留父節點指標
if(ptr->node>number ) //節點大於刪除節點
ptr=ptr->left; //往左子樹
else //若相反
ptr=ptr->right; //往右子樹
}
}
if ( ptr==NULL )
{ //沒有找到刪除節點
printf("不存在!!!\n\n");
return;
}
if(ptr->left==NULL&&ptr->right==NULL&&ptr==head)
{
head=NULL;
ptr=NULL;
printf("!空空如也!\n\n");
return;
}
/*===============case1:leaf node===============*/
if(ptr->left==NULL && ptr->right==NULL )
{
if(parent->left==ptr)//欲刪除節點在左子樹
parent->left=NULL; //左子樹接地
else
parent->right=NULL;//右子樹接地

free(ptr);//釋放節點記憶體
return;
}

/*==============case2:no left-child tree===========*/
if(ptr->left==NULL)
{
if(parent!=ptr)//父節點不等於刪除節點
{
if(parent->left==ptr)//左子節點為刪除節點
parent->left=ptr->right; //左節點指向刪除節點右子節點
else
parent->right=ptr->right; //右節點向刪除節點右子節點
}
else
head=head->right;//根節點指向右子節點

free(ptr);//釋放節點記憶體
return ;
}

/*==============case3:no right-child tree=============*/
if(ptr->right==NULL)
{
if(parent!=ptr)//父節點不等於刪除節點
{
if(parent->right==ptr)//右子節點為刪除節點
parent->right=ptr->left;//右節點向刪除節點左子節點
else
parent->left=ptr->left; //左節點向刪除節點左子節點
}
else head=head->left;//根節點指向左子節點

free(ptr);//釋放節點記憶體
return ;
}

/*===============case4:have both===============*/
parent=ptr;//父節點指向刪除節點
child=ptr->left;//設定成左子節點

while(child->right!=NULL)//找到最右的葉節點
{
parent=child; //保留父節點指標
child=child->right; //往右子樹
}
ptr->node=child->node; //變成葉節點
if(parent->left==child) //子節點無右子樹
parent->left=child->left;//連結左葉節點
else
parent->right=child->left;

free(child);//釋回節點記憶體
return;

}
/*================search===============================*/
int search(pointer head,int number)
{ //比較節點與輸入值相同時回傳1
pointer ptr=head;
while(ptr!=NULL)
{
if(ptr->node==number)//找到了
return 1;
else
if(ptr->node>number)//比較
ptr=ptr->left; //節點大於輸入值往左子樹
else
ptr=ptr->right; //節點小於輸入值往右子樹
}
return 0;//未找到
}
/*================print================================*/
void print(pointer pointer) //顯示二元樹
{
if(head==NULL)//空時
{
printf("empty!!\n");return;
}
else//至少有一元素時
printf("%d",pointer->node);
if(pointer->left) //有左子樹
{
printf("(");
print(pointer->left);
}
else if(pointer->left==NULL) //只有右子樹
{
if(pointer->right)
{
printf("(");
}
}
if(pointer->right) //有右子樹
{
if(pointer->left)
{
printf(",");
}
print(pointer->right);
printf(")");
}
else if(pointer->right==NULL) //只有左子樹
{
if(pointer->left)
{
printf(")");
}
}
}
void main()
{
int choice;//選項
int da;//欲輸入的數字
int judge;//判斷是否在裡面
while(choice!=6)
{
printf("\n1.新增一筆資料\n");
printf("2.刪除一筆資料\n");
printf("3.查詢\n");
printf("4.顯示\n");
printf("5.輸出inorder travesal的結果\n");
printf("6. exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("請輸入:\n");
scanf("%d",&da);
judge=search(head,da);//判斷是否重複
if(judge==1) //不容許重複
printf("重覆已存在數字!!\n");
else
add(&head,da); //未重複,進行增加
break;
case 2:
printf("輸入欲刪除的節點:");
scanf("%d",&da);
deletetree(da);
//root=head;
break;
case 3:
printf("\n輸入欲查詢的數字:");
scanf("%d",&da);
judge=search(head,da);
if(judge==1)
printf("找到了!!\n");
else
printf("沒有T_T\n");
break;
case 4:
print(head);
break;
case 5:
inorder(head);
break;
case 6:break;//離開
default:
printf("ERROR!!\n");
break;
}
}
}

0推薦此文章
Today's Visitors: 0 Total Visitors: 34
Personal Category: Uncategorized Articles Topic: technology
[Trackback URL]

Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0