专栏首页T客来了打牢地基-二叉树、BST

打牢地基-二叉树、BST

章节

  • tree结构简介
  • 二叉树详解
  • 二分搜索树 - Binary Search Tree

1 tree结构简介

tree-简介

  1. tree 是非线性数据结构
  2. tree 是高效的

tree-高效性

2 二叉树详解

重新认识下tree

1. 和链表一样,动态的数据结构 
class Node { 
    E e; 
 Node left; 
 Node right; 
} 
2. 二叉树具有唯一根节点 
3. 二叉树中每个节点最多有两个孩子 - 左孩子 or 右孩子 
4. 1个孩子都没有的节点叫叶子节点 
5. 二叉树每个节点最多有一个父节点 
6. 根节点没有父节点 
7. 二叉树具有比链表更明显的递归属性
 

二叉树的天然递归属性

一个节点有n个分叉- n叉树

满二叉树

定义: 除了叶子节点,每个节点都有两个孩子节点

二叉树不一定是满二叉树

3 二分搜索树 - Binary Search Tree

1. 二分搜索树是二叉树
 
2. 二分搜索树每个节点的值:
 
 大于其左子树所有节点的值
 
 小于其右子树所有节点的值
 
 左子树(all node val) < cur node val < 右子树(all node val)
 
3. 每一棵子树也是二分搜索树
 

二分搜索树-BTS 加速查询过程的原因,假如根节点val = 28, 现在在查找 30 这个元素,因为BTS的存储特性,只需要查找右子树部分就可以了,大大提高了查询的速度 有个细节,需要保证node的val 是可比较的,这是有局限性的

3.1 定义树中节点-struct

class Node:
 
 def __init__(self, e=None, left=None, right=None):
 
        self.e = e
 
        self.left = left
 
        self.right = right
 

节点结构体中 包含数据域 e, 左子树引用 left, 右子树引用right

3.2 定义BTS

class BST:
 
 def __init__(self, root: Node = None):
 
 """
 
        根节点
 
        :param root:
 
        """
 
        self._root = root
 
        self._size = 0
 

一棵树包包含一个根节点root,以及node的个数 size

3.3 add(e)-递归新增一个节点数据

 def add(self, e):
 
        self._root = self._add_element(self._root, e)
 


 
 def _add_element(self, root, e):
 
 """
 
        递归构建二分搜索树
 
        :param root:
 
        :param e:
 
        :return:
 
        """
 
 if root is None:
 
            self._size += 1
 
 """
 
            返回的是子树根节点
 
            """
 
 return Node(e)
 
 elif e < root.e:
 
            root.left = self._add_element(root.left, e)
 
 elif e > root.e:
 
            root.right = self._add_element(root.right, e)
 
 return root
 

3.4 contains- 递归查询树中是否包含某个数据

 def contains(self, e):
 
 return self._contains(self._root, e)
 
 def _contains(self, _root, e):
 
 if self._root is None:
  return False
  
 if self._root.e == e:
 
 return True

 
 if e < self._root.e:
 
 return self._contains(self._root.left, e)
 
 if e > self._root.e:
 
 return self._contains(self._root.right, e)
 

3.5 二分搜索树的遍历

3.5.1 前序遍历 - 递归

def pre_order(self):
 
 """
 
        前序遍历
 
        :return:
 
        """
 
        self._pre_order(self._root)
 


 
 def _pre_order(self, node):
 
 if node is None:
 
 return
 


 
 print(node.e)
 


 
        self._pre_order(node.left)
 
        self._pre_order(node.right)
 

3.5.2 中序遍历-递归

 def in_order(self):
 
 """
 
        中序遍历,即是二分搜索树从小到达排序的数据
 
        :return:
 
        """
 
        self._in_order(self._root)
 


 
 def _in_order(self, node):
 
 if node is None:
 
 return
 


 
        self._in_order(node.left)
 
 print(node.e)
 
        self._in_order(node.right)
 

3.5.3 后序遍历 post_order - 递归

 def post_order(self):
 
 """
 
        后续遍历
 
        :return:
 
        """
 
        self._post_order(self._root)
 


 
 def _post_order(self, node):
 
 if node is None:
 
 return
 
        self._post_order(node.left)
 
        self._post_order(node.right)
 
 print(node.e)
 

3.5.4 前序遍历 - 非递归算法(栈的应用)- DFS 深度优先遍历

LinkedListStack-使用先前实现的链表栈

 def pre_order_nr(self):
 
 """
 
        前序遍历-非递归,使用栈
 
        :return:
 
        """
 
        stack = LinkedListStack()
 
        stack.push(self._root)
 
 while stack.is_empty() is False:
 
            cur = stack.pop()
 
 print(cur.e)
 
 if cur.right is not None:
 
                stack.push(cur.right)
 
 if cur.left is not None:
 
                stack.push(cur.left)
 

3.5.5 二分搜索树的层序遍历-(队列的应用) BFS (Breadth First Search)

