乐趣区

关于ide:扫盲数据结构-二叉树入门

什么是二叉树

有一个根节点 向下扩大两个子节点 两个子节点又能够向下扩大。相似于这样的构造成为二叉树

<img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318164309773.png” alt=”image-20200318164309773″ style=”zoom:50%;” />

下面这种就够就是二叉树,当然有二叉树就有三叉树、四叉树。

<img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318164534883.png” alt=”image-20200318164534883″ style=”zoom:50%;” />

树中相应节点的概念

<img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318165011873.png” alt=”image-20200318165011873″ style=”zoom:50%;” />

  • A 节点是 B 节点的【 父节点
  • B 节点是 A 节点的【 子节点
  • B、C、D 这三个节点的父亲节点是同一个节点,所以他们之间互称为【 兄弟节点
  • E 节点没有父亲节点,所以咱们把它称为【 根节点
  • G、H、I、J、K、L 没有子节点,所以咱们把它称为【 叶子节点
  • 节点的高度:节点到叶子节点的最长门路
  • 节点的深度:根节点到这个节点所经验的节点个数
  • 节点的层数:节点的深度 + 1

二叉树的品种

在二叉树之上,具备各种各样的其余属性,就会衍生出其余的树结构。

  • 满二叉树

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318170240608.png” alt=”image-20200318170240608″ style=”zoom:50%;” />

    叶子节点全都在最底层,除叶子节点外,每个节点都有两个子节点,这种二叉树叫做【 满二叉树 】。

  • 齐全二叉树

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318170532465.png” alt=”image-20200318170532465″ style=”zoom:50%;” />

    叶子节点都在最底下两层,最初一次的叶子节点都靠左排列,并且除了最初一层,其余层的节点个数都要达到最大,这种二叉树叫做【 齐全二叉树

  • 二分搜寻树

    <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318171007366.png” alt=”image-20200318171007366″ style=”zoom:50%;” />

    若任意节点的左子树不为空,则左子树上所有节点的值均小于它的根节点的值;

    若任意节点的右子树不为空,则右子树上所有节点的值均大于或等于它的根节点的值;

    任何左子树或右子树也都为二分搜寻树。

  • <img src=”https://gitee.com/xiaoxiunique/picgo-image/raw/master/atips/image-20200318195545250.png” alt=”image-20200318195545250″ style=”zoom:50%;” />

    堆就是用数组实现的二叉树,所以它没有应用父指针或子指针。堆依据堆属性来排序。

    堆的罕用办法

    构建优先队列、反对堆排序、反对找出一个汇合中最小值(或者最大值)

    堆分为两种:最大堆和最小堆,两者的差异在于节点的排序形式。

    在最大堆中,父节点的值每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。

  • AVL
  • 红黑树
  • 线段树
  • 字典树
  • 并查集

树的遍历

  • 前序 根左右
  • 中序 左根有
  • 后序 左右根
  • DFS 深度优先遍历

    代码模板(递归写法)

    visited = set() 
    
    def dfs(node, visited):
        if node in visited: # terminator
            # already visited 
            return 
    
        visited.add(node) 
    
        # process current node here. 
        ...
        for next_node in node.children(): 
            if next_node not in visited: 
                dfs(next_node, visited)

    非递归写法

    def DFS(self, tree): 
    
        if tree.root is None: 
            return [] 
    
        visited, stack = [], [tree.root]
    
        while stack: 
            node = stack.pop() 
            visited.add(node)
    
            process (node) 
            nodes = generate_related_nodes(node) 
            stack.push(nodes) 
    
        # other processing work 
        ...
  • BFS 广度优先遍历(层序遍历)

    代码模板

    def BFS(graph, start, end):
        visited = set()
        queue = [] 
        queue.append([start]) 
    
        while queue: 
            node = queue.pop() 
            visited.add(node)
    
            process(node) 
            nodes = generate_related_nodes(node) 
            queue.push(nodes)
    
        # other processing work 
        ...

本文由博客群发一文多发等经营工具平台 OpenWrite 公布

退出移动版