Fw: [請問] C語言二元搜尋樹levelorder traversal
※ [本文轉錄自 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)
推
09/17 09:07, , 1F
09/17 09:07, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：