二叉树上篇

一、特征

1.1、树的基本定义

树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架
构等等

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

树具有以下特点：

1、每个节点有零个或多个子节点

2、没有父节点的节点为根节点

3、每一个非根节点只有一个父节点

4、每个节点及其后代节点整体上可以看作是一棵树，称为当前节点父节点的一个子树

1.2、树的相关术语

1、节点的度

一个节点含有的子树的个数称为该节点的度

2、叶子节点

度为 0 的节点称为叶子节点，也可以叫做终端节点

3、分支节点

度不为 0 的结点称为分支结点，也可以叫做非终端结点

4、节点的层次

从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推

5、节点的层序编号

将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。

6、树的度

树中所有结点的度的最大值

7、树的高度（深度）

树中结点的最大层次

8、森林

m（m>=0）个互不相交的树的集合，将一棵非空树的根结点删去，树就变成一个森林，给森林增加一个统一的根结点，森林就变成一棵树

二、二叉树的基本定义

1）、二叉树就是度不超过 2 的树（每个节点最多有两个子节点）

2）、二叉树中规定父节点的值大于左子节点，小于右子节点

2.1、满二叉树

1）、一个二叉树，如果每一个层的节点树都达到了最大值，则我们就称这个树为满二叉树

2.2、完全二叉树

1）、叶子节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树（即最下面的叶子节点必须是从左到右一次排列）

三、总结

本篇文章我们介绍：

1、树的基本定义和相关特征

2、二叉树的定义和特征

3、满二叉树和完全二叉树的概念

好了，本篇文章到这里就结束了，感谢你的阅读🤝