开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 数据结构 > 查看源码
7_6.C
资源名称：04722-x　[点击查看]
上传用户：wyn840322
上传日期：2007-01-13
资源大小：294k
文件大小：4k
源码类别：

数据结构

开发平台：

C/C++

7_6.C：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 7_6.c                       */
  3. /*    二叉树的搜索方式                      */
  4. /* ======================================== */
  5. #include <stdlib.h>
  7. struct tree                       /* 树的结构宣告       */
  8. {
  9.    int data;                      /* 节点数据           */
  10.    struct tree *left;             /* 指向左子树的指标   */
  11.    struct tree *right;            /* 指向右子树的指标   */
  12. };
  13. typedef struct tree treenode;     /* 树的结构新型态     */
  14. typedef treenode *btree;          /* 宣告树节点指标型态 */
  16. /* ---------------------------------------- */
  17. /*  建立二叉树                              */
  18. /* ---------------------------------------- */
  19. btree createbtree(int *data,int pos)
  20. {
  21.    btree newnode;                 /* 新节点指标         */
  23.    if ( data[pos] == 0 || pos > 15 )  /* 终止条件       */
  24.       return NULL;
  25.    else
  26.    {
  27.       /* 建立新节点记忆体 */
  28.       newnode = ( btree ) malloc(sizeof(treenode));
  29.       newnode->data = data[pos];  /* 建立节点内容       */
  30.       /* 建立左子树的递归呼叫 */
  31.       newnode->left = createbtree(data,2*pos);
  32.       /* 建立右子树的递归呼叫 */
  33.       newnode->right = createbtree(data,2*pos+1);
  34.       return newnode;
  35.    }
  36. }
  38. /* ---------------------------------------- */
  39. /*  二叉搜索树的搜索                        */
  40. /* ---------------------------------------- */
  41. btree btreefind(btree ptr,int value)
  42. {
  43.    while ( ptr != NULL )          /* 主回路             */
  44.    {
  45.       if ( ptr->data == value )   /* 找到了             */
  46.          return ptr;              /* 传回节点指标       */
  47.       else
  48.          if ( ptr->data > value ) /* 比较数据           */
  49.             ptr = ptr->left;      /* 左子树             */
  50.          else
  51.             ptr = ptr->right;     /* 右子树             */
  52.    }
  53.    return NULL;                   /* 没有找到           */
  54. }
  56. /* ---------------------------------------- */
  57. /*  二叉树遍历搜索                          */
  58. /* ---------------------------------------- */
  59. btree btreesearch(btree ptr,int value)
  60. {
  61.    btree ptr1,ptr2;
  63.    if ( ptr != NULL )             /* 终止条件           */
  64.    {
  65.       if ( ptr->data == value )   /* 找到了             */
  66.          return ptr;              /* 传回节点指标       */
  67.       else
  68.       /* 往左子树找 */
  69.       ptr1 = btreesearch(ptr->left,value);
  70.       /* 往右子树找 */
  71.       ptr2 = btreesearch(ptr->right,value);
  72.       if ( ptr1 != NULL )
  73.          return ptr1;             /* 在左子树           */
  74.       else
  75.          if ( ptr2 != NULL )
  76.             return ptr2;          /* 在右子树           */
  77.          else
  78.             return NULL;          /* 没有找到           */
  79.    }
  80.    else
  81.       return NULL;                /* 是叶节点           */
  82. }
  84. /* ---------------------------------------- */
  85. /*  主程式: 二叉树搜索方式.                 */
  86. /* ---------------------------------------- */
  87. void main()
  88. {
  89.    btree root = NULL;             /* 树根指标           */
  90.    btree ptr = NULL;              /* 树根指标           */
  91.    int value;                     /* 节点值             */
  93.    /* 二叉树节点数据 */
  94.    int data[16] = { 0, 5, 4, 6, 2, 0, 0, 8, 1,
  95.                     3, 0, 0, 0, 0, 7, 9 };
  96.    root = createbtree(data,1);    /* 建立树状结构       */
  97.    printf("请输入寻找节点数据(1 - 9) ==> ");
  98.    scanf("%d",&value);            /* 读取节点数据       */
  99.    ptr = btreefind(root,value);   /* 二叉树搜索         */
  100.    if ( ptr != NULL )
  101.       printf("二叉搜索树: 节点数据是 [%d]n",ptr->data);
  102.    else
  103.       printf("二叉搜索树: 没有找到n");
  104.    ptr = btreesearch(root,value); /* 遍历搜索         */
  105.    if ( ptr != NULL )
  106.       printf("遍历搜索: 节点数据是 [%d]n",ptr->data);
  107.    else
  108.       printf("遍历搜索: 没有找到n");
  109. }