纯C++代码详解二叉树相关操作

2024-10-08 07:05:41

前言

大家好，今天给大家带来的是二叉树的相关操作，希望能够给大家带来帮助。

二叉树的概念

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树的相关术语

①节点：包含一个数据元素及若干指向子树分支的信息。

②节点的度：一个节点拥有子树的数目称为节点的度。

③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。

④分支节点：也称为非终端节点，度不为零的节点称为非终端节点。

⑤树的度：树中所有节点的度的最大值。

⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层。

⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。

二叉树的构造

//构造二叉树
typedef struct Binode
{
    //数据域
    char data;
    //定义左孩子和右孩子
    struct Binode*lchid, *rchid;
}Binode, *StrBinode;

创建二叉树

//先序遍历创建二叉树
void creatBinode(StrBinode&T)
{
    cin >> ch;
    if (ch == '#')
    {
        //如果输入是#的话就说明根结点就是叶子结点
        //就没必要再去进行开辟一个二叉树空间
        T = NULL;
    }
    else
    {
        T = new Binode;
        T->data = ch;
        creatBinode(T->lchid);
        creatBinode(T->rchid);
    }
}

先序遍历二叉树

//先序遍历二叉树
void visitBinode(StrBinode&T)
{
    if (T!=NULL)
    {
        cout << T->data << " ";
        visitBinode(T->lchid);
        visitBinode(T->rchid);
    }
    if(T==NULL)
    {
        cout << "#" << " ";
    }
}

中序遍历二叉树

//中序遍历二叉树
void MidvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        cout << T->data << " ";
        visitBinode(T->rchid);
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}

后序遍历二叉树

//后序遍历二叉树
void BackvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        visitBinode(T->rchid);
        cout << T->data << " ";
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}

层次遍历二叉树

//二叉树的层次遍历
void Levelorder(StrBinode&HT)
{
    StrBinode T;
    T = new Binode;
    //创建一个队列qu
    queue<StrBinode> qu;
    //将根结点的指针压入队列
    qu.push(HT);
    //当队列不为空的时候就继续进行循环
    while (!qu.empty())
    {
        //让T里面存放队列中第一个元素的值
        T = qu.front();
        //C++自带的队列出队的话是删除值不返回值
        qu.pop();
        //访问出队元素的值
        cout << T->data << " ";
        //当该节点左孩子不为空的时候就让左孩子入队
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //当该节点右孩子不为空的时候就让左孩子入队
        if (T->rchid != NULL)
        {
            qu.push(T->rchid);
        }
    }

}

二叉树的深度

//二叉树的深度
int deep(StrBinode&T)
{
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        int m = deep(T->lchid);
        int n = deep(T->rchid);
        if (m > n)
        {
            return (m + 1);
        }
        else
        {
            return (n + 1);
        }
    }
}

二叉树的叶子结点数

//求二叉树的叶子结点
int leaf(StrBinode&T)
{
    //如果是空树
    if (T == NULL)
    {
        //返回0
        return 0;
    }
    //如果是叶子结点
    if (T->lchid == NULL && T->rchid == NULL)
    {
        //返回1
        return 1;
    }
    return leaf(T->lchid) + leaf(T->rchid);
}

二叉树的结点数

//求二叉树的结点数
int Nodecount(StrBinode&T)
{
    //如果是根结点没有数据
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
    }
}

整体代码

#include<iostream>
#include<queue>
using namespace std;
char ch = 0;

//构造二叉树
typedef struct Binode
{
    //数据域
    char data;
    //定义左孩子和右孩子
    struct Binode*lchid, *rchid;
}Binode, *StrBinode;

//先序遍历创建二叉树
void creatBinode(StrBinode&T)
{
    cin >> ch;
    if (ch == '#')
    {
        //如果输入是#的话就说明根结点就是叶子结点
        //就没必要再去进行开辟一个二叉树空间
        T = NULL;
    }
    else
    {
        T = new Binode;
        T->data = ch;
        creatBinode(T->lchid);
        creatBinode(T->rchid);
    }
}

//先序遍历二叉树
void visitBinode(StrBinode&T)
{
    if (T!=NULL)
    {
        cout << T->data << " ";
        visitBinode(T->lchid);
        visitBinode(T->rchid);
    }
    if(T==NULL)
    {
        cout << "#" << " ";
    }
}

