数据结构-非线性结构-树形结构：有序树 ----＞二叉树【动态数据结构】

谁践踏了优雅 2023-10-04 12:29 15阅读 0赞

**二叉树**是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

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

## 一、二叉树的特性 ##

*  性质1: 在二叉树的第i层上至多有2(i-1)个结点（i>0）
 *  性质2: 深度为k的二叉树至多有2(k-1)个结点（k>0）
 *  性质3: 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2\+1;
 *  性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)
 *  性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

## 二、二叉树的种类 ##

### 1、完全二叉树 ###

> **完全二叉树**：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树。

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

### 2、满二叉树 ###

> **满二叉树**：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树，每一层都挂满了节点。

![在这里插入图片描述][20201027140833323.jpg_pic_center]

### 3、平衡二叉树 ###

> **平衡二叉树**（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树

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

### 4、搜索/排序二叉树 ###

> **排序二叉树**（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树），排序二叉树包含空树。

排序二叉树(BST)的要求:

1.  若左子树不空，则左子树上所有节点的值均小于它的根节点的值
2.  若右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.  左、右子树也分别为二叉搜索/排序树  
    ![在这里插入图片描述][20201027141521768.jpg_pic_center]

### 5、二分搜索树、AVL树（平衡二叉树）、红黑树（准平衡二叉树） 性能对比 ###

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

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

### 1、顺序存储 ###

**顺序存储**：将数据结构存储在固定的数组中，虽然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树  
存储方式.二叉树通常以链式存储。

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

### 2、链式存储 ###

**链式存储**：由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2。

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

## 四、二叉树-代码实现 ##

class Node(object):
     	"""二叉树节点"""
        def __init__(self, item):
            self.elem = item
            self.lchild = None
            self.rchild = None
    
    class BinaryTree(object):
        """完全二叉树"""
    
        def __init__(self, node=None):
            self.root = node
    
        def add(self, item):
            """添加节点"""
    
            if self.root is None:
                self.root = Node(item)
                return
    
            # 队列
            queue = [self.root]
            # 从尾部添加数据
    
            while True:
                # 从头部取出数据
                node = queue.pop(0)
                # 判断左节点是否为空
                if node.lchild is None:
                    node.lchild = Node(item)
                    return
                else:
                    queue.append(node.lchild)
    
                if node.rchild is None:
                    node.rchild = Node(item)
                    return
                else:
                    queue.append(node.rchild)

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

> **树的遍历**：是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。

> 树的两种重要的遍历模式是：**深度优先遍历**和**广度优先遍历**。深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

### 1、广度优先遍历 ###

> **广度优先遍历**：从树的root开始，从上到下从从左到右遍历整个树的节点

### 2、深度优先遍历 ###

> **深度优先搜索**(Depth First Search)：对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。

三种深度优先遍历方式：

*  先序遍历（preorder）：根 左 右
 *  中序遍历（inorder）：左 根 右
 *  后序遍历（postorder）：左 右 根  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 7]  
    根据深度遍历结果反推二叉树的结构：由**中序遍历&先序遍历** 或者 **中序遍历&后序遍历** 的遍历结果就可以推出二叉树的结构  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 8]

### 3、二叉树遍历的代码实现 ###

class Node(object):
        """节点类"""
        def  __init__(self, item):
            self.item = item
            self.lchild = None
            self.rchild = None
    
    
    class BinaryTree(object):
        """完全二叉树"""
        def __init__(self, node=None):
            self.root = node
    
        def add(self, item):
            """添加节点"""
    
            if self.root == None:
                self.root = Node(item)
                return
    
            # 队列
            queue = []
            # 从尾部添加数据
            queue.append(self.root)
    
            while True:
                # 从头部取出数据
                node = queue.pop(0)
                # 判断左节点是否为空
                if node.lchild == None:
                    node.lchild = Node(item)
                    return
                else:
                    queue.append(node.lchild)
    
                if node.rchild == None:
                    node.rchild = Node(item)
                    return
                else:
                    queue.append(node.rchild)
    
        def breadh_travel(self):
            """广度优先遍历"""
    
            if self.root == None:
                return
    
            # 队列
            queue = []
            # 添加数据
            queue.append(self.root)
    
            while len(queue)>0:
                # 取出数据
                node = queue.pop(0)
                print(node.item, end="")
    
                # 判断左右子节点是否为空
                if node.lchild is not None:
                    queue.append(node.lchild)
                if node.rchild is not None:
                    queue.append(node.rchild)
    
        def preorder_travel(self, root):
            """先序遍历 根 左 右"""
            if root is not None:
                print(root.item, end="")
                self.preorder_travel(root.lchild)
                self.preorder_travel(root.rchild)
    
        def inorder_travel(self, root):
            """中序遍历 左 根 右"""
            if root is not None:
                self.inorder_travel(root.lchild)
                print(root.item, end="")
                self.inorder_travel(root.rchild)
    
        def postorder_travel(self, root):
            """后序遍历 根 左 右"""
            if root is not None:
                self.postorder_travel(root.lchild)
                self.postorder_travel(root.rchild)
                print(root.item, end="")
    
    
    if __name__ == '__main__':
        tree = BinaryTree()
        tree.add("0")
        tree.add("1")
        tree.add("2")
        tree.add("3")
        tree.add("4")
        tree.add("5")
        tree.add("6")
        tree.add("7")
        tree.add("8")
        tree.add("9")
        tree.preorder_travel(tree.root)
        print()
        tree.inorder_travel(tree.root)
        print()
        tree.postorder_travel(tree.root)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210503204555296.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201027141055460.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20201027140833323.jpg_pic_center]: https://img-blog.csdnimg.cn/20201027140833323.jpg#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201027141310939.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20201027141521768.jpg_pic_center]: https://img-blog.csdnimg.cn/20201027141521768.jpg#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210512184159316.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201027142020883.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/2020102714215823.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201027142946267.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201027145329761.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/2020102714564572.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center