三、代码清单

    [cpp]

    #include<stdio.h>

    #include<stdlib.h>

    #define maxSize 20

    #define maxWidth 20

    typedef int KeyType; //假定关键字类型为整数

    typedef struct node { //结点类型

    KeyType key; //关键字项

    struct node *lchild,*rchild;//左右孩子指针

    } BSTNode,BSTree;

    //typedef BSTNode *BSTree; //BSTree是二叉排序树的类型

    //先序遍历

    void preOrder（BSTree *BT）

    {

    if（BT!= NULL）

    {

    printf（"%d",BT->key）；

    preOrder（BT->lchild）；

    preOrder（BT->rchild）；

    }

    }

    //中序遍历

    void inOrder（BSTree *BT）

    {

    if（BT!= NULL）

    {

    inOrder（BT->lchild）；

    printf（"%d",BT->key）；

    inOrder（BT->rchild）；

    }

    }

    //后序遍历

    void postOrder（BSTree *BT）

    {

    if（BT!= NULL）

    {

    postOrder（BT->lchild）；

    postOrder（BT->rchild）；

    printf（"%d",BT->key）；

    }

    }

    //层次法打印树

    void dispTree（BSTree *BT）

    {

    BSTree *stack[maxSize],*p;

    int level[maxSize] ,top,n,i,width=4;

    if（BT!=NULL）

    {

    printf（"Display a tree by hollow means.\n"）；

    top=1;

    stack[top]=BT;//push root point to stack.

    level[top][0]=width;

    while（top>0）

    {

    p=stack[top];

    n=level[top][0];

    for（i=1;i<=n;i++）

    printf（" "）；

    printf（"%d",p->key）；

    for（i=n+1;i<maxWidth;i+=2）

    printf（"--"）；

    printf（"\n"）；

    top--;

    if（p->rchild!=NULL）

    {

    top++;

    stack[top]=p->rchild;

    level[top][0]=n+width;

    level[top] =2;

    }

    if（p->lchild!=NULL）

    {

    top++;

    stack[top]=p->lchild;

    level[top][0]=n+width;

    level[top] =1;

    }

    }

    }

    }

    /* 向二叉排序树中加入一个结点

    要改变指针，需要传递指针的指针*/

    int InsertNode（BSTree **tree, KeyType key）

    {

    BSTNode *p= NULL, *parent = NULL;

    BSTNode *pNewNode = （BSTNode *）malloc（sizeof（BSTNode））；

    if （pNewNode==NULL）

    {

    return -1;

    }