二叉树的初步学习

发布于 2020-03-31  111 次阅读


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;
}

山下闲人漫步,山上泉水熙熙。 山外庸人自扰,山里野花灿灿。