ChenGen

一切归零，重新开始
随笔 - 13, 文章 - 10, 评论 - 21, 引用 - 0
数据加载中……

复习二叉排序树

   二叉排序数是一种很重要的数据结构，今天复习了一下如何创建一棵二叉排序数＆二叉排序数的两种中序遍历方法——递归中序遍历＆非递归的中序遍历。

   宏定义＆头文件：

#include  " stdio.h "
#include  " stdlib.h "   /* 内存分配*/
#include  " ctype.h "   /* 字符操作*/
#define MAXNUM  100   /* 非递归时的栈的大小*/


   数据结构：

typedef struct node {
     int  data;
    struct node  * left;
    struct node  * right;
}  Node;

   生成一棵二叉排序数：   
Node *CreateTree()
{
    int p,data;
    char buffer[100],ch;
    Node *head;
    head=NULL;    /*This is very important!*/
    while((ch=getchar())!=EOF){
        p=0;
        if(isspace(ch)) /*过滤空格*/
            continue;
        else if(isdigit(ch)){
            buffer[p++]=ch;
            for(ch=getchar();isdigit(ch);ch=getchar())
                buffer[p++]=ch;
            ungetc(ch,stdin);
            buffer[p]='\0';
            data=atoi(buffer); /*将字符串转化为整数*/
        }
        InsertNode(&head,data);/*向树中插入一个结点*/
    }
    return head;
}

void InsertNode(Node **head,int data)
{
    if(*head==NULL){ /*如果结点为空，正是要插入的位置*/
        *head=(Node *)malloc(sizeof(Node));
        (*head)->data=data;
        (*head)->left=NULL;
        (*head)->right=NULL;
    }
    else{
        if(data<(*head)->data) InsertNode(&((*head)->left),data);/*插入左子树*/
        else InsertNode(&((*head)->right),data);/*插入右子树*/
    }
}

   二叉排序数的递归中序遍历：
void MidTravel(Node *head)
{
    if(head){
        MidTravel(head->left); /*遍历左子树*/
        printf("%d\t",head->data); /*输出结点值*/
        MidTravel(head->right); /*遍历又子树*/
    }
}

   二叉排序数的非递归遍历：
void MidTravel2(Node *p)
{
    Node *a[MAXNUM]; /*栈*/
    int top; /*栈顶*/
    top=0;
    while(p || top){
        while(p){
            if(top==MAXNUM) {
                printf("over flow\n");
                exit(-1);
            }
            a[top++]=p; /*入栈*/
            p=p->left; /*遍历左子树*/
        }
        if(top){
            p=a[--top]; /*出栈*/
            printf("%d\t",p->data); /*输出结点值*/
            p=p->right; /*遍历右子树*/ 
        }
    }
}

posted on 2006-09-27 14:33 ChenGen 阅读(1655) 评论(2)  编辑  收藏 所属分类: 数据结构复习

评论

# re: 复习二叉排序树  回复  更多评论   

又有沙发座了
2006-09-27 11:05 | 坏男孩1

# re: 复习二叉排序树  回复  更多评论   

呵呵，支持下！
2006-09-28 08:37 | 冰川

只有注册用户登录后才能发表评论。
网站导航: