二叉树的基本概念和特点

太过爱你忘了你带给我的痛 2022-01-31 22:43 563阅读 0赞

**首先，什么是二叉树？**  
二叉树（Binary Tree）是n （n>=0）个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两个互不相交的，分别称为根节点的左子树和右子树的二叉树组成。  
所以这是二叉树吗？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70]  
错，上图并不是一个二叉树

**由此引入二叉树特点：**  
1.每个节点最多有两个子树，所以二叉树不存在度大于2的节点（结点的度：结点拥有的子树的数目。），可以没有子树或者一个子树。  
2.左子树和右子树有顺序，次序不能任意颠倒。  
3.即使树种某节点只有一颗子树，也要区分是左子树还是右子树。  
所以二叉树长这这样  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 1]  
**二叉树的5种基本形态：**  
1.空二叉树  
2.只有一个根节点  
3.根节点只有左子树  
4.根节点只有右子树  
5.根节点既有左子树，又有右子树

**特殊二叉树：**  
1.斜树：  
所有节点都只有左子树的二叉树叫左斜树，所有节点都只有右子树的二叉树叫右斜树，  
![在这里插入图片描述][20190512160455173.png]  
![在这里插入图片描述][20190512160558655.png]  
2.满二叉树  
在一棵二叉树中如果所有分支节点都存在左子树和右子树并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

![在这里插入图片描述][20190512161144874.png]  
3.完全二叉树  
对于一颗具有n个节点的二叉树按层次编号，如果编号为i（1<=i<=n）的节点与同样深度的满二叉树中编号为i的节点在二叉树中位值完全相同，则这棵二叉树称为完全二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 2]  
二叉树性质：  
1.二叉树第i层上的结点数目最多为 2\{i-1\} (i≥1)  
2.深度为k的二叉树至多有2\{k\}-1个结点(k≥1)  
3.在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1  
4.包含n个结点的二叉树的高度至少为log2 (n+1)  
文章参考大话数据结构

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70]: /images/20220201/47e219bfddd546a180f4f5d224656343.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 1]: /images/20220201/8516af7129c94b1eba679dee2cc0fe7e.png
[20190512160455173.png]: /images/20220201/0e289319126243a591b0f63ca7c8341d.png
[20190512160558655.png]: /images/20220201/8118c7aa7ecc4b7e83a7be77eff12b7b.png
[20190512161144874.png]: /images/20220201/6b24294e999f4275b4b4d2e617c49ef2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODE3ODI3_size_16_color_FFFFFF_t_70 2]: /images/20220201/e8943fde116b4476ac7688544eb54755.png