一个二叉排序树的实际例子

用二叉排序树实现的将乱序输入字母按从小到大排列,无重复输出项.

#include<stdio.h>
#include<stdlib.h>
#include<strings.h>
typedef struct node{
    char data;
    struct node *left;
    struct node *right;
}node;
/*
* 中序遍历
*/
void print_node(node *p){
    if(p){
        print_node(p->left);
        printf("%c",p->data);
        print_node(p->right);
    }
}

int main(void){
    node *head;
    char tmp;
    node *p;
/*生成头节点*/
    head=(node *)malloc(sizeof(node));
    if (!head){
        printf("1:malloc error!\n");
        return -1;
    }
/*将头节点填充0*/
    bzero(head,sizeof(node));
    while ((tmp=getchar())!=EOF){
/*判断头节点是否为空*/
        if (!head->data){
            head->data=tmp;
            head->left=NULL;
            head->right=NULL;
        }else{
            p=head;
/*分配新节点空间*/
            node *new_node=(node *)malloc(sizeof(node));
            if (!new_node){
                printf("2:malloc error!\n");
                return(-1);
            }
            bzero(new_node,sizeof(node));
/*搜索二叉排序树*/
            while(1){
/*排除重复输入项*/
                if (tmp==p->data){
                    free(new_node);
                    break;
                }else if(tmp < p->data){
/*左子数非空,转向左子树*/
                    if (p->left){
                        p=p->left;
/*左子树为空,将新节点挂载在左子树上*/
                    }else{
                        new_node->data=tmp;
                        p->left=new_node;
                        break;
                    }
                }else{
                    if (p->right){
                        p=p->right;
                    }else{
                        new_node->data=tmp;
                        p->right=new_node;
                        break;
                    }
                }
            }
        }
    }
/*二叉搜索树建立完毕,中序遍历输出*/
    print_node(head);
    printf("\n");
    return 0;
}