当前位置:网站首页>二叉树的基本概念和性质
二叉树的基本概念和性质
2022-07-07 16:50:00 【Brant_zero】
目录
1.3 树的表示
一、树的概念和结构
1.1 树的概念
树是一种非线性的数据结构,他是由n(n>=0)个有限结点组成的一个具有层次关系的集合。叫做树是因为其结构像一颗倒挂的树,即根朝上,而叶朝下。
- 有一个特殊的节点,称为根节点,根结点没有前驱结点。
- 除了根节点,其余结点被分成M(M>0)个互不相交的集合T1、T2……Tn,其中每一个集合Ti(1 <= i <= n)又是一颗树结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继结点。
- 因此,树是递归定义的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构,而应是图型的数据结构。
1.2 树的重要概念
重要:
节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的度为6。
叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I……等为叶节点。
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;如上图:A是B的父节点。
孩子节点或子节点:一个节点含有的子树的根节点称为节点的子节点;如上图:B是A的孩子节点。
树的高度或深度:树种节点的最大层次;如上图:树的高度为4。
节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先。
子孙:从某节点为根的子树种任一节点都称之为该节点的子孙。如上图:所有节点都是A的子孙。
树的度:一颗树中,最大节点的度称之为树的度;如上图:树的度为6。
其次:
非终端节点或分支节点:度不为0的节点;如上图:D、E、F、G……等节点为分支节点。
兄弟节点:具有相同父节点的节点称为兄弟节点;如上图:B、C是兄弟节点。
节点的层次:从根开始定义起,根为第一层,根的子节点为第二层,以此类推;
堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为堂兄弟节点。
森林:由m(M>0)棵互不相交的树的集合称为森林。
1.3 树的表示
树结构相对于线性表就比较复杂了,既要保存值域、也要保存结点和结点之间的关系,实际中树有很多种表示方法,这里了解一下最常用的孩子兄弟表示法即可。
typedef int DataType;
struct Node
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
二、 二叉树概念及结构
2.1 二叉树的概念
一颗二叉树是结点的一个有限集合,该集合:
- 或则为空
- 由一个根结点加上两棵别称为左子树和右子树的二叉树组成。
从上图可以看出:
- 二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树。
2.2 特殊的二叉树
- 满二叉树:一个二叉树,如果每一层的结点树都达到最大值,啧啧换个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是-1,则它就是满二叉树。
- 完全二叉树:完全二叉树是效率很高的数据机构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点——对应时称为完全二叉树。(第n层不满但是从左到右为连续,n-1层全满),要注意的是满二叉树是一种特殊的完全二叉树。
2.3 二叉树的性质
重要:
- 若规定根结点的层数为1,则一颗非空二叉树的第i层上最多有个结点。
- 若规定根结点的层数为1,则深度为h的二叉树的最大节点是.
- 对任何一颗二叉树,如果度为0其叶节点个数为n0,
- 若规定根节点的层数为1,具有n的结点的满二叉树的深度,.
- 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
- 若i>0,i位置节点的双亲序号:(i-1)/2; i=0, i为根结点编号,无双亲结点
- 若2i+1<n , 左孩子序号:2i+1, 2i+1>=n否则无左孩子
- 若2i+2<n , 右孩子序号:2i+2,2i+2>=n 否则无右孩子
2.4 二叉树练习题
1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为 ()A 不存在这样的二叉树B 200C 198D 199
2.下列数据结构中,不适合采用顺序存储结构的是 ()A 非完全二叉树B 堆C 队列D 栈
3.在具有 2n 个结点的完全二叉树中,叶子结点个数为 ()A nB n+1C n-1D n/2
4.一棵完全二叉树的节点数位为531个,那么这棵树的高度为 ()A 11B 10C 8D 12
5.一个具有767个节点的完全二叉树,其叶子节点个数为()A 383B 384C 385D 386
答案:
第一题:
第二题: B
第三题:
第四题:
第五题:
本篇到此就结束了,其中重点在于树的概念和二叉树的性质,这些是理解二叉树的精髓,也是考试的出题点,希望大家可以理解。
下篇博客会带来链式二叉树的基本结构和功能,希望大家持续关注。
边栏推荐
- 能同时做三个分割任务的模型,性能和效率优于MaskFormer!Meta&UIUC提出通用分割模型,性能优于任务特定模型!开源!...
- Charles+Postern的APP抓包
- Win11C盘满了怎么清理?Win11清理C盘的方法
- Tear the Nacos source code by hand (tear the client source code first)
- A few simple steps to teach you how to see the K-line diagram
- Comparison and selection of kubernetes Devops CD Tools
- Datasimba launched wechat applet, and datanuza accepted the test of the whole scene| StartDT Hackathon
- [demo] circular queue and conditional lock realize the communication between goroutines
- Charles+drony的APP抓包
- [unity shader] insert pass to realize the X-ray perspective effect of model occlusion
猜你喜欢
Disk storage chain B-tree and b+ tree
Ten thousand words nanny level long article -- offline installation guide for datahub of LinkedIn metadata management platform
idea彻底卸载安装及配置笔记
直播预约通道开启!解锁音视频应用快速上线的秘诀
CVPR 2022 - learning non target knowledge for semantic segmentation of small samples
AntiSamy:防 XSS 攻击的一种解决方案使用教程
Nat address translation
Differences between rip and OSPF and configuration commands
Discuss | frankly, why is it difficult to implement industrial AR applications?
Classification of regression tests
随机推荐
小试牛刀之NunJucks模板引擎
Win11C盘满了怎么清理?Win11清理C盘的方法
Wireshark分析抓包数据*.cap
pip相关命令
Discuss | frankly, why is it difficult to implement industrial AR applications?
Backup Alibaba cloud instance OSS browser
线程池中的线程工厂
[sword finger offer] 59 - I. maximum value of sliding window
Calculation of torque target value (ftorque) in servo torque control mode
socket编程之常用api介绍与socket、select、poll、epoll高并发服务器模型代码实现
卖空、加印、保库存,东方甄选居然一个月在抖音卖了266万单书
GSAP animation library
AI 击败了人类,设计了更好的经济机制
直播软件搭建,canvas文字加粗
Will low code help enterprises' digital transformation make programmers unemployed?
Recommend free online SMS receiving platform in 2022 (domestic and foreign)
Do you really understand sticky bag and half bag? 3 minutes to understand it
Sports Federation: resume offline sports events in a safe and orderly manner, and strive to do everything possible for domestic events
[unity shader] insert pass to realize the X-ray perspective effect of model occlusion
Some key points in the analysis of spot Silver