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

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

数据结构

开发平台：

C/C++

7_11.C：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 7_11.c                      */
  3. /*    表达式二叉树的建立和计值              */
  4. /* ======================================== */
  5. #include <stdlib.h>
  7. struct tree                       /* 树的结构宣告       */
  8. {
  9.    char 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 > 7 )   /* 终止条件       */
  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. void inorder(btree ptr)
  42. {
  43.    if ( ptr != NULL )             /* 终止条件           */
  44.    {
  45.       inorder(ptr->left);         /* 左子树             */
  46.       printf("%c",ptr->data);     /* 列印节点内容       */
  47.       inorder(ptr->right);        /* 右子树             */
  48.    }
  49. }
  51. /* ---------------------------------------- */
  52. /*  表达式二叉树前序列印                    */
  53. /* ---------------------------------------- */
  54. void preorder(btree ptr)
  55. {
  56.    if ( ptr != NULL )             /* 终止条件           */
  57.    {
  58.       printf("%c",ptr->data);     /* 列印节点内容       */
  59.       preorder(ptr->left);        /* 左子树             */
  60.       preorder(ptr->right);       /* 右子树             */
  61.    }
  62. }
  64. /* ---------------------------------------- */
  65. /*  表达式二叉树后序列印                    */
  66. /* ---------------------------------------- */
  67. void postorder(btree ptr)
  68. {
  69.    if ( ptr != NULL )             /* 终止条件           */
  70.    {
  71.       postorder(ptr->left);       /* 左子树             */
  72.       postorder(ptr->right);      /* 右子树             */
  73.       printf("%c",ptr->data);     /* 列印节点内容       */
  74.    }
  75. }
  77. /* ---------------------------------------- */
  78. /*  表达式二叉树后序计值                    */
  79. /* ---------------------------------------- */
  80. int cal(btree ptr)
  81. {
  82.    int operand1 = 0;              /* 前运算元变数       */
  83.    int operand2 = 0;              /* 后运算元变数       */
  85.    /* 终止条件 */
  86.    if ( ptr->left == NULL && ptr->right == NULL )
  87.       return ptr->data-48;
  88.    {
  89.       operand1 = cal(ptr->left);  /* 左子树             */
  90.       operand2 = cal(ptr->right); /* 右子树             */
  91.       return getvalue(ptr->data,operand1,operand2);
  92.    }
  93. }
  95. /* ---------------------------------------- */
  96. /*  计算二叉表达式的值                      */
  97. /* ---------------------------------------- */
  98. int getvalue(int op,int operand1,int operand2)
  99. {
  100.    switch ( (char) op )
  101.    {
  102.       case '*': return ( operand2 * operand1 );
  103.       case '/': return ( operand2 / operand1 );
  104.       case '+': return ( operand2 + operand1 );
  105.       case '-': return ( operand2 - operand1 );
  106.    }
  107. }
  109. /* ---------------------------------------- */
  110. /*  主程式: 建立表达式二叉树后计算结果.     */
  111. /* ---------------------------------------- */
  112. void main()
  113. {
  114.    btree root = NULL;             /* 表达式二叉树指标   */
  115.    int result;                    /* 结果变数           */
  117.    /* 表达式二叉树节点数据 */
  118.    int data[8] = { ' ', '+', '*', '*', '5',
  119.                    '6', '4', '3' };
  120.    root = createbtree(data,1);    /* 建立表达式二叉树   */
  121.    printf("中序表达式: ");
  122.    inorder(root);                 /* 中序列印二叉树     */
  123.    printf("n前序表达式: ");
  124.    preorder(root);                /* 前序列印二叉树     */
  125.    printf("n后序表达式: ");
  126.    postorder(root);               /* 后序列印二叉树     */
  127.    result = cal(root);            /* 计算结果           */
  128.    printf("n表达式结果是:%dn",result); /* 印出结果    */
  129. }