Data Structure--树基本概念引入(二叉树)

向右看齐 2022-10-31 01:57 218阅读 0赞

### 树的表示 ###

*  基本概念
 *  关键字
 *   *  二叉树
     *  二叉树存储
     *   *  1.顺序存储
         *  2.链式存储

# 基本概念 #

树是一个非线性的数据结构,由有限的节点组成的由层次关系的集合,因为它的结构和我们显示现实生活中的数恰巧是倒过来的,所以被叫做树

# 关键字 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]  
**比较简单的关键字:**  
节点的度：一个节点含有的子树的个数称为该节点的度；

叶节点或终端节点：度为0的节点称为叶节点；

非终端节点或分支节点：度不为0的节点；

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

树的度：一棵树中，最大的节点的度称为树的度；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

森林：由m（m>0）棵互不相交的树的集合称为森林；

## 二叉树 ##

二叉树的意思就是每一个父节点**最多**只有两个子节点,比较简单  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]  
二叉树有两个特别的存在:**满二叉**和**完全二叉**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]

## 二叉树存储 ##

**二叉树的性质:**

1.  若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2.  若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
3.  对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
4.  若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1).
5.  对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：  
    (1). 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点  
    (2). 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子  
    (3). 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

可以分为下面两种储存方式:

### 1.顺序存储 ###

链接: [点击这里][Link 1]

### 2.链式存储 ###

链接: [点击这里][Link 2]

对于这一节后面的两种储存方式,我会在后面代码整理完后完成,一起加油!!!多敲代码 !!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/c6e30f8bba8d4faba7269a283fec9c6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/b2f5b2263608495ea0ace60673585c45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/2981e98f91d44ac09687a660785676b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221024/22d987d1d3d648798a83432d004b9d31.png
[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/113907885
[Link 2]: https://blog.csdn.net/weixin_46554582/article/details/113926917