查找二叉树的建立

#include <stdio.h>
#include <stdlib.h>

#define MAXSTACK 64

//假定关键字类型为整数

typedef int KeyType;

typedef struct
{
} InfoType;

typedef struct node
{ //结点类型

  KeyType key; //关键字项

  InfoType otherinfo; //其它数据域，InfoType视应用情况而定，下面不处理它

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

} BSTNode;

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


void InsertBST(BSTree *Tptr, KeyType key)
{
    //若二叉排序树 *Tptr中没有关键字为key，则插入，否则直接返回

    BSTNode *current, *p = (*Tptr); //p的初值指向根结点

    //查找插入位置

    while (p)
    {
        //树中已有key，无须插入

        if (p->key == key)
            return;
        //f保存当前查找的结点

        current = p;
        //若keykey，则在左子树中查找，否则在右子树中查找

        p = (key < p->key) ? p->lchild : p->rchild;
    }
    
    p = (BSTNode *)malloc(sizeof(BSTNode));
    p->key = key;
    p->lchild = NULL;
    p->rchild = NULL;
    
    //原树为空

    if ((*Tptr) == NULL)
    {
        (*Tptr) = p;
    }
    else //原树非空时将新结点关p作为关curreent的左孩子或右孩子插入

    {
        //p = (key < p->key) ? current->lchild : current->rchild;

        if (key < current->key)
         current->lchild = p;
        else
           current->rchild = p;
    }
}

BSTree CreateBST(void)
{
    //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回

    //初始时T为空树

    BSTree T=NULL;
    KeyType key;
    
    scanf("%d", &key);
    getchar();
    while (key)
    {
        InsertBST(&T, key);
        scanf("%d", &key);
        getchar();
    }

    return T;
}

// 非递归中序遍历二叉树

void LNRtree(BSTree t)
{
  BSTree tmp = NULL;
  // 保存节点的栈

  BSTree stack[MAXSTACK];
  int top = 0;
  
  memset(stack, 0x00, sizeof(stack));

  tmp = t;

  while((tmp != NULL) || (top > 0))
  {
     if (tmp != NULL)
     {
        stack[top++] = tmp;
        tmp = tmp->lchild;
     }
     else
     {
        tmp = stack[--top];
        printf("%d\n", tmp->key);
        tmp = tmp->rchild;
     }
  }
}

int main(int argc, char *argv[])
{
  BSTree tp = CreateBST();
  LNRtree(tp);
  system("PAUSE");    
  return 0;
}

/* 查找二叉树按中序遍历，其键值会成递增排列，哈弗曼排列未必如此 */