- 前言
- 1 树的基本概念
- 1.1 树的定义
- 1.2 基本术语
- 1.3 树的性质
- 2. 二叉树的概念
- 2.1 二叉树的定义及其主要特性
- 2.1.1二叉树的定义
- 2.1.2几个特殊的二叉树
- 3. 二叉树的遍历与线索二叉树
- 4. 树、森林
- 5. 树与二叉树的应用
- 1.引入库
- 2.读入数据
- 总结
前言
1 树的基本概念 1.1 树的定义
树：
n（n>=0）个结点的有限集合。n=0时，称为空树。
树应满足的条件：
- 有且仅有一个特定的称为根的结点。
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，… Tm，其中每个集合又是一棵树，并将其称为根的子树。
树的特点：
- 树的根节点没有前驱，除根结点外的所有结点有且只有一个前驱。
- 树中所有结点可以有多个或零个后继。
如下图所示：
-
祖先：考虑结点K，根A到结点K的唯一路径（路径具有单一方向）上的任意结点，称为结点K的祖先。
-
子孙：考虑结点A，根A到结点K的唯一路径上的任意结点，称为结点A的子孙。
-
双亲：考虑结点K，根A到结点K的唯一路径上最接近结点K的结点E称为K的双亲。
-
孩子：考虑结点A，根A到结点K的唯一路径上最接近结点A的结点B称为A的孩子。 兄弟：有相同双亲的的结点称为兄弟。
-
结点的度：树中一个结点孩子的个数称为称为该结点的度。
-
树的度：树中结点的最大度树。
-
分支节点（非终端结点）：度大于0的结点。
-
叶子节点（终端结点）：度为0的结点。
-
结点的层次：从树根开始定义，根节点为第1层，它的子结点为第2层，依次类推。
-
结点的深度：从根结点开始自顶向下逐层累加。
-
结点的高度：从叶结点开始自底向上逐层累加。
-
树的高度：树中结点的最大层数。
-
有序树：树中结点的各子树从左到右是有次序的，不能互换。
-
无序树：树中结点的各子树从左到右是无次序的，可以互换。
-
路径：树中两个结点之间的路径是由这两个结点之间结点序列构成的。
-
路径长度：两个结点之间的路径上所经过边的个数。
森林：森林是m(m>0)棵互不相交的树的集合。
1.3 树的性质- 树中结点数等于所有结点的度数之和加1。
- 度为m的树中第i层上至多有mi-1个结点（i>=1）。
- 高度为h的m叉树至多有(mh-1)/(m-1)个结点。
- 具有n个结点的m叉树的最小高度为[logm(n(m-1)+1)]。
含义：每个结点至多有两棵子树的树，这两棵子树称为左树与右数，其次序不能任意颠倒。
二叉树的5种基本形态：
二叉树与度为2的有序树的区别：
度为2的树至少有3个结点，而二叉树可以为空。
度为2的树其孩子的左右次序相对于另一个孩子而言的，而二叉树无论其孩子数是否为2，均需确定其左右次序。
满二叉树：
3. 二叉树的遍历与线索二叉树 4. 树、森林 5. 树与二叉树的应用 1.引入库代码如下（示例）：
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import warnings
warnings.filterwarnings('ignore')
import ssl
ssl._create_default_https_context = ssl._create_unverified_context
2.读入数据
代码如下（示例）：
data = pd.read_csv(
'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())
该处使用的url网络请求的数据。
总结
提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