//中序遍历二叉树
void MidvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        cout << T->data << " ";
        visitBinode(T->rchid);
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}

//后序遍历二叉树
void BackvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        visitBinode(T->rchid);
        cout << T->data << " ";
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}

//二叉树的层次遍历
void Levelorder(StrBinode&HT)
{
    StrBinode T;
    T = new Binode;
    //创建一个队列qu
    queue<StrBinode> qu;
    //将根结点的指针压入队列
    qu.push(HT);
    //当队列不为空的时候就继续进行循环
    while (!qu.empty())
    {
        //让T里面存放队列中第一个元素的值
        T = qu.front();
        //C++自带的队列出队的话是删除值不返回值
        qu.pop();
        //访问出队元素的值
        cout << T->data << " ";
        //当该节点左孩子不为空的时候就让左孩子入队
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //当该节点右孩子不为空的时候就让左孩子入队
        if (T->rchid != NULL)
        {
            qu.push(T->rchid);
        }
    }

}

//二叉树的深度
int deep(StrBinode&T)
{
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        int m = deep(T->lchid);
        int n = deep(T->rchid);
        if (m > n)
        {
            return (m + 1);
        }
        else
        {
            return (n + 1);
        }
    }
}

//求二叉树的叶子结点
int leaf(StrBinode&T)
{
    //如果是空树
    if (T == NULL)
    {
        //返回0
        return 0;
    }
    //如果是叶子结点
    if (T->lchid == NULL && T->rchid == NULL)
    {
        //返回1
        return 1;
    }
    return leaf(T->lchid) + leaf(T->rchid);
}

//求二叉树的结点数
int Nodecount(StrBinode&T)
{
    //如果是根结点没有数据
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
    }
}

//菜单
void menu()
{
    cout << "\t\t\t******************************************************************" << endl;
    cout << "\t\t\t****************  1.输入-1  退出程序           *******************" << endl;
    cout << "\t\t\t****************  2.输入1   初始化二叉树       *******************" << endl;
    cout << "\t\t\t****************  3.输入2   对二叉树先序遍历   *******************" << endl;
    cout << "\t\t\t****************  4.输入3   对二叉树中序遍历   *******************" << endl;
    cout << "\t\t\t****************  5.输入4   对二叉树后序遍历   *******************" << endl;
    cout << "\t\t\t****************  6.输入5   对二叉树层次遍历   *******************" << endl;
    cout << "\t\t\t****************  7.输入6   二叉树深度         *******************" << endl;
    cout << "\t\t\t****************  8.输入7   二叉树叶子结点数   *******************" << endl;
    cout << "\t\t\t****************  9.输入8   二叉树的结点数     *******************" << endl;
    cout << "\t\t\t******************************************************************" << endl;
}

int main()
{
    int n = 0;
    StrBinode T;
    menu();
    while (cin >> n)
    {
        if (n < 0)
        {
            break;
        }
        switch (n)
        {
        case 1:
            //初始化二叉树
            cout << "请输入值对二叉树进行初始化" << endl;
            creatBinode(T);
            cout << "初始化完成" << endl;
            break;
        case 2:
            //先序遍历
            cout << "先序遍历的结果为" << endl;
            visitBinode(T);
            cout << "先序遍历结束" << endl;
            break;
        case 3:
            //中序遍历
            cout << "中序遍历的结果为" << endl;
            MidvisitBinode(T);
            cout << "中序遍历结束" << endl;
            break;
        case 4:
            //后序遍历
            cout << "后序遍历的结果为" << endl;
            BackvisitBinode(T);
            cout << "后序遍历结束" << endl;
            break;
        case 5:
            //层次遍历
            cout << "层次遍历的结果为" << endl;
            Levelorder(T);
            cout << "层次遍历结束" << endl;
            break;
        case 6:
            cout << "二叉树的深度为：";
            cout << deep(T) << endl;
            break;
        case 7:
            cout << "二叉树的叶子结点数为：";
            cout << leaf(T) << endl;
            break;
        case 8:
            cout << "二叉树的结点数为；";
            cout << Nodecount(T) << endl;
            break;
        default:
            cout << "您的输入有误，请重新输入" << endl;
            break;
        }
    }
    return 0;
}

