文章目录

实验二 树1. 实验目的2. 实验内容3. 实验要求4. 实验过程(1) 问题描述(2) 数据结构与算法设计(3) 程序实现(4) 实验结果(5) 实验总结

实验二 树

——还原二叉树

1. 实验目的

熟练掌握二叉树存储结构、遍历及应用。

2. 实验内容

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

3. 实验要求

(1) 输入格式说明： 输入首先给出正整数N（<=50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。 (2) 输出格式说明： 输出为一个整数，即该二叉树的高度。 (3) 样例输入与输出：

序号输入输出19ABDFGHIECFDHGIBEAC5215cdefghijklmnxyz cdefghijklmnxyz1537Abcdefg gfedcbA741aa1

4. 实验过程

(1) 问题描述

(问题分析及功能描述)

(2) 数据结构与算法设计

(逻辑结构分析+存储结构设计+关键算法思路+伪代码或流程图)

(3) 程序实现

(函数说明+函数之间的调用关系+关键算法的实现代码)

#include <stdio.h> #include <stdlib.h> typedef struct node { char data;//数据域 struct node* lChild;//左孩子 struct node* rChild;//右孩子 }BiNode,*BiTree; BiTree CreatTree(char *in, char *pre, int inStrt, int inEnd); //利用中序序列in和前序序列pre递归构造一棵大小为n的二叉树,inStart和inEnd的初始值应当为0和n-1 int search(char arr[], int start, int end, char value); //在数组 arr[start...end] 中查找值 value的下标 BiNode* newNode(char data); /* * 辅助函数 * 利用给定的数据域 data 分配一个新结点，该节点的 left 和 right 域均为 NULL * 并返回指向该结点的指针 */ int Depth (BiTree T);//返回二叉树深度 int main() { int n; //声明变量存储树的节点个数. scanf("%d",&n); char pre[n+1],in[n+1]; //声明字符数组分别存储先序和中序遍历序列 scanf("%s",pre); //读入先序序列 scanf("%s",in); //读入中序序列 BiTree tree = CreatTree(in, pre, 0, n-1);//建树 printf("%d",Depth(tree)); //输出树的高度 return 0; } int preIndex = 0; //前序序列索引 BiTree CreatTree(char *in, char *pre, int inStrt, int inEnd) { if (inStrt > inEnd) return NULL; // 利用索引 preIndex 从前序序列中取出一个元素，并利用此元素创建一个二叉树结点 // 最后索引值 preIndex 加 1 BiNode* tNode = newNode(pre[preIndex++]); // 如果此结点没有孩子则返回 if (inStrt == inEnd) return tNode; //否则在中序序列中找到此元素的索引 int inIndex = search(in, inStrt, inEnd, tNode->data); // 利用中序索引构造左子树与右子树 tNode->lChild = CreatTree(in, pre, inStrt, inIndex -1); tNode->rChild = CreatTree(in, pre, inIndex +1, inEnd); return tNode; } int search(char arr[], int start, int end, char value) { int i; for (i = start; i <= end; i++) { if (arr[i] == value) return i; } } BiNode* newNode(char data) { BiTree node = (BiTree)malloc(sizeof(BiNode)); node->data = data; node->lChild = NULL; node->rChild = NULL; return node; } int Depth (BiTree T){ int depth,lDepth,rDepth; if ( !T ) depth = 0; else { lDepth = Depth( T->lChild ); rDepth= Depth( T->rChild ); depth = (lDepth>rDepth?lDepth:rDepth)+1; } return depth; }

(4) 实验结果

(运行截图+结果分析描述+遇到的问题和解决办法等)

(5) 实验总结

(实验体会、学习收获、过程总结等) 以下再给出一种无需建树的算法:

#include <stdio.h> int max(int a,int b){ return a>b?a:b; } int Depth(char* pre,char* in,int n);//求给定先序和中序序列对应的树的高度 int main() { int n;//声明变量存储树的节点个数. scanf("%d",&n); char pre[n+1],in[n+1]; //声明字符数组分别存储先序和中序遍历序列 scanf("%s",pre);//读入先序序列 scanf("%s",in);//读入中序序列 printf("%d",Depth(pre,in,n));//输出先序和中序序列对应的树的高度 return 0; } int Depth(char* pre,char* in,int n) //pre:先序序列; in:中序序列; n:节点个数; { int left,right,i; if(n == 0) //若没有结点，为空树 { return 0; } for(i = 0; i < n; i++) { if(in[i] == pre[0]) //找到根结点在中序的位置 { break; } } left = Depth(pre+1,in,i); //左子树的深度 right = Depth(pre+i+1,in+i+1,n-i-1); //右子树的深度 return max(left,right)+1; //返回左右子树深度的较大值中的较大值+根结点 }