数据结构与算法-树的定义【七】

绝地灬酷狼 2023-05-22 22:40 13阅读 0赞

标签（空格分隔）： 数据结构与算法

--------------------

## 树的定义 ##

栈和队列的数据元素之间的关系从逻辑结构上来看是线性结构，就是一一对应关系。而树型结构的逻辑结构就不是一对一了，是一对多。这个[链接][Link 1]里面介绍了，线性结构。现在讨论的树就是非线性结构中的一种【树形结构】。  
参考线性表的特性，线性表里面的元素，只能最多只能有一个前驱节点和一个后继节点。  
但是树形结构里面的元素，至多一个前驱节点，但是可以有多个后继节点。

树是n(n>=0)个节点组成的有限集。

1.  n为0，则为空树
2.  n不为0的情况满足两个条件：  
    A，有且仅有一个根节点\[无父节点/前驱节点\]。  
    B，其与节点可以分为m(m>=0)个互不想交的有限集T1, T2, T3…Tm，其中每一个集合本身又是一颗树，并称之为子树(SubTree)。

## 基本术语 ##

根节点： 无父子节点  
度：节点拥有的子树数量  
叶子节点：度为0的节点  
树的度：树内各个节点的度的最大值

## 二叉树 ##

一个节点最多2个子树，并且是有顺序的，左子树或者右子树。  
对于只有两个节点的普通树来说：子节点没有位置可言。  
对于只有两个节点的二叉树来说：子节点要么在左子节点，要么在右子节点。

任意一棵树都可以转换成唯一的与之对应的二叉树, 实现方式参考这个[链接][Link 2]

## 二叉树的遍历\[重点\] ##

1，先序/中序/后序3种遍历都可以通过递归来实现。

2，非递归的方式，三种方式又有所不同：

*  深度优先遍历 先序后序\[stack 栈 先进后出\] 中序\[queue 队列 先进先出\]
 *  广度优先遍历 先进先出\[queue 队列 先进先出\] 也可以用递归

## 特殊性质 ##

对于一个二叉树，所有叶子节点的总数 等于 度为2的节点数 + 1。`N0 = N2 + 1`

前提：总边数为B，总节点数为n。  
1,总边数，B = n - 1【从下往上看】 。 B = N2 \* 2 + N1 \* 1 【从上往下看】----> 得到  
`n = 2 * N2 + 1 * N1 + 1`  
2,总节点数n 为度为0，1，2的节点数之和。 -----> 得到  
`n = N2 + N1 + N0`

最终得到结论： `N0 = N2 + 1`

## 满二叉树 ##

二叉树的每一层节点数都达到最大值，那么这颗树为满二叉树。第n层的节点数为2^(n-1), 总的节点数为2^n - 1 个。

## 完全二叉树 ##

对满二叉树的节点，从上而下，从左到右进行编号。

从最后一个节点开始，【连续】的去掉n个节点，剩下的树就是完全二叉树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70_pic_center]

--------------------

> ## 树的存储结构 ##

和线性表一样，也可以分为： 线性存储结构/链式存储结构。

1，线性存储结构，连续的存储空间去存储树的节点。

Tree 1                     Tree 2                    
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7

tree1的结果\[1, 3, 2, 5\]  
tree2的结果\[2, 1, 3, null, 4, null, 7\]

Tree 3                                       
          1                                                     
           \                                                     
            2                                                
             \                                               
              5

tree3的结果为\[1, null, 2, null, null, null, 5\]

Tree4                                       
          1                                                     
           \                                                     
            2                                                
             \                                               
              5    
               \
                6

Tree4的结果为\[1, null, 2, null, null, null, 5, null, null, null, null, null, null, null, 6\]

可以看到，实际上顺序存储结构，有浪费空间的情况，在特殊的情况下，浪费的空间是巨大的。

所以顺序存储结构只适合`满二叉树` 和 `完全二叉树`【因为是连续的】。

2，链式存存储结构

数据域、左孩子指针，右孩子指针。

Tree4:
                                       
          1                                                     
           \                                                     
            2                                                
             \                                               
              5    
               \
                6

上面同样的树，咱们用链式结构来存储，是这样的。

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
     
     const n1 = new TreeNode(1)
     const n2 = new TreeNode(2)
     const n5 = new TreeNode(5)
     const n6 = new TreeNode(6)
     
     n1.right = n2
     n2.right = n5
     n5.right = n6

链式存储实际上也有空间的浪费，这里的空指针域有5个，但是和顺序存储结构浪费的空间（11）比起来是好很多了。而且插入和删除更加快速。

> 在n个节点的二叉树中，有多少个空指针域？

一共2n个指针域，每个节点都有一个左孩子和右孩子指针。每个节点都有唯一一个父节点指向它【除了根节点】，所有一共有n-1个非空指针域。

空的指针域，就为： 2n - (n - 1) = n + 1

[Link 1]: https://blog.csdn.net/a5534789/article/details/103445895
[Link 2]: https://www.cnblogs.com/Lanly/p/6305766.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20230521/0ad6300b0f5146e0a492764eae86db80.png