LinkedListQueue-使用先前实现的链表队列实现层序遍历

 def level_order(self):
 
 """
 
        队列实现中序遍历 - 先进先出
 
        :return:
 
        """
 
        queue = LinkedListQueue()
 
        queue.enqueue(self._root)
 
 while queue.is_empty() is False:
 
            cur = queue.dequeue()
 
 print(cur.e.e)
 
 if cur.e.left is not None:
 
                queue.enqueue(cur.e.left)
 
 if cur.e.right is not None:
 
                queue.enqueue(cur.e.right)
 

编程的过程中会发现其实每一个节点都会被访问3次。

本文分享自微信公众号 - T客来了(ltdo11),作者:bofeng

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打牢算法基础,从动手出发!

    大家好,我是光城。算法在计算机领域的重要性,就不用我多说了,每个人都想要学算法,打牢算法基础,可是不知道如何做,今天我来推荐一波学习思路。

    公众号guangcity
  • 手把手刷二叉搜索树(第一期)

    前文「手把手刷二叉树系列」已经写了 第一期,第二期 和 第三期,今天写一篇二叉搜索树(Binary Search Tree,后文简写 BST)相关的文章,手把手...

    labuladong
  • 漫画:二叉树系列 第四讲(BST的查找)

    在上一节中,我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢?和普通的二叉树又有何不同?我们将在本节内容中进行学习!

    程序员小浩
  • 判断一棵满二叉树是否为二叉搜索树

    给定一棵满二叉树,判定该树是否为二叉搜索树,是的话打印 True,不是的话打印 False。

    echobingo
  • 基本算法|图解各种树(二)

    01 — 二叉搜索树 基本算法|图解各种树(一) 二叉搜索树,又称为二叉排序树,简写为 BST,它与线性表,链表,二叉树间的关系,二维链表近似是二叉树,BST继...

    double
  • 第38期:BST 的搜索(小白必看)

    在上一节中,我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢?和普通的二叉树又有何不同?我们将在本节内容中进行学习! 下面我们仍然通过例题进行讲解。

    程序员小浩
  • 野生前端的数据结构基础练习(7)——二叉树

    一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

    大史不说话
  • 原创 | 手把手刷二叉搜索树(第二期)

    我们前文 手把手刷二叉搜索树(第一期) 主要是利用二叉搜索树「中序遍历有序」的特性来解决了几道题目,本文来实现 BST 的基础操作:判断 BST 的合法性、增、...

    labuladong
  • 二叉排序树(BSTree)关于查找算法结合

    /*基于树的顺序查找法*/ /*二叉排序树的存储结构*/ typedef struct node { KeyType key; ...

    Steve Wang
  • 手把手带你刷通二叉搜索树(第三期)

    之前写了两篇手把手刷 BST 算法题的文章,第一篇 讲了中序遍历对 BST 的重要意义,第二篇 写了 BST 的基本操作。 本文就来写手把手刷 BST 系列的...

    labuladong
  • 美团面试官:你对二叉树后续遍历一无所知

    其实二叉树的题目真的不难,无非就是前中后序遍历框架来回倒嘛,但是对于有的题目,不同的遍历顺序时间复杂度不同。

    labuladong
  • 【43期】盘点那些必问的数据结构算法题之二叉树基础

    来自:juejin.im/post/5ba3bb52e51d450e942f3031

    良月柒
  • javascript进阶必备的二叉树知识

    每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于0-3年的前端程序员...

    徐小夕
  • 数据结构与算法-二叉排序树

    一棵二叉排序树(Binary Sort Tree)(又称二叉查找树)或者是一棵空二叉树,或者是具有下列性质的二叉树:

    越陌度阡
  • 打牢地基-拿下红黑树

    红黑树与2-3树的等价关系,理解2-3树和红黑树之间的关系 红黑树就很简单了 学习2-3树不仅对理解红黑树有帮助,对于理解B类树,也是有巨大帮助的:

    用户1081422
  • JS数据结构与算法-二叉树和二叉查找树

    ①先递归遍历左子树到尽头,将每一项push到一个数组中,先是得到这样的一个结果[56,22,10]。

    Ewall
  • [数据结构] 二叉搜索树的CURD(增删改查)操作

    对于二叉搜索树的查找指定元素、查找最大元素、查找最小元素、删除指定元素、插入元素等基础操作。除了删除操作外,基本上都是使用的非递归函数解决。

    泰坦HW
  • Treap——堆和二叉树的完美结合,性价比极值的搜索树

    Treap本质上也是一颗BST(平衡二叉搜索树),和我们之前介绍的SBT是一样的。但是Treap维持平衡的方法和SBT不太一样,有些许区别,相比来说呢,Trea...

    TechFlow-承志
  • C++版 - 剑指offer 面试题24:二叉搜索树BST的后序遍历序列(的判断) 题解

    题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。

    Enjoy233

扫码关注云+社区

领取腾讯云代金券