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

42次阅读

共计 2412 个字符，预计需要花费 7 分钟才能阅读完成。

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

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

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 
    ...