首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >树与二叉树

树与二叉树

作者头像
小王不头秃
发布于 2024-06-19 06:44:01
发布于 2024-06-19 06:44:01
21500
代码可运行
举报
运行总次数:0
代码可运行

定义:

树有n个节点,当n=0时,该树是空树,当n>=1时,除根结点的左右子树节点各不相同,并且每一个子树又可以当作一个树,依次类推到最后。

存储方式:

数组存储: 存储树必须要存储各个节点之间的关系,为了存储这种关系,需要定义一种结构体

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
struct Node
{
int value
int parent,firstchild;    //此种定义方式方便节点寻找子节点,双亲节点
}


struct Node
{
int value
int parent,right;    //此种定义方式方便寻找双亲还有兄弟
}

用一维数组将各个节点存储在数组中。 链表存储:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
struct Node
{
int data;
Node *child1,.....child;//存储子节点
}

这种方式存储节点的方式较为麻烦与浪费空间,并且每一个节点的子节点数量不同,选用最多的子节点数来设置子节点数目会导致空间的浪费,变换的方式会很复杂。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
struct Node
{
int data;
Node *child,Node *right;   //存储第一个子节点与右兄弟节点
} 

二叉树

定义

二叉树也是树的一种,二叉树中的两个指针是左子节点与右子节点

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
struct Node
{
int data;
Node *rchild,*lchild;  //存储节点的右子节点与左子节点
}
遍历方式

先序遍历: 先遍历根节点,在遍历左子树,最终遍历右子树 后序遍历: 先遍历左子树,在遍历右子树,最终遍历根节点 中序遍历: 先遍历左子树,然后遍历根节点,最终遍历右子树

通常实现二叉树遍历可以可以使用递归的思想,这种遍历方式的好处是代码简洁,代码数量少,但是缺点是需要占用大量的内存,执行速度慢。 实现代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void  preprint(Node *t)
{
if (t)
{
return;
}
cout<<t->data;
preprint(t—>lchild);
preprint(t—>rchild);
}

上述代码实现的是前序遍历,而实现中序遍历与后序遍历仅仅是将cout<data;改变一下位置即可。

为了减少遍历的时间,还可以对二叉树进行非递归的遍历 前序遍历代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 stack<Tree*> all;
       all.push(first);
       cout<<first->value;
       while(1)
       {
         if(all.top()->l)
         {
             all.push(all.top()->l);
                cout<<all.top()->value;
         }
         else{
            break;
         }
       }
       while(!all.empty())
       {
           if(all.top()->r)
           {
               all.push(all.top()->r);
               cout<<all.top()->value;
               break;
           }
           else{
           all.pop();
           }
       }

中序遍历,后序遍历同样也可以使用栈方式进行遍历。

总结

树的遍历操作使用递归的方式遍历代码会相对简单,但是占用的内存比非递归要明显增多,至于那种方式都可。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-11-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
数据结构——树和二叉树
满二叉树是叶子一个也不少的树,而完全二叉树虽然前n-1层是满的,但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
ruochen
2021/06/29
7460
数据结构 第五章 树和二叉树
树:n(n≥0)个结点的有限集合。 当n=0时,称为空树; 任意一棵非空树满足以下条件: ⑴ 有且仅有一个特定的称为根的结点; ⑵ 当n>1时,除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,… ,Tm,其中每个集合又是一棵树,并称为这个根结点的子树。 结点的度:结点所拥有的子树的个数。 树的度:树中各结点度的最大值。 叶子结点:度为0的结点,也称为终端结点。 分支结点:度不为0的结点,也称为非终端结点。 孩子、双亲:树中某结点子树的根结点称为这个结点的孩子结点,这个结点称为它孩子结点的双亲结点; 兄弟:具有同一个双亲的孩子结点互称为兄弟。 路径:如果树的结点序列n1, n2, …, nk有如下关系:结点ni是ni+1的双亲(1<=i<k),则把n1, n2, …, nk称为一条由n1至nk的路径;路径上经过的边的个数称为路径长度。 祖先、子孙:在树中,如果有一条路径从结点x到结点y,那么x就称为y的祖先,而y称为x的子孙。 结点所在层数:根结点的层数为1;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层。 树的深度:树中所有结点的最大层数,也称高度。 层序编号:将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。 有序树、无序树:如果一棵树中结点的各子树从左到右是有次序的,称这棵树为有序树;反之,称为无序树。 森林:m (m≥0)棵互不相交的树的集合。 同构:对两棵树,若通过对结点适当地重命名,就可以使这两棵树完全相等(结点对应相等,结点对应关系也相等),则称这两棵树同构。 前序遍历:树的前序遍历操作定义为: 若树为空,不进行遍历;否则 ⑴ 访问根结点; ⑵ 按照从左到右的顺序前序遍历根结点的每一棵子树。 后序遍历:树的后序遍历操作定义为: 若树为空,则遍历结束;否则 ⑴ 按照从左到右的顺序后序遍历根结点的每一棵子树; ⑵ 访问根结点。 层序遍历:树的层序遍历操作定义为: 从树的第一层(即根结点)开始,自上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。
Twcat_tree
2022/11/29
3080
二叉树的非递归遍历
                                                            二叉树的非递归遍历