结果展示

以上就是纯C++代码详解二叉树相关操作的详细内容，更多关于C++二叉树的资料请关注我们其它相关文章！

C++ 数据结构完全二叉树的判断

C++ 数据结构完全二叉树的判断完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树.完全二叉树由满二叉树而引起来的.对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树. 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树. 完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二
C++二叉树结构的建立与基本操作

准备数据定义二叉树结构操作中需要用到的变量及数据等. 复制代码代码如下: #define MAXLEN 20 //最大长度typedef char DATA; //定义元素类型struct CBTType //定义二叉树结点类型 { DATA data; //元素数据 CBTType * left; //左子树结点指针 CBTType * right; //右子树结点指针 }; 定义二叉树结构数据元素的类型DA
C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree
C++实现二叉树基本操作详解

树是一种重要的非线性数据结构,二叉树是树型结构的一种重要类型.本学年论文介绍了二叉树的定义,二叉树的存储结构,二叉树的相关术语,以此引入二叉树这一概念,为展开二叉树的基本操作做好理论铺垫.二叉树的基本操作主要包含以下几个模块:二叉树的遍历方法,计算二叉树的结点个数,计算二叉树的叶子结点个数,二叉树深度的求解等内容. 前序遍历(递归&非递归) 访问根节点前序访问左子树前序访问右子树 //前序非递归 void PrevOrder() { stack<Node*> s; Node *cu
C++数据结构之搜索二叉树的实现

目录零.前言 1.概念 2.作用 3.迭代实现 (1)查找 (2)插入 (3)删除 4.递归实现 (1)查找 (2)插入 (3)删除 5.key/value模型的应用 (1)对应查找 (2)判断出现次数 6.总结零.前言了解搜索二叉树是为了STL中的map和set做铺垫,我们所熟知的AVL树和平衡搜索二叉树也需要搜索二叉树的基础,本文就来建立一棵搜索二叉树. 1.概念搜索二叉树又称为二叉排序树,它或者是一棵空树,或者具有如下性质: 1.若其左子树不为空,则左子树上所有节点的值都小于根节点
C++ 详解数据结构中的搜索二叉树

目录定义查找某个元素构造搜索二叉树往搜索二叉树中插入元素搜索二叉树删除节点定义搜索二叉树,也称有序二叉树,排序二叉树,是指一棵空树或者具有下列性质的二叉树: 1.若任意节点的左子树不空,则左子树上的所有节点的值均小于它的根节点的值 2.若任意节点的右子树不空,则右子树上的所有节点的值均大于它的根节点的值 3.任意节点的左右子树也称为二叉查找树. 4.没有键值相等的节点. 5.搜索二叉树中序遍历为有序数组. 结构代码实现 template<class K> struct BSTre
纯C++代码详解二叉树相关操作

目录前言二叉树的概念二叉树的相关术语相关操作菜单二叉树的构造创建二叉树先序遍历二叉树中序遍历二叉树后序遍历二叉树层次遍历二叉树二叉树的深度二叉树的叶子结点数二叉树的结点数整体代码结果展示前言大家好,今天给大家带来的是二叉树的相关操作,希望能够给大家带来帮助. 二叉树的概念二叉树(Binary tree)是树形结构的一个重要类型.许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉
jQuery Ajax 全局调用封装实例代码详解

有一种情况:全站都要用异步方式来调用数据,提交数据,那么你每次操作都会要$.ajax({.....}) 写重复的方法和代码,冗余太大, 也浪费时间,虽说你有代码自动提示补全,但真的不优雅,身为前端极客,是不能允许的! [嘿嘿!虽说我现在基本不用jquery了 ,不过异步概念是永远要用的,就帮助下新人] jQuery Ajax通用js封装第一步:引入jQuery库 <script type="text/javascript" src="/js/jquery.mi
BootStrap实现树形目录组件代码详解

需求描述产品添加页面,需要选择车型.在bootStrap的modal上弹出子modal来使用. 车型一共有4级目录.要使用目录树. 然后分活动和商品两种,需要能够通过不通参数来调用该组件. 车型品牌要使用字母导航. 技术实现数据都是后端传json过来,我们ajax获取然后操作. 由于车型总数据有几万条以上,不可能一次性请求过来.这里我们使用异步的方式,每点击一次目录节点,加载它的下一级. 这里我们用两个参数来控制活动和商品的不同加载._showPrice和opened 后端传过来的第一级数据
JavaScript知识点总结(十六)之Javascript闭包（Closure）代码详解

