二叉树

/*链式存储结构体类型定义*/
typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} BTree;

/*链式存储二叉树构建函数*/
int BTreeCreate(BTree *tp)
{
    int x;
    scanf("%d",&x);
    if(x<0)
    {
        tp = NULL;
        return 0;
    }
    tp = (BTree *)malloc(sizeof(BTree));
    if(tp == NULL)
        return FALSE;
    tp->data = x;
    BTreeCreate(tp->letf);
    BTreeCreate(tp->right);
    return OK:
}

/*前序遍历 非递归函数*/
void PreOrder(BTree *tp)
{
    BTree *p;
    BTree *stack[MAXIZE];
    int top = -1;
    if(tp == NULL)
        return ;
    else
    {
        top++;
        stack[top] = tp;
        while(top>-1)
        {
            p = stack(top);
            top--;
            printf("%d\t",p->data);
            if(p->right!=NULL)
            {
                top++;
                stack[top] = p->right;
            }
            if(p->left!=NULL)
            {
                top++;
                stack[top] = p->left;
            }
        }
        printf("\n")
    }
}

/*前序遍历 递归函数*/
void PreOrder(BTree *tp)
{
    if(tp == NULL)
        return ;
    else
    {
        printf("%d\t",tp->data);
        PreOrder(tp->left);
        PreOrder(tp->right);
    }
}

/*中序遍历 递归函数*/
void MidOrder(BTree *tp)
{
    if(tp == NULL)
        return ;
    else
    {
        PreOrder(tp->left);
        printf("%d\t",tp->data);
        PreOrder(tp->right);
    }
}

/*后序遍历 递归函数*/
void MidOrder(BTree *tp)
{
    if(tp == NULL)
        return ;
    else
    {
        PreOrder(tp->left);
        PreOrder(tp->right);
        printf("%d\t",tp->data);
    }
}


/* 顺序查找*/
#include <stdlib.h>
#include <stdio.h>
#define N 10

typedef struct node {                        /* 定义线性表的类型 */
  int data[N];
  int length;
} SeqList;
int sq_search(SeqList *p, int k);                /* 声明顺序查找函数 */

int main()
{
  SeqList sl;                             /* 定义线性表 */
  int i, j;
  int k;
  printf("input the elements:\n");
  for(i=0; i<N; i++)
  {
    scanf("%d", &(sl.data[i]));                /* 初始化线性表的各数据元素 */
  }
  sl.length = N;                         /* 初始化线性表的长度 */
  printf("input the key:\n");
  scanf("%d", &k);                         /* 输入要查找的关键字 */
  j = sq_search(&sl, k);                     /* 调用顺序查找函数 */
  printf("-------------------\n");
  if(j >= 0)
  {
    printf("found : data[%d]\n", j);             /* 查找成功 */
  }
  else
  {
    printf("%d is not been found.\n", k);         /* 查找失败 */
  }
  return 0;
}

int sq_search(SeqList *p, int k)             /* 定义顺序查找函数 */
{
  int i = 0;
  int j = -1;
  while(i < N)                            /* 逐个扫描线性表中的所有数据元素 */
  {
    if(p->data[i] == k)
    {
      j = i;                            /* 如果找到，将数据元素所在的位置赋给变量j */
      break;
    }
    i++;
  }
  return j;
}


/* 二分查找 */
#include <stdlib.h>
#include <stdio.h>
#define N 9
typedef struct node {                        /* 定义线性表的类型 */
  int data[N];
  int length;
} SeqList;
int bi_search(SeqList *p, int k);                /* 声明二分查找函数 */

int main()
{
  SeqList sl;                             /* 定义线性表 */
  int i, j, k, t;
  printf("input the elements in ascendant order:\n");
  i = 0;
  scanf("%d", &(sl.data[i]));
  while(i < N-1)                         /* 初始化线性表的各数据元素 */
  {
    scanf("%d", &t);                     /* 输入数据元素的值 */
    if(t > sl.data[i])                         /* 检查输入的数据元素是否满足升序排列要求 */
    {
      i++;
      sl.data[i] = t;                        /* 如果满足要求，进行赋值操作 */
    }
    else
    {
      printf("errer, must bigger than %d\n ", sl.data[i]);        /* 如果不满足要求，输出错误提示信息 */
    }
  }
  sl.length = N;                         /* 初始化线性表的长度 */
  printf("input the key:\n");
  scanf("%d", &k);                         /* 输入要查找的关键字 */
  j = bi_search(&sl, k);                     /* 调用二分查找函数 */
  printf("-------------------\n");
  if(j >= 0)
  {
    printf("found : data[%d]\n", j);             /* 查找成功 */
  }
  else
  {
    printf("%d is not been found.\n", k);         /* 查找失败 */
  }
  return 0;
}

int bi_search(SeqList *p, int k)                 /* 定义二分查找函数 */
{
  int low = 0;
  int high = p-> length;
  int mid;
  while(low <= high)
  {
    mid = (low+high)/2;
    if(p->data[mid] == k)                    /* 查找成功 */
      return mid;
    else if(p->data[mid] > k)                /* 中间位置的数据元素大于关键字 */
      high = mid-1;
    else                                /* 中间位置的数据元素小于关键字 */
      low = mid+1;
  }
  return -1;
}