二叉树的初步学习-小山坡

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