数据结构课内实验1
本文最后更新于 412 天前,其中的信息可能已经有所发展或是发生改变。

对任意给定的二叉树完成下列操作:
               (1)根据输入的序列,建立二叉链表存储结构;
               (2)输出该二叉树的先序、中序、后序遍历结果(递归算法);
               (3)先序遍历二叉树(非递归算法);
               (4)借助队列实现二叉树的层次遍历;
               (5)求二叉树的高度;
               (6)求二叉树叶子结点个数;
               (7)将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数。
/*
 * @Author: Vastsea(lyx8851@qq.com)
 * @Date: 2023-05-26 15:29:24
 * @LastEditors: Vastsea(lyx8851@qq.com)
 * @LastEditTime: 2023-05-31 11:52:45
 * @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_1\树和二叉树.cpp
 * @Description: 对任意给定的二叉树完成下列操作:
            ok    (1)根据输入的序列,建立二叉链表存储结构;
            ok    (2)输出该二叉树的先序、中序、后序遍历结果(递归算法);
            ok    (3)先序遍历二叉树(非递归算法);
            ok    (4)借助队列实现二叉树的层次遍历;
            ok    (5)求二叉树的高度;
            ok    (6)求二叉树叶子结点个数;
            ok    (7)将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数。
 * Link:https://59888888.xyz/
 * Phone:18893558104
 */
#include <iostream>
#include <queue>
using namespace std;

typedef int ElemType;

struct node
{
    ElemType data;
    struct node *lchild = NULL;
    struct node *rchild = NULL;
};

typedef node *BTree;

/**
 * @description: 根据已有数组构建完全二叉树
 * @param {BTree} &root 当前操作节点
 * @param {ElemType} source 来源数据数组
 * @param {int} numOfSource Source数组的长度
 * @param {int} nowNum 现在在插入的是第几个元素
 * @return {*}
 */
void Structure(BTree &root, ElemType source[], int numOfSource, int nowNum = 1) // 根据数组构造
{
    if (nowNum > numOfSource)
    {
        return;
    }
    if (!root) // 往下看,只要root空&&nowNum合法就插入
    {
        root = new node;
        root->data = source[nowNum - 1];
    }
    Structure(root->lchild, source, numOfSource, nowNum * 2);
    Structure(root->rchild, source, numOfSource, nowNum * 2 + 1);
}

void Print(BTree T, int level = 0, int lr = 0) // 打印二叉树
{
    if (!T)
    {
        return;
    }
    Print(T->rchild, level + 1, 2);
    for (int i = 0; i < level; i++)
    {
        cout << "          ";
    }
    switch (lr)
    {
    case 1:
    {
        cout << "\\-";
        break;
    }
    case 2:
    {
        cout << "/-";
        break;
    }
    default:
        break;
    }
    cout << T->data << endl;
    Print(T->lchild, level + 1, 1); // 打印左子树,并将层次加1
}

void PreOrder(BTree &root) // 先序遍历
{
    if (!root)
    {
        return;
    }
    else
    {
        cout << root->data << " ";
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

void MidOrder(BTree &root) // 中序遍历
{
    if (!root)
    {
        return;
    }
    else
    {
        MidOrder(root->lchild);
        cout << root->data << " ";
        MidOrder(root->rchild);
    }
}

void PostOrder(BTree &root) // 后序遍历
{
    if (!root)
    {
        return;
    }
    else
    {
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        cout << root->data << " ";
    }
}

void PreOrder_NoRecursion(BTree &root) // 先序遍历_非递归
{
    node *p = root;
    node *s[500];
    int top = -1;
    while (p || top != -1)
    {
        while (p)
        {
            cout << p->data << " ";
            s[++top] = p;
            p = p->lchild;
        }
        if (top != -1)
        {
            p = s[top--];
            p = p->rchild;
        }
    }
}

void LevelOrder(BTree &root) // 层序遍历
{
    queue<node *> q;
    if (root)
    {
        q.push(root);
    }
    while (!q.empty())
    {
        node *n = q.front();
        cout << n->data << " ";
        if (n->lchild != NULL)
        {
            q.push(n->lchild);
        }
        if (n->rchild != NULL)
        {
            q.push(n->rchild);
        }
        q.pop();
    }
}

int Height(BTree &root) // 求高度
{
    if (!root)
    {
        return 0;
    }
    else
    {
        int HeightL = Height(root->lchild);
        int HeightR = Height(root->rchild);
        return max(HeightL, HeightR) + 1;
    }
}

int leafNodeNum = 0;
void CountleafNode(BTree &root) // 求叶子节点个数
{
    if (!root)
    {
        return;
    }
    if (!(root->lchild) && !(root->rchild))
    {
        leafNodeNum++;
    }
    else
    {
        CountleafNode(root->lchild);
        CountleafNode(root->rchild);
    }
}

int TreeleafNodeNum = 0;
void CountTreeleafNode(BTree &root)//求二叉链表视为树或森林的孩子兄弟链表后的叶子节点个数
{
    if (!root)
    {
        return;
    }
    if (!root->lchild)
    {
        TreeleafNodeNum++;
    }
    CountTreeleafNode(root->lchild);
    CountTreeleafNode(root->rchild);
}

int main()
{
    BTree T1 = NULL;
    ElemType tes[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    cout << "根据已有数组{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}构建完全二叉树:" << endl;
    Structure(T1, tes, 20);
    Print(T1);

    cout << endl
         << "先序遍历序列为:";
    PreOrder(T1);
    cout << endl
         << endl
         << "中序遍历序列为:";
    MidOrder(T1);
    cout << endl
         << endl
         << "后序遍历序列为:";
    PostOrder(T1);
    cout << endl
         << endl;

    cout << "先序遍历(非递归)结果为:";
    PreOrder_NoRecursion(T1);
    cout << endl
         << endl;

    cout << "层序遍历的结果为:";
    LevelOrder(T1);
    cout << endl
         << endl;

    cout << "该二叉树的高度为:" << Height(T1) << endl
         << endl;

    CountleafNode(T1);
    cout << "该二叉树的叶子节点个数为:" << leafNodeNum << endl
         << endl;

    CountTreeleafNode(T1);
    cout << "将二叉链表视为树或森林的孩子兄弟链表后的叶子节点个数为:" << TreeleafNodeNum << endl
         << endl;

    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