※ [本文轉錄自 ask 看板 #1GLTt29K ]

作者: supercygnus (......) 看板: ask
標題: [請問] C語言二元搜尋樹levelorder traversal
時間: Sun Sep 16 22:10:08 2012

以下是我的程式碼


網頁版:http://ideone.com/2HN1Z

#include<iostream>
#define N 100

using namespace std;

struct TreeNode{

int value;
TreeNode *left;
TreeNode *right;


};



struct Queue{
TreeNode queuearray[N];
int rear;
int front;


};
Queue q;


int isEmpty(Queue *);
void BST_insert(int,TreeNode **);
void queueMove(Queue *);
void levelOrder(TreeNode *);
void preorder(TreeNode *);
void inorder(TreeNode *);
void postorder(TreeNode *);
TreeNode* BST_delete(TreeNode *,int);
void createQueue(Queue *);

int main(void){



int data;
TreeNode *root=NULL;

int choose,loopflag=1;

while(loopflag){

cout << "\n(1)插入節點\n(2)Level Order列出樹中所有節點\n(3)前序追蹤\n(4)中序
追蹤\n(5)後序追蹤\n(6)刪除一元素\n(0)結束 => ";
cin >> choose;
switch(choose){
case 0:
loopflag=0;
break;
case 1:

cout << "請輸入欲放入之資料=> ";
cin >> data;
BST_insert(data,&root);
break;
case 2:
levelOrder(root);
break;
case 3:
preorder(root);
break;
case 4:
inorder(root);
break;
case 5:
postorder(root);
break;
case 6:
cin>>data;
BST_delete(root,data);
break;
default:
cout<<"輸入錯誤"<<endl;
break;


}




}


return 0;


}


void BST_insert(int x,TreeNode **root){
TreeNode *q=*root,*r=NULL;

while(q!=NULL){
r=q;
if(x<q->value)
q=q->left;
else
q=q->right;
}


q=new TreeNode;

q->value=x;
q->left=NULL;
q->right=NULL;
if(r==NULL)
*root=q;
else if(x<r->value)
r->left=q;
else
r->right=q;

}

void createQueue(Queue *p){
p->rear=-1;
p->front=-1;
}


void enQueue(Queue *p,TreeNode *x){
if(p->rear==N-1)
queueMove(p);


p->rear++;
p->queuearray[p->rear]=*x;



}

void deQueue(Queue *p,TreeNode *x){
p->front++;
*x=p->queuearray[p->front];

}

void queueMove(Queue *p){
int i;
for(i=p->front+1;i<=p->rear;i++)
p->queuearray[i-p->front-1]=p->queuearray[i];
p->rear=p->rear-p->front-1;
p->front=-1;

}

int isEmpty(Queue *p){
if(p->rear==p->front)
return 1;
}



void levelOrder(TreeNode *ptr){
TreeNode* k;

createQueue(&q);

enQueue(&q,ptr);
while(!(isEmpty(&q))){

deQueue(&q,k);
ptr=k;
cout<<"Visit"<<k->value<<" ";

if(ptr->left!=NULL)
enQueue(&q,ptr->left);
if(ptr->right!=NULL)
enQueue(&q,ptr->right);


}

}


void preorder(TreeNode *ptr){
if(ptr!=NULL){
cout<<ptr->value<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}


void inorder(TreeNode *ptr){
if(ptr!=NULL){
inorder(ptr->left);
cout<<ptr->value<<" ";
inorder(ptr->right);
}
}

void postorder(TreeNode *ptr){
if(ptr!=NULL){
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->value<<" ";

}
}

TreeNode* BST_delete(TreeNode *ptr,int x){

int found=0,direction=0;
TreeNode *r,*q,*s,*t;

r=q=s=NULL;
t=ptr;

while(ptr!=NULL && !found)
{
if(x == ptr->value)
found=1;
else if(x< ptr->value)
{
direction=1;
r=ptr;
ptr=ptr->left;
}
else
{
direction=0;
r=ptr;
ptr=ptr->right;
}
}
if(ptr == NULL)
cout<<"找不到該節點"<<endl;


if(r == NULL)
{
if(ptr->right == NULL)
return(ptr->left);
else if(ptr->left == NULL)
return(ptr->right);
}
if(ptr->right == NULL)
{
if(direction == 1)
r->left=ptr->left;
else
r->right=ptr->left;
}
else if(ptr->left == NULL)
{
if(direction == 1)
r->left=ptr->right;
else
r->right=ptr->right;
}
else
{
s=ptr;
q=ptr->left;
while(q->right != NULL)
{
s=q;
q=q->right;
}
ptr->value=q->value;
if(ptr == s)
s->left=q->left;
else
s->right=q->left;
}


}



但是level order traversal跑不出來
請問要怎麼改才可以跑呢0.0
用的是DevC++
如果有人很好心的話幫忙轉到C++版一下,感恩

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.253.210.88

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: supercygnus (111.253.210.88), 時間: 09/16/2012 22:19:44
※ 編輯: supercygnus 來自: 111.253.210.88 (09/16 22:26)