闭包(closure)是Javascript语言的一个难点,也是它的特色,很多高级应用都要依靠闭包实现.很早就接触过闭包这个概念了,但是一直糊里糊涂的,没有能够弄明白JavaScript的闭包到底是什么,有什么用,今天在网上看到了一篇讲JavaScript闭包的文章(原文链接),讲得非常好,这下算是彻底明白了JavaScript的闭包到底是个神马东东以及闭包的用途了,在此写出来和大家分享一下,希望不理解JavaScript闭包的朋友们看了之后能够理解闭包!以下内容大部分是来自原文,我在原文的基础
ListView点击Item展开菜单实现代码详解

一.概述 ListView点击item显示菜单是要实现这样的效果: 需要实现的逻辑如下: 1)点击一个普通item,展开当前菜单,同时关闭其他菜单 2)点击一个已展开的菜单,隐藏当前菜单 3)将展开菜单滑到listview之外,再滑动回来,展开菜单状态不变 4)点击菜单中的按钮,能够根据不同item进行不同的处理二.实现思路 1.UI布局上,对于这种每个listitem都包含动态显示菜单的场景,可以直接在listitem的xml布局里就包含两部分元素:item本身以及展开菜单点击item的时
java编程无向图结构的存储及DFS操作代码详解

图的概念图是算法中是树的拓展,树是从上向下的数据结构,结点都有一个父结点(根结点除外),从上向下排列.而图没有了父子结点的概念,图中的结点都是平等关系,结果更加复杂. 无向图有向图图G=(V,E),其中V代表顶点Vertex,E代表边edge,一条边就是一个定点对(u,v),其中(u,v)∈V. 这两天遇到一个关于图的算法,在网上找了很久没有找到java版的关于数据结构中图的存储及其
Hibernate中Session增删改查操作代码详解

把三状态转换图放在这,方便分析方法的作用: 1.Session的save()方法 Session是Hibernate所有接口中最重要的接口,提供了对数据保存,更新,查询和删除的方法. Session的save()方法可以使临时态或游离态转换为持久态.例如,保存一个Customer对象: SessionFactory sessionFactory; Configuration configuration = new Configuration().configure(); sessionFacto
python操作列表的函数使用代码详解

python的列表很重要,学习到后面你会发现使用的地方真的太多了.最近在写一些小项目时经常用到列表,有时其中的方法还会忘哎! 所以为了复习写下了这篇博客,大家也可以来学习一下,应该比较全面和详细了列表(list): 用来存放相同或者不同元素(字符)用逗号隔开的一个存储方式. list我个人认为最重要的有一点大家可能都容易忽略那就是复制列表,这点文章最后来讲解定义三个列表的样例 lis = [1, 2, 3, 4, 5, 6] lis = ['a', 'b', 'c', 'd'] lis =
java使用FFmpeg合成视频和音频并获取视频中的音频等操作(实例代码详解)

FFmpeg是一套可以用来记录.转换数字音频.视频,并能将其转化为流的开源计算机程序. ffmpeg命令参数如下: 通用选项 -L license -h 帮助 -fromats 显示可用的格式,编解码的,协议的... -f fmt 强迫采用格式fmt -I filename 输入文件 -y 覆盖输出文件 -t duration 设置纪录时间 hh:mm:ss[.xxx]格式的记录时间也支持 -ss position 搜索到指定的时间 [-]hh:mm:ss[.xxx]的格式也支持 -title
android 限制某个操作每天只能操作指定的次数(示例代码详解)

最近有个需求,要求启动页的拦截页每天只能显示3次,超过三次就显示别的页面,然后到第二天才可以再次显示,利用SharePreferences保存天数和每天的次数,大概是思路是:判断如果是同一天,就去拿保存的次数,当次数小于3才执弹出拦截页,然后,每次弹出,次数就加1,并且保存次数和当天的时间:如果不是同一天,就把次数赋值为1,并且把当天赋值给最后访问的时间,然后保存当前的次数.具体实现如下: package com.example.demo1.test; import android.suppo