学习二叉树必须知道的基本性质

冷不防 2022-06-06 07:53 172阅读 0赞

## 二叉树 ##

1.  首先二叉树为什么是我们讨论的对象，那么多叉树，比如3叉树，4叉树，5叉树。其实我也不知道为什么讨论二叉树，但是二叉树的使用范围是非常广泛的。所以我们会深入的去讲解二叉树。
2.  二叉树为何物，即定义是什么，二叉树还有个英文名在国外叫Binary Tree.是不是非常的熟悉。首先我们要知道二叉树并不是真的树，在计算中是描述了一个数据节点持有2个子节点并且仅最多2个节点。这2个子节点是没有任何交集也就是没有任何联系，是2棵独立的节点，或者是独立的2 棵子树。  
    先上图，以免说多了看晕  
    ![这里写图片描述][SouthEast]

看图是不是每个节点的孩子节点最多为2个并且2个孩子节点都是没有任何关系的。

下面我来给二叉树下个正式的官方定义：二叉树是由n(n >=0)个有限节点的集合，从n的取值多少我们看的出这个树当n=0的时候也就是这棵树没有任何的节点我们称它为空树，如果n >= 1,这棵树是由一个根节点加上节点的2个左右子树构成，当然它的子树也会有自己的子树。

## 二叉树的特性 ##

注意二叉树交换他的左右子树是不同的一棵树的。  
二叉树包括左右斜树和满二叉树，完全二叉树，  
满二叉树是什么呢，我们的最后一层也就是有叶子的那一层是满的节点就是说在也加不上节点了，并且除叶子那层外的层上的节点都是满的。  
完全二叉树：一定要在满二叉树基础之上，我们先找到满二叉树最后一层我们可以不拿掉满二叉树的任何节点这棵树也叫完全二叉树，我们要去掉部分节点也只能从叶子节点那层并且是从右开始拿掉节点剩余的树就是完全二叉树。  
二叉树的第i(i >=1)层上的节点数最多是2^(i - 1)个节点。我们看上图，假如i = 2就是在二叉树第二层上我们可以数出是BC二个节点，并且是最多的，我们在看2^(2-1) = 2^1 = 2个。其他层请自己用数据测试下，很简单。

在来谈下非常重要的性质：  
![这里写图片描述][SouthEast 1]

\#\# 如何根据节点编号求双亲编号 \#\#  
补一个小知识点：我们的编号可以看成是数组索引，这样我们就可以通过编号存入内存，通过编号就可以读取和写入数据。  
首先我们给二叉树从根节点开始编号，是从上到下，左到右的顺序并且是从1开始。  
假如i = 1,表示这个节点就是我们二叉树的根节点，是没有双亲的，反之节点数大于1我们用i/2就是得到父亲的索引号。下面我们进行测试，假如i = 1, 那么双亲节点 = 1/2 = 0;我们没有编号为0的，说明当前节点就是根节点，而二叉树根节点是没有双亲节点的。  
i >1的情况下。假如i = 3,说明是第三编号的节点，也就是根节点的右孩子，3/2 = 1,得到了他的双亲节点是1编号的，i = 2得到他的双亲节点也是1编号。那么i = 4,5,6,7,8….呢是不是也满足嗯，具体不测了。

下面我们在来讲解如何通过当前节点编号也就是顺序存储表中的索引拿到当前节点的左右孩子节点呢。我先给个计算公式假如当前节点i = 1  那么当前5编号的节点的编号就 2*i = 2，对不对呢。我先上图

![这里写图片描述][SouthEast 2]  
我就不编号了，是不是很明显那个数值就是2号对应的2编号。那么右孩子是不是+ 1呢。i = 2i + 1 = 3;  
对就是3号。那么其他值是不是也一样对的。这里要注意假如你编号是5元素，那么从二叉树上看他是没有子节点的。如果你还是用上上个公式，在程序中就出bug了。因为当我们需要得到当前节点的孩子节点之前必须做个有没有孩子节点存在的判断。很明显如果我们通过当前节点得到的左右孩子数的编号已经大于节点总数了，那肯定是没有左右孩子的。公式如下if(2i > n) (n表示数的节点数) 这个情况表示没有左孩子 反之就是有左孩子。 if((2i + 1) > n) 也是没有右孩子，反之有。

[SouthEast]: /images/20220606/d1c28df5029846d99064b789640d1519.png
[SouthEast 1]: /images/20220606/24c08b4699cd43909de6ea4998cd0fc3.png
[SouthEast 2]: /images/20220606/5455d640e63243c694f54e2a8499e2ee.png