数据结构:手撕二叉树

二叉树的基础概念: 

树:高效的查找与搜索

1.为什么会存在树结构?

企业中员工的分类就是一个"树"结构!!!

如果是一个线性结构,大家都在一个"目录"中:

比如当前企业一共有300号员工,要找到一个特定员工最坏情况下要找300次

如果是一个树结构:

按照员工的职级分类,300个员工一共分为5级,搜索一个特点员工只需要5次即可找到

OS系统中的文件就是基于树结构管理的

OS系统中的所有文件都放在一个目录下,若当前操作系统有1亿个文件,最坏情况遍历1亿次才能找到特定元素

OS为多级目录,只需要logN级别的查找次数

2.关于树的概念 

• 子树不相交
• 除了根节点没有父节点之外,每个节点有且只有一个父节点
• 边的个数x,树中的节点个数n,x = n - 1(每个节点都有父节点,除了跟没有)x = 5 - 1
• 节点和树的"度":
•     节点的度:该节点中包含的子树的个数称为该节点的度 I的度为1,J,K度为0
•     树的度:树中最大的节点的度称为树的度 D的度为3,树的度就是3
• 叶子节点:度为0的节点M,J,K都没有子树,都是叶子节点
• 非叶子节点:度不为0的节点,还存在子树,D,I是非叶子节点
• 跟节点:没有父节点的节点,树中只能有一个,D就是根节点

二叉树:树中节点最大的度为2的树称为2叉树 

  二叉树中,一个节点最多有两颗子树,二叉树节点的度 <= 2;子树有左右之分,左右的顺序不能颠倒

二叉树常考性质:

 1. 在深度为K的二叉树中,最多存在2^k - 1个节点:2^4 - 1 = 15

 2.在第k层,该层最多有2^(k-1)个节点:2^(3-1) = 4

 3.由于任意二叉树都满足节点个数n和边长X具备x = n - 1

    在二叉树中度为2的节点和度为0的节点有一下关系

    n0 = n2+1 

常见的二叉树: 

 满二叉树:在该二叉树中,每一层的节点个数都是最大值,每一层节点个数都是拉满的