bear_fish
2018/09/20
8630
数据结构基础温故-4.树与二叉树(上)
前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形结构的身影,如下图所示的Windows资源管理器和应用程序的菜单都属于树形结构。树形结构是一种典型的非线性结构,除了用于表示相邻关系外,还可以表示层次关系。本文重点讨论树与二叉树的基本结构和遍历算法等内容。
Edison Zhou
2018/08/20
5250
数据结构基础温故-4.树与二叉树(上)
数据结构不懂二叉树,就来看这里吧
二叉树(Binary Tree)相信大家不陌生吧,不管在面试还是平时开发中,都会经常用到,其定义为每个节点最多两个子节点的有序树。本文将对二叉树进行全面而深入的讲解,涵盖其基本概念、存储结构、遍历方法以及相关操作的实现细节,帮助大家更好地理解和应用这一数据结构。
小明爱吃火锅
2025/01/16
2140
二叉树
定义:二叉树是有限结点的集合 二叉树有五种形态,有四种表示方法,其中括号表示法是最重要的,下面的链式存储结构也是根据括号表示法来的== 二叉树的性质: 性质1:非空二叉树上的叶子节点数等于双分支节点数加1 性质2:非空二叉树的第i层上最多有2(i-1)个结点 性质3:高度位h的二叉树最多有2(h)-1个结点
废江_小江
2022/09/05
3300
二叉树
二叉树由浅至深(上)
树有很多种表示方式,如:双亲表示法,孩子表示法、孩子兄弟表示法等等。这里简单了解其中最常用的孩子兄弟表示法。
海盗船长
2020/08/27
3030
二叉树四种遍历,根据前中,后中遍历序列求二叉树
采用指针+结点来存储二叉树,链表栈也是如此, BTNode本身也是一个指针节点,可以指向和其一样结构的地址,所以,struct结构体中的结点也是struct结构体类型
废江_小江
2022/09/05
2420
二叉树的构建及其遍历算法
本篇博客参照了兰亭风雨的博客:http://blog.csdn.net/ns_code/article/details/12977901/
AI那点小事
2020/04/20
4660
二叉树的构建及其遍历算法
二叉树的遍历——递归和非递归
二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中, 前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。 一.前序遍历    前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。   1.递归实现 void pre_order(BTre
猿人谷
2018/01/17
1.3K0
带你一文看懂二叉树的先(中、后)序遍历以及层次遍历(图解+递归/非递归代码实现)
  先序遍历的核心思想:1.访问根节点;2.访问当前节点的左子树;3.若当前节点无左子树,则访问当前节点的右子树;即考察到一个节点后,即刻输出该节点的值,并继续遍历其左右子树。(根左右)
嵌入式与Linux那些事
2021/05/20
37.2K0
带你一文看懂二叉树的先(中、后)序遍历以及层次遍历(图解+递归/非递归代码实现)
数据结构基础温故-4.树与二叉树(中)
在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要比非递归代码要大很多。而且,如果递归深度太大,可能系统撑不住。因此,我们使用非递归(这里主要是循环,循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销)来重新实现一遍各种遍历算法,再对二叉树的另外一种特殊的遍历—层次遍历进行实现,最后再了解一下特殊的二叉树—二叉查找树。
Edison Zhou
2018/08/20
6090
数据结构基础温故-4.树与二叉树(中)
数据结构C#版笔记--树与二叉树
                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以认为是node的特例。 树跟之前学习过的线性结构不同,它是一对多的非线性结构,具有二个基本特点: 1、根节点(root)没有前驱节点,除root之外的所有节点有且只有一个前驱节点 2、树中的所有节点都可以有0个或多个后继节点。 所以下面这些歪瓜咧枣,不能算是树:                 图2 下是是一些烦人但是很重要的术语:   1、
菩提树下的杨过
2018/01/23
1.5K0
数据结构C#版笔记--树与二叉树
二叉树的基本操作(C 语言版)包含递归和非递归算法
二叉树是每个结点最多有两个子树的树结构,常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构,用的是二叉链,本质上是链表。二叉树通常以结构体的形式定义,如下,结构体内容包括三部分:本节点所存储的值、左孩子节点的指针、右孩子节点的指针。
零式的天空
2022/03/28
4K0
我的思念像满二叉树般疯长,每个空指针都指向你的方向——全程动画可视化数据结构算法之二叉树
盛透侧视攻城狮
2025/03/02
1561
我的思念像满二叉树般疯长,每个空指针都指向你的方向——全程动画可视化数据结构算法之二叉树
数据结构图文解析之:树的简介及二叉排序树C++模板实现.
0. 数据结构图文解析系列 数据结构系列文章 数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现 数据结构图文解析之:栈的简介及C++模板实现 数据结构图文解析之:队列详解与C++模板实现 数据结构图文解析之:树的简介及二叉排序树C++模板实现. 数据结构图文解析之:AVL树详解及C++模板实现 数据结构图文解析之:二叉堆详解及C++模板实现 数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现 1. 树的简介 1.1 树的特征 树是一种数据结构,它是n(n>=0)个节点的有限集。n=0
Tencent JCoder
2018/07/02
8451
二叉树的非递归遍历(递归和非递归)
二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。在三种遍历中, 前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。 一.前序遍历    前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。   1.递归实现 void pre_order(BTree
猿人谷
2018/01/17
1.7K0
数据结构(三):二叉树遍历
前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,所以可以按照根-左-右的方式,递归访问每棵子树。
zhipingChen
2018/09/13
6780
数据结构(三):二叉树遍历
树形结构--二叉树以及二叉树的遍历(十七)
性质3:在任意一棵二叉树中,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
花狗Fdog
2020/10/28
6480
树形结构--二叉树以及二叉树的遍历(十七)
二叉树的链式存储结构创建与遍历
递归异常,忘记生成树的时候申请空间,和节点异常,定义了数据为%d类型,输入了整个字符串导致
一个风轻云淡
2023/12/30
1800
推荐阅读
相关推荐
数据结构——树和二叉树
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档