1. 实验内容简介
已知一个按先序序列输入的字符序列,如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树,最后求出叶子节点个数和二叉树深度。
2. 程序设计思路
首先先序输入创建二叉树,然后进行中序和后序遍历,之后是树的叶子节点数判断,最后是求二叉树的深度。每一小步之间除了顺序关系外没有联系,所以设计5个不同的算法函数即可。
3. 算法分析与设计
- 先序输入创建二叉树
对于二叉树的创建,最好的办法就是递归,对此我们设置每一层级的递归为输入数据,然后转向子树,在最终完成二叉树创建
void creattree(tree& t) {//先序创建二叉树
char c;
cin >> c;
if (',' == c)t = NULL;
else {
t = new treenode;
t->data = c;
creattree(t->left);
creattree(t->right);
}
}
- 中序和后序遍历
对于二叉树的操作,我们始终坚持递归是天的原则,其实思考一下会发现,二叉树遍历的规则始终是逐步节点判断,唯一不同的只是下一步的方向,中序遍历的方向是优先执行左子树,再根节点,再右子树,之后每一节点递归即可,后序遍历思路也是一样。
void midorder(tree t) {//中序遍历
if (t) {
midorder(t->left);
cout << t->data << " ";
midorder(t->right);
}
}
void postorder(tree t) {//后序遍历
if (t) {
postorder(t->left);
postorder(t->right);
cout << t->data << " ";
}
}
- 树的叶子节点数计算
对于树的叶子节点,我们只需要对叶子节点进行判断,即没有子树,接着我们使用递归,对于每一个没有子树的节点返回1,相加即可。
int tree_leaf(treenode* a) {//求树的叶子节点个数
if (a == NULL)return 0;
if (a->left == NULL && a->right == NULL)return 1;
return tree_leaf(a->left) + tree_leaf(a->right);
}
- 树的深度计算
对于树的深度,我们对每一个节点的左右子树深度进行判断,返回最大的子树深度,这样直到最后,就是根节点的深度。
int tree_depth(treenode * a) {//求树的深度
int deep_left, deep_right;
if (a == NULL)return 0;
else
{
deep_left = tree_depth(a->left);
deep_right = tree_depth(a->right);
return (deep_left > deep_right) ? deep_left + 1 : deep_right + 1;
}
}
4. 数据结构设计
本实验创建的节点如下
typedef struct node {
char data;
struct node* left, * right;//左右孩子指针
}treenode, * tree;
5. 系统实现(系统架构,操作系统运用,数据库运用等)
本实验未使用到系统实现。
6. 测试结果
示例输入
abc,,de,g,,f,,,
示例输出
cbegdfa cgefdba 3 5
输出正确,测试完成。
7. 源代码
#include <stdio.h>
#include<iostream>
#include <winsock2.h>
#include <time.h>
#include<string.h>
#include <string>
#include <windows.h>
#include <stdlib.h>
#include<math.h>
#include<string>
#include<cstdlib>
#include<cstdio>
#pragma comment (lib, "ws2_32.lib") //加载 ws2_32.dll
#pragma warning (disable: 4996)
#define MAX_SIZE 20
using namespace std;
typedef struct node {
char data;
struct node* left, * right;//左右孩子指针
}treenode, * tree;
void creattree(tree& t) {//先序创建二叉树
char c;
cin >> c;
if (',' == c)t = NULL;
else {
t = new treenode;
t->data = c;
creattree(t->left);
creattree(t->right);
}
}
void midorder(tree t) {//中序遍历
if (t) {
midorder(t->left);
cout << t->data << " ";
midorder(t->right);
}
}
void postorder(tree t) {//后序遍历
if (t) {
postorder(t->left);
postorder(t->right);
cout << t->data << " ";
}
}
int tree_depth(treenode * a) {//求树的深度
int deep_left, deep_right;
if (a == NULL)return 0;
else
{
deep_left = tree_depth(a->left);
deep_right = tree_depth(a->right);
return (deep_left > deep_right) ? deep_left + 1 : deep_right + 1;
}
}
int tree_leaf(treenode* a) {//求树的叶子节点个数
if (a == NULL)return 0;
if (a->left == NULL && a->right == NULL)return 1;
return tree_leaf(a->left) + tree_leaf(a->right);
}
int main()
{
tree t;
creattree(t);
midorder(t);
cout << endl;
postorder(t);
cout << endl;
cout << tree_leaf(t) << endl;
cout << tree_depth(t) << endl;
return 0;
}