树和二叉树（一）

灰太狼 2024-04-20 12:27 0阅读 0赞

## 一、树 ##

> 非线性数据结构，在实际场景中，存在一对多，多对多的情况。

![918b325d0a1c495ebd15a20cfa4ca20e.png][]

> ### 树( tree）是n (n>=0）个节点的有限集。当n=0时，称为空树。 ###
> 
> 在任意一个非空树中，有如下特点。
> 
> 1.有且仅有一个特定的称为根的节点。
> 
> 2.当n>1时，其余节点可分为m (m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

#### 如图所示：节点1:根节点（root），节点5,6,7,8:叶子节点（leaf）；分为不同的层级，节点4是父节点（parent）,节点4的孩子节点（child）节点4的兄弟节点（sibling）; ####

![9f7352000e224988a7fee1684b8d9a47.png][]

> 树的最大的层级树，称为数的高度或深度，上图的数的高度为4。

## 二、 二叉树 ##

二叉树(binary tree）是树的一种特殊形式。二叉顾名思义，这种树的每个节点**最多有2个孩子节点**。

>  **注意：这里是****最多有2个****，也可能****只有1个****，或者****没有****孩子节点。**

![cf90253a39aa4fe287a4e1d36df630e8.png][]

二叉树节点的两个孩子节点，一个被称为左孩子(leftchild) ，一个被称为右孩子（right child）。

此外，二叉树还有两种特殊形式，一个叫作**满二叉树，**另一个叫作**完全二叉树**。

**2.1、二叉树的五种基本形式**：

![5d5af676467e45a6ae4bc80d2c8ca50c.png][]

**2.2、二叉树与树的区别** ：

>  *  **树中结点的最大度数没有限制，而二叉树结点的最大度数为2**
>  *  **树的结点无左、右之分，而二叉树的结点有左、右之分**

**2.3、满二叉树与完全二叉树：**

**（1）满二叉树**

> 一个二叉树的所有非叶子节点都存在左孩子和右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

**简单点说，满二叉树的每一个分支都是满的。**

![5715b7e8d59d4a528975612d07ee2f20.png][]

**（2）完全二叉树**

>  **对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。**

![0b83e60ccc374e7f86a5a75e273264a3.png][]

在上图中，二叉树编号从1到12的12个节点，和**前面满二叉树编号从1到12的节点位置完全对应**。因此这个树是完全二叉树。

完全二叉树的条件没有满二叉树那么苛刻:满二叉树要求所有分支都是满的;而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

## 三、二叉树的性质 ##

> 1、在二叉树的第 i 层上最多有 2^n-1个结点（i>=1）

![e887e2526e4c45fea6a2967755cc7480.png][]

> 2、深度（高度）为 k 的二叉树最多有 2^k - 1个结点（k>=1）

![403a9d4b51bb42889e8550393a6ecfec.png][]

> 3、对任意一颗二叉树，如果其叶子节点数为 N0,度为2的结点数为N2,则 N0 = N2 + 1

设 : 结点之间的总连线数是B ,总结点数是n,  
度为0的结点是n0,  
度为1的结点是n1,  
度为2的结点是n2,

从上往下看 [二叉树][Link 1]最大的度就是2所以的节点要么度是2，要么度是1，要么度是0，度是2的会发出两条线, 度是1的发出1条线所以得到图片里的公式 B = n2 \* 2 + n1;

二叉树的总结点数 n = n1 +n2+n0;

总连续数 B=n-1

![b63b22cca7314cc883c472fb01388ecd.png][]

> 由此得出：度是0的结点个数=度是2的结点个数+1

## 四、二叉树的存储 ##

> 1.链式存储结构
> 
> 2.数组

**（1）链式存储结构**

![88fdcf8648fc4088943b922f94518c6b.png][]

>  *  存储数据的data变量
>  *  指向左孩子的left指针
>  *  指向右孩子的right指针

**（2）数组**

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。

![85c08962f1444fbba181a11f0b636ce2.png][]

**如何方便地在数组中定位二叉树的孩子节点和父节点？**

> 假设一个父节点的下标是parent，
> 
> 左孩子节点的下标=2xparent +1;
> 
> 右孩子节点的下标=2xparent+2。
> 
> 由此：
> 
> 如果一个左孩子节点的下标是leftChild，那么它的父节点下标=(leftChild-1)/2。
> 
> 如果一个右孩子节点的下标是rightChild，那么它的父节点下标=(rightChild-2)/2。
> 
>  **图上所示， 节点5的索引是4，那么节点5的父节点=(4-2)/2=1,由此可得索引1对应的是节点2**

## 五、二叉树的遍历 ##

> 1.  **深度优先遍历**
> 2.  **广度优先遍历**

**1. 深度优先遍历**  
深度优先( depth first search，DFS ) ，顾名思义就是偏向于纵深，“一头扎到底”的访问方式。深度优先遍历又根据遍历顺序的不同分为三种：**前序遍历、中序遍历、后序遍历**。

**1.1 前序遍历**  
所谓前序遍历，是指二叉树遍历每个子树的时候，都是**按照根结点、左子树、右子树的顺序**来遍历，因为根结点在前，所以叫做前序遍历。前序遍历中根结点的优先级别最高。如下图所示：

![56a4708273cf46cbb017798285d8aa0f.png][]

##### 1.2 中序遍历 #####

如果二叉树遍历每个子树的时候，都是**按照左子树、根结点、右子树的顺序**来遍历，因为**根结点在中间，所以叫做中序遍历**。如下图所示：

![638ca1ee9711429d8e4f973ad96e2fc4.png][]

##### 1.3 后序遍历 #####

二叉树遍历每个子树的时候，都是**按照左子树、右子树、根结点的顺序**来遍历，因为根结点在最后，所以叫做后序遍历。如下图所示：

![a6d44f2b9d944be9abb53da1cd24fa83.png][]

> #### 使用递归的方式来操作，如图所示 ####

![5f36bd9add264ccf87e438f6d284610d.png][]

''''树节点'''
    class TreeNode:
        '''初始化'''
        def __init__(self,data):
            self.data=data #数据
            self.left=None #左节点
            self.right=None #右节点
    
    '''二叉树'''
    class MyTree:
        def create_tree(self,input_list=[]):
            #判断数列是否为空
            if input_list is None or len(input_list)==0:
                return None
            #第一个出队
            data=input_list.pop(0)
            #判断数据为空
            if data is None:
                return None
            #树节点
            node=TreeNode(data)
            #创建左节点
            node.left=self.create_tree(input_list)
            #创建右节点
            node.right =self.create_tree(input_list)
            return node
    
        def before_foreach(self,node):
            '''
            前序遍历  （根左右）
            :param node:  二叉树节点
            :return:
            '''
            # 判断节点为空
            if node is None:
                return None
            #显示节点数据
            print(node.data,end=',')
            #再次遍历左节点，右节点
            self.before_foreach(node.left)
            self.before_foreach(node.right)
            return node
    
        def middle_foreach(self,node):
            '''
            中年序遍历  （左根右）
            :param node:  二叉树节点
            :return:
            '''
            # 判断节点为空
            if node is None:
                return None
            #再次遍历左节点
            self.middle_foreach(node.left)
            # 显示节点数据
            print(node.data, end=',')
            # 再次遍历右节点
            self.middle_foreach(node.right)
            return node
    
        def after_foreach(self,node):
            '''
            后序遍历  （左右根）
            :param node:  二叉树节点
            :return:
            '''
            # 判断节点为空
            if node is None:
                return None
            #再次遍历左节点，右节点
            self.after_foreach(node.left)
            self.after_foreach(node.right)
            # 显示节点数据
            print(node.data, end=',')
            return node
    
    
    if __name__ == '__main__':
        #二叉树对象
        my=MyTree()
        #列表
        ll=list([5,6,8,None,None,10,None,None,9,None,7])
        #调用方法
        node=my.create_tree(input_list=ll)
        print('前序遍历')
        my.before_foreach(node)
        print('\n中序遍历')
        my.middle_foreach(node)
        print('\n后序遍历')
        my.after_foreach(node)

![4ddc50a04f674667962957d3834dc366.png][]

**2. 广度优先遍历**

广度优先遍历( Breadth First Search，BFS )也叫**层序遍历**，就是按照二叉树中的层次从左到右依次遍历每层中的结点。**层序遍历的实现思路是利用队列来实现**。

> 先将树的根结点入队，然后再让队列中的结点出队。队列中每一个结点出队的时候，都要将该结点的左子结点和右子结点入队。当队列中的所有结点都出队，树中的所有结点也就遍历完成。此时队列中结点的出队顺序就是层次遍历的最终结果。如下图所示：

![dc29ef6c38214e3ebf803e2ba181f60c.png][]

（1） 根节点1入队列

![16f2083fad8247d695a26b52c675751b.png][]

（2） 节点1出队，输出节点1，并得到节点1的左孩子节点2、右孩子节点3。让节点2和节点3入队。

![f7127cc14d074b70b2e29c1711c0480c.png][]

（3） 节点2出队，输出节点2，并得到节点2的左孩子节点4、右孩子节点5。让节点4和节点5入队。

![4eb881448aa64036ba74d3227b7f5f46.png][]

（4） 节点3出队，输出节点3，并得到节点3的右孩子节点6。让节点6入队。

![a19d2038e1a84395ad51a4520c73b9a2.png][]

（5）节点4出队，输出节点4，由于节点4没有孩子节点，所以没有新节点入队。

![cafbbf5350b4458f8d75fde156ab9465.png][]

（6）节点5出队，输出节点5，由于节点5同样没有孩子节点，所以没有新节点入队。

![3cecbfa91cfb4d439fe9b46b0211182e.png][]

（7） 节点6出队，输出节点6，节点6没有孩子节点，没有新节点入队。

![89eeb8b3070b4989878b46dbecd2b539.png][]

> #### 使用递归的方式来操作，如上图所示 ####

'''节点'''
    class TreeNode:
        '''初始化数据'''
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None
    
    '''层序遍历'''
    def level_order_traversal(root):
        # 判断节点为空
        if root is None:
            return []
        #数列
        result = []
        #队列
        queue = [root]
        #循环
        while queue:
            level = []  #层列
            #循环
            for _ in range(len(queue)):
                #第一个数据出队列
                node = queue.pop(0)
                #添加数据
                level.append(node.data)
                #判断左节点是否不为空
                if node.left is not None:
                    queue.append(node.left)
                # 判断左节点是否不为空
                if node.right is not None:
                    queue.append(node.right)
            #添加到列表中
            result.append(level)
        return result
    
    if __name__ == '__main__':
        #二叉树对象
        root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left.left = TreeNode(4)
        root.left.right = TreeNode(5)
        root.right.right = TreeNode(6)
    
        print(level_order_traversal(root))

![0f843e5da50d4975b785a9614d05f4f8.png][]

在实际应用中，二叉树又是使用最广泛的，特别是二叉树的几种遍历操作的规则，需要重点掌握。在面试或应试中，通常会根据前序、中序、后序中的两种序列，询问另外一种树的遍历结果。

[918b325d0a1c495ebd15a20cfa4ca20e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/410b5fd4d4554060a0c5f1507219e58d.png
[9f7352000e224988a7fee1684b8d9a47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6228c82f43d649b1961c73703bd26063.png
[cf90253a39aa4fe287a4e1d36df630e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/36fd459b38f94e2bb94323f62c600e3c.png
[5d5af676467e45a6ae4bc80d2c8ca50c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/f88ce7d89ce64b3ba49698066abf52be.png
[5715b7e8d59d4a528975612d07ee2f20.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/47b027d51d43406db977bd1c6ee7843a.png
[0b83e60ccc374e7f86a5a75e273264a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2c310f18cb884665861a39601f878805.png
[e887e2526e4c45fea6a2967755cc7480.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4730d6c48f804492b794e1840fbc709a.png
[403a9d4b51bb42889e8550393a6ecfec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d921fe1f381d430c95b666f63b46e73c.png
[Link 1]: https://so.csdn.net/so/search?q=%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1001.2101.3001.7020
[b63b22cca7314cc883c472fb01388ecd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/13c5d151c972497e8cc39aae535cf709.png
[88fdcf8648fc4088943b922f94518c6b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9999fffdd90445539efb5ad04f7f7649.png
[85c08962f1444fbba181a11f0b636ce2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/37c5b7f417314edd80b4b55cc3264473.png
[56a4708273cf46cbb017798285d8aa0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/df7e21c4a9c34ba7b58f8ebf18632fd7.png
[638ca1ee9711429d8e4f973ad96e2fc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5fdf265a667947acb031cf2df754edce.png
[a6d44f2b9d944be9abb53da1cd24fa83.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/496d395a3127429d9e57b01fb4e37c07.png
[5f36bd9add264ccf87e438f6d284610d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3ea31457cd2f493c85f8fdb026acc5b7.png
[4ddc50a04f674667962957d3834dc366.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9297264bdf9946b49435c9341e30e2c3.png
[dc29ef6c38214e3ebf803e2ba181f60c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9617a65e025a4ed38af8ddee1406b0f9.png
[16f2083fad8247d695a26b52c675751b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6a811eb1376b4d13a32d98f7c8c86a5b.png
[f7127cc14d074b70b2e29c1711c0480c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/62a26837f5b64497bb960a7796095b11.png
[4eb881448aa64036ba74d3227b7f5f46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/410b810fced143b2a67be82f8d901663.png
[a19d2038e1a84395ad51a4520c73b9a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/120ce5a7f9be4995b09cee46f54f0ab8.png
[cafbbf5350b4458f8d75fde156ab9465.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/13b5a95b820a4c0689b9e3a712557573.png
[3cecbfa91cfb4d439fe9b46b0211182e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/19d919ed40924735819e1ed51f54e0c3.png
[89eeb8b3070b4989878b46dbecd2b539.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/475871c3f5974e3ebdcf4bc632908f45.png
[0f843e5da50d4975b785a9614d05f4f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/54f77f933c044d7293d3c88a9d52f143.png