10_7.c

数据结构 C语言版 本书范例适合初学者学习参考

/* ======================================== */
/*    程序实例: 10_7.c                      */
/*    二叉查找树排序法                      */
/* ======================================== */
#include <stdlib.h>

/* ---------------------------------------- */
/*  建立二叉查找树                          */
/* ---------------------------------------- */
void createbtree(int *btree,int *data,int len)
{
   int level;                     /* 树的层数           */
   int i;

   btree[1] = data[1];            /* 建立根结点         */
   for ( i = 2; i <= len; i++ )   /* 用回路建立其它结点 */
   {
      level = 1;                  /* 从层数1开始        */
      while ( btree[level] != 0 ) /* 是否有子树         */
      {
         if ( data[i] > btree[level] )  /* 是左或右子树 */
            level = level * 2 + 1;      /* 右子树       */
         else
            level = level * 2;    /* 左子树             */
      }
      btree[level] = data[i];     /* 存入结点数据       */
   }
}

/* ---------------------------------------- */
/*  二叉树中序遍历                          */
/* ---------------------------------------- */
void inorder(int *btree,int pos)
{
   if ( btree[pos] != 0 && pos < 16 )   /* 终止条件     */
   {
      inorder(btree,pos*2+1);     /* 左子树             */
      printf("[%d]",btree[pos]);  /* 输出结点内容       */
      inorder(btree,pos*2);       /* 右子树             */
   }
}

/* ---------------------------------------- */
/*  主程序: 使用二叉查找树执行排序         */
/* ---------------------------------------- */
void main()
{
   int btree[16];                 /* 二叉树数组        */
   /* 二叉树结点数据 */
   int data[10] = { 0, 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   int i;

   for ( i = 1; i < 16; i++ )     /* 清除二叉树数组    */
      btree[i] = 0;
   createbtree(btree,data,9);     /* 建立二叉查找树     */
   printf("二叉查找树的内容: ");
   for ( i = 1; i < 16; i++ )     /* 输出出二叉查找树   */
      printf("[%d]",btree[i]);
   printf("\n输出的排序结果: ");
   inorder(btree,1);              /* 输出排序结果       */
   printf("\n");                  /* 换行               */
}