《假设二叉树中结点值互不相同,输入一给定值,查找给定值对应的结点是否存在》由会员分享，可在线阅读，更多相关《假设二叉树中结点值互不相同,输入一给定值,查找给定值对应的结点是否存在（7页珍藏版）》请在金锄头文库上搜索。
1、假设二叉树中结点值互不相同假设二叉树中结点值互不相同, ,输入一给定值输入一给定值, ,查找给定值对应的结查找给定值对应的结点是否存在点是否存在实训四：利用二叉树的遍历计算表达式的值 实训 4.1 二叉树的操作：实训目的要求：1了解建立二叉树的方法。2掌握在二叉树中寻找结点的方法。实训内容：设二叉树中结点值互不相同，即各值具有惟一性。输入一给定值，确定给定值对应的结点是否在二叉树中存在。实训 4.2 树的应用 实训目的要求：1掌握树可以处理各种层数关系的方法。2使用表达式二叉树，可以很容易解决表达式转换问题。3学会利用二叉树遍历计算表达式的值。实训内容：将 5*6+4*3 表达式二叉树存入数组
2、，然后用递归方法创建表达式二叉树，输出表达式二叉树三种遍历的结果，并计算表达式的值。实训参考程序： 实训 4.1 参考程序：typedef struct node1 char data;struct node1 *lchild, *rchild;BT;#include stdio.h#include stdlib.hBT * createbt( ) BT *q;BT *s30;int j,i,x;printf(“creat bintreenn“);printf(“i,x = “);scanf(“%d,%c“,while(i != 0 /*建立一个新结点 q*/q-data = x; q-lch
3、ild = NULL; q-rchild = NULL;si = q; /*q 新结点地址存入 s 指针数组中*/if(i != 1) /*i = 1，对应的结点是根结点*/j = i / 2; /*求双亲结点的编号 j*/if(i % 2 = = 0) sj-lchild = q; /*q 结点编号为偶数则挂在双亲结点 j 的左边*/else sj-rchild = q; /*q 结点编号为奇数则挂在双亲结点 j 的右边*/printf(“i,x = “);scanf(“%d,%c“,return s1; /*返回根结点地址*/BT *search_ch(BT *cur, char x)/*
4、先序查找*/BT *temp;if(cur= =NULL) return NULL;if(x = = cur-data) return cur;temp = search_ch(cur-lchild,x);if (temp != NULL) return temp; else return search_ch(cur-rchild,x);main()BT *t, *p;char ch;int i;t=createbt(); i = 1;while(i)printf(“Enter search data： “); scanf(“%c“,p = search_ch(t,ch);if(p = = N
5、ULL) printf(“no node nn“);else printf(“node existnn“);printf(“ncontinue?(Contumer press 1，Over press 0): n“);scanf(“%d“,printf(“n“);该程序运行结果如下（加下划线部分为用户输入）：create bintree:i,x=1,ai,x=2,bi,x=3,ci,x=4,di,x=5,ei,x=10,fi,x=11,qi,x=23,hi,x=1,$enter search data:enode existcontinue? (Contumer press 1，Over pr
6、ess 0):0实训 4.2 参考程序#includestdlib.hstruct tree /*二叉树的结构声明*/char data; /*结点数据*/struct tree*left; /*指向左子树的指针*/struct tree*right; /*指向右子树的指针*/;typedef struct tree TREENODE; /*数的新结构类型*/typedef TREENODE*BTREE;BTREE createbtree（int*data，int pos） /*创建表达式二叉树*/BTREE newnode; /*新结点指针*/if（datapos=0|pos7） /*终止条
7、件*/return NULL;elsenewnode=（BTREE）malloc（sizeof（TREENODE） ）; /*创建新结点内存*/newnode-data=datapos; /*创建结点内容*/newnode-left=createbtree（data，2*pos）; /*创建左子树的递归调用*/newnode-right=createbtree（data，2*pos+1）; /*创建右子树的递归调用*/return newnode;void inorder（BTREE ptr） /*表达式二叉树中序输出*/ if（ptr!=NULL） /*终止条件*/inorder（ptr-l
8、eft）; /*左子树*/printf（%c，ptr-data）; /*输出结点内容*/inorder（ptr-right）; /*右子树*/void preorder（BTREE ptr） /*表达式二叉树先序输出*/ if（ptr!=NULL） /*终止条件*/printf（%c，ptr-data）; /*输出结点内容*/preorder（ptr-left）; /*左子树*/preorder（ptr-right）; /*右子树*/void postorder（BTREE ptr） /*表达式二叉树后序输出*/ if（ptr!=NULL） /*终止条件*/postorder（ptr-left
9、）; /*左子树*/postorder（ptr-right）; /*右子树*/printf（%c，ptr-data）; /*输出结点内容*/int cal（BTREE ptr） /*表达式二叉树后序计值*/ int operand1=0; /*前操作数变量*/int operand2=0; /*后操作数变量*/if（ptr-left=NULLoperand1=cal（ptr-left）; /*左子树*/operand2=cal（ptr-right）; /*右子树*/return getvalue（ptr-data，operand1，operand2）;int getvalue（int op，i
10、nt operand1，int operand2） /*计算二叉表达式的值*/switch（char）op）case*:return（operand2*operand1）; case.:return（operand2.operand1）;case+:return（operand2+operand1）;case-:return（operand2-operand1）;void main（） /*主程序:创建表达式二叉树后计算结果*/BTREE root=NULL; /*表达式二叉树指针*/int result; /*结果变量*/int data8=，+，*，*，5，6，4，3;/*表达式二叉树结点
11、数据*/root=createbtree（data，1）; /*调用创建表达式二叉树函数*/printf（中序表达式:）;inorder（root）; /*调用中序输出二叉树函数*/printf（n 先序表达式:）;preorder（root）; /*调用先序输出二叉树函数*/printf（n 后序表达式:）;postorder（root）; /*调用后序输出二叉树函数*/result=cal（root）; /*调用计算表达式值函数*/printf（n 表达式结果是:%dn，result）; /*输出结果*/ 该程序运行结果如下：中序表达式：5*6+4*3先序表达式：+*56*43后序表达式：56*43*+表达式结果是：42
