数据结构与算法全套精讲(python版) (六)树

女爷i 2021-12-14 00:19 234阅读 0赞

**1. 树的术语**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70][]

**2. 树的种类 **

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1][]

(1). 完全二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2][]

(2). 满二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3][]

(3).  二叉排序树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5][]

**3. 树的存储**

(1). 顺序存储(非主流)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6][]

(2) . 链式存储

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7][]

**4 . 树的常见应用场景**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8][]

**5. 二叉树性质**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 9][]

** **

**6. 二叉树遍历**

广度遍历(层次)：一层一层的走，每层从左至右；

深度遍历：先序遍历(根节点—>左子树—>右子树)，中序遍历(左子树—>根节点—>右子树)，后序遍历(左子树—>右子树—>根节点)。

例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 10][]

遍历实现：

class Node(object):
        def __init__(self,data):
            self.data = data
            self.lchild = None
            self.rchild = None
    
    class Tree(object):
        def __init__(self):
            self.root = None
    
        def add(self,item):#插入节点
            node = Node(item)
            'bool([])==False, bool([None])==True'
            if self.root == None:#当根节点None，[self.root]即[None]
                self.root = node
                return
            queue = [self.root]#二叉树以list形式存储
            while queue:#从根开始，依次往下检查各节点，直至全取出
                cur = queue.pop(0)#每轮把list现有的首节点取出
                if not cur.lchild:
                    cur.lchild = node
                    return
                else:
                    queue.append(cur.lchild)
                if not cur.rchild:
                    cur.rchild = node
                    return
                else:
                    queue.append(cur.rchild)
        '广度遍历'
        def breadth_travel(self):#层次遍历
            'bool([])==False, bool([None])==True'
            if self.root == None:#当根节点None，[self.root]即[None]
                return
            queue = [self.root]#二叉树以list形式存储
            while queue:#从根开始，依次往下检查各节点，直至全取出
                cur = queue.pop(0)#每轮把list现有的首节点取出
                print(cur.data,end=' ')
                if  cur.lchild:
                    queue.append(cur.lchild)
                if  cur.rchild:
                    queue.append(cur.rchild)
    
        '深度遍历'
        def preorder(self,node):#前序遍历
            if not node:
                return
            print(node.data,end=' ')
            self.preorder(node.lchild)
            self.preorder(node.rchild)
    
        def inorder(self,node):#中序遍历
            if not node:
                return
            self.inorder(node.lchild)
            print(node.data, end=' ')
            self.inorder(node.rchild)
    
        def postorder(self,node):#后序遍历
            if not node:
                return
            self.postorder(node.lchild)
            self.postorder(node.rchild)
            print(node.data,end=' ')
    
    
    if __name__ == '__main__':
        tree = Tree()
        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.breadth_travel()
        print('')
        tree.preorder(tree.root)
        print('')
        tree.inorder(tree.root)
        print('')
        tree.postorder(tree.root)
        print('')

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 11][]

**7.  由一直遍历反推出这棵树**

在深度遍历里，已经两种遍历则可退出该树，且其中一种必须是中序遍历。

例1：已知先序遍历为0 1 3 7 8 4 9 2 5 6  ，中序遍历为7 3 8 1 9 4 0 5 2 6 ，请画出该二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 12][]

例2：已知后序遍历为7 8 3 9 4 1 5 6 2 0   ，中序遍历为7 3 8 1 9 4 0 5 2 6 ，请画出该二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 13][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]: /images/20211213/d6976b760ef04050959fb8e17f8fd47a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]: /images/20211213/12c5263f99eb417d92f1510ef1e3f245.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2]: /images/20211213/9ea1423185334f33ae918cd9fd5f273e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3]: /images/20211213/44d5f24d20084fae8f7098cda07c2c55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4]: /images/20211213/5f03f5e4f287437bbd6d54381449a295.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5]: /images/20211213/49afdf4aefc544fa8cdb0cdd0909b36e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6]: /images/20211213/a32ebc14e55048bc83af1447fb83ffb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7]: /images/20211213/64496e6a53274b1cb50641c4c98a2826.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8]: /images/20211213/d513cb4e02e04dbab7f1e8078741a459.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 9]: /images/20211213/401e920f9a9d41eebc07f2f54554707f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 10]: /images/20211213/a7f35e661e9e490fa6cac37811a2530f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 11]: /images/20211213/3b731702f6724fd0a2d2415805fc2f5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 12]: /images/20211213/d2b7ea95d6694d87abcd3e4d587e56b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 13]: /images/20211213/a35f271bcbb2475287b9023f3f85b2a6.png