c语言实现二叉树操作用栈实现算术表达式求值 - CSDN文库

算数表达式

需积分: 50 134 浏览量更新于2023-03-16 6 收藏 115KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

沈阳理工大学课程设计专用纸

目录

题目一.二叉树操作（1）二.算术表达式求..........................................................................................................1

一、课程设计的目的...........................................................................................................................................1

二、课程设计的内容和要求...............................................................................................................................1

三、题目一设计过程...........................................................................................................................................1

四、题目二设计过程...........................................................................................................................................5

五、设计总结.....................................................................................................................................................13

六、参考文献.....................................................................................................................................................13

沈阳理工大学

沈阳理工大学课程设计专用纸

No. 2

现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取

结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍

历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉

树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结

点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！

由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它

的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后

返回其中大的那个值加一，则求出数的高度。这里用递归实现！

2、算法描述

main ( )（主函数）

先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树

的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。

void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造

二叉树）

根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中

序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序

列为左子树, 后边的序列为右子树。设根前边有 n 个元素，则又有, 在前序序列中，

紧跟着根(root)的 n 个元素序列(即 pre[1...n]) 为左子树, 在后边的为右子树，而构造

左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为 pre[1...n]), 中序

序列为 in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！

int Depth(BiTree T)（求树的深度）

当所给的参数 T 是 NULL 时，返回 0。说明这个树只有一个叶子节点深度为

0，当所给的参数不是 NULL 时，函数调用自己看看这个参数的左分支是不是

NULL，如果不是继续调用自己看看左分支的左分支是不是 NULL，直到最后一个

的左分支是 NULL。然后看与最后一个左分支并列的右分支是不是 NULL，不是

的话自动调用自己，直到是 NULL。同理求出右分支，然后左分支深度和右分支

深度比较，返回值大的作为深度。

3、源代码

#include<stdio.h>

#include<malloc.h>

typedef struct Node

{

char data;

struct Node *lchild;

struct Node *rchild;

}*BiTree,BitNode;

void InitBitTree(BiTree *T);//初始化一棵树

沈阳理工大学

剩余13页未读，继续阅读

liangjiang1989

粉丝: 0
资源: 5

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