锐客网

  1. 首页 > 生活百科 > it技术 > >

笔记|数据结构-＞二叉树的介绍

数据结构c语言笔记链表开发语言

目录
一，树的概念和结构
1.1 概念
1.2 相关的重要概念
双亲节点或父节点
孩子节点或子节点
节点的度
树的度
叶子节点或终端节点
兄弟节点
节点的层次
树的高度或深度
节点的祖先
子孙
森林
1.3 树的孩子兄弟表示法
二、二叉树
2.1 概念
特点
2.2 特殊的二叉树
满二叉树
完全二叉树
2.3 重要性质
总节点数n：
n个结点的满二叉树的深度h
指定层数节点数：
叶节点和度为2节点的特殊关系
总节点数为n的完全二叉树
2.4 二叉树的存储结构
顺序存储
链式存储

一，树的概念和结构 1.1 概念 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。看起来向一颗根朝上的倒挂着的树。
子树（分支）间不能有联系，否则不是树形结构。
笔记|数据结构-＞二叉树的介绍
文章图片

1.2 相关的重要概念 用血缘关系来记忆树的概念
双亲节点或父节点
若一个节点含有子节点（有分支），则这个节点称为其子节点的父节点；
如上图：A是B的父节点
孩子节点或子节点
一个节点含有的子树的根节点称为该节点的子节点；
如上图：B是A的孩子节点
节点的度
一个节点含有的子树的个数称为该节点的度（一个节点的孩子个数）；
如上图：A的为6，D为1，E为2
树的度
一棵树中，最大节点的度称为树的度（拥有最多孩子的节点的孩子个数）；
如上图：树的度为6
叶子节点或终端节点
度为0的节点称为叶节点（树末尾无分支的节点）；
如上图：B、C、H、I、K、L、M、N、P、Q节点为叶节点
兄弟节点
具有相同父节点的节点互称为兄弟节点；
如上图：B、C是兄弟节点
节点的层次
从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度
树中节点的最大层次； 如上图：树的高度为4
节点的祖先
从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙
以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林
由m（m>0）棵互不相交的树的集合称为森林；
1.3 树的孩子兄弟表示法 采用的是链式存储结构，保存孩子的节点指向孩子，兄弟的节点指向兄弟，并保存元素
笔记|数据结构-＞二叉树的介绍
文章图片

typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 };

二、二叉树 2.1 概念 二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。
笔记|数据结构-＞二叉树的介绍
文章图片

笔记|数据结构-＞二叉树的介绍
文章图片

特点
1.二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
2.2 特殊的二叉树 满二叉树
【笔记|数据结构-＞二叉树的介绍】一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。
笔记|数据结构-＞二叉树的介绍
文章图片

完全二叉树
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
笔记|数据结构-＞二叉树的介绍
文章图片

2.3 重要性质 规定根节点的层数为1，层数用k表示，层数K=树的深度h
总节点数n：
n=2^k-1 或 n=2^h-1
n个结点的满二叉树的深度h
公式：h = 笔记|数据结构-＞二叉树的介绍
文章图片

由总结点数公式可推出
指定层数节点数：
一棵非空二叉树的第i层上最多有 2^(i-1) 个结点.
叶节点和度为2节点的特殊关系
n0=n2+1n0(叶子节点数)n2(度为2节点数)
总节点数为n的完全二叉树
注意：序号从0开始，下图序号在上面标注，n为节点总数，不是最大序号
对于序号为i的节点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
孩子节点序号不能大于总结点序号
2. 若2i+1=n则无左孩子
3. 若2i+2=n则无右孩子
笔记|数据结构-＞二叉树的介绍
文章图片

2.4 二叉树的存储结构 顺序存储
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。如下图
笔记|数据结构-＞二叉树的介绍
文章图片

链式存储
用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
笔记|数据结构-＞二叉树的介绍
文章图片

二叉树的基本概念到这结束，下一篇介绍堆的概念及实现：堆的实现+堆排序_i跑跑的博客-CSDN博客

    推荐阅读


    上一篇：笔记|堆排序详解+TOP-K问题

    下一篇：LeetCode OJ - Binary Tree Preorder Traversal