【数据结构】树和二叉树基本概念和性质

前言
1、树的概念
- 1.1 树的基本概念
- 1.2 树的主要概念
- 1.3 树的表示
- 1.4 树在实际中的运用（表示文件系统的目录树结构）
2. 二叉树概念及结构
- 2.1 概念
- 2.2 特殊的二叉树
- 2.3 二叉树的性质
3. 二叉树性质相关选择题练习
4. 答案和解析
5. 总结

前言

本章带来数据结构重点树相关的概念，同时和之前的线性结构完全不同，树是非线性结构

1、树的概念

1.1 树的基本概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它
叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

有一个特殊的结点，称为根结点，根节点没有前驱结点
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集
合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以
有0个或多个后继
因此，树是递归定义的

子树是不相交的，相交如下图，这个结构就不是树了，因为里面有回路，类似与图结构
在这里插入图片描述

1.2 树的主要概念

在这里插入图片描述
关键：

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为3
叶节点或终端节点：度为0的节点称为叶节点；如上图：J、F、K、L、H、I是叶子结点
非终端节点或分支节点：度不为0的节点；如上图：B、C、D、E…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B
的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：：具有相同父节点的节点互称为兄弟节点；如上图：B、C、D是兄弟
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为3
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
另一种情况，根为0层，根的子节点为第1层
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先，父亲也是祖先结点
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

其次：

森林：由m（m>0）棵互不相交的多颗树的集合称为森林；（数据结构中的学习并查集本质就是一个森林）

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，
如：双亲表示法，孩子表示法、孩子兄弟表示法等等。

第一种：孩子兄弟表示法，最常用的的树表示方法

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

在这里插入图片描述

第二种：双亲表示法，把所有的节点都存在数组里，通过子节点存父节点的数组下标来表示，注意不是父节点存下标，就是一个节点只指向父亲，不指向孩子
第三种：通过顺序表来存储，但是我们并不知道到底有多少个子节点，这里C++里面库里vector可以解决，vector是可变的不固定数组

1.4 树在实际中的运用（表示文件系统的目录树结构）

在这里插入图片描述

2. 二叉树概念及结构

2.1 概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子
树和右子树的二叉树组成。
二叉树的特点：

每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
二叉树的子树有左右之分，其子树的次序不能颠倒。

2.2 特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉
树。也就是说，如果一个二叉树的层数为K，且结点总数是(2 ^ k) - 1 ，则它就是满二叉树。
完全二叉树：前k-1层是满的，最后一层不满，但是最后一层从左往右节点都是连续的，节点个数(2 ^ k - 1 - X),X表示最后一层缺的数量

在这里插入图片描述

2.3 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i - 1) 个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1
对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2
＋1
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=LogN，以2为底
度为1的结点一定是左子树；
度要么为1，要么为0
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从开始编号: 那么就会有：（对于编程的写法，这个规律是成立的）

左孩子结点的下标：2*parent +1;
右孩子结点的下标：2*parent +2;
父亲结点的下标：(child -1) / 2; 其中child为左右孩子都行。

3. 二叉树性质相关选择题练习

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199


2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2



3.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

4. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386