二叉树的深度优先遍历与广度优先遍历

先说说为什么要遍历,二叉树不是已经排好序了么?如果大于当前节点值,搜索右子树,小于当前值,继续搜索左子树。 参考两个sql: select id,name,grade from student where id=1 select id,name,grade from student where name='李四'

  • 按id查找,id是主键,已经创建索引,用二叉树存储,id就是二叉树节点的key,可以按照二分查找法搜索。
  • 按name搜索,只能采用遍历的方法,必须保证检查到树上的每一个节点,不能有遗漏。

数据库创建索引,可以加快搜索速度,但要维护额外空间。

深度优先遍历

先遍历子节点,再遍历兄弟节点。 从根节点开始递归,如果存在子节点,继续遍历子节点。

    def traverse_d(self):
        self._traverse_d(self.root)
        
    ##深度优先遍历
    def _traverse_d(self,node):
        if(node == None):
            return
        self._traverse_d(node.lnode)
        self._traverse_d(node.rnode)
        print("key:%d==>value:%d"% (node.key,node.value))

广度优先遍历

先遍历兄弟节点,在遍历子节点。 采用队列实现,出队时添加子节点。

    def traverse_w(self):
        self._traverse_w(self.root)
    ## 广度优先遍历
    def _traverse_w(self,node):
        q = Queue()
        q.put(node)
        while(not q.empty()):
            node = q.get()
            if(node.lnode!=None):
                q.put(node.lnode)
            if(node.rnode!=None):
                q.put(node.rnode)
            print("key:%d==>value:%d"% (node.key,node.value))

总结:

以作者的自身经历,二叉树的深度遍历比较好记,总是忘如何实现广度优先,后来记住一个诀窍,广度优先要有一个队列,就记住了。放个图,加深一下记忆。

队列

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

C语言程序设计教程(第三版)课后习题6.3

题目描述 求Sn=a+aa+aaa+…+aa…aaa(有n个a)之值,其中a是一个数字,为2。 例如,n=5时=2+22+222+2222+22222,n由键盘...

281120
来自专栏计算机视觉与深度学习基础

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth larg...

228100
来自专栏Java学习网

Java中三种Set类型用法、性能大比拼

Java为开发者提供了大量的工具类,这给开发人员带来了很大方便,但是选择多了也有困扰,究竟用哪个类;我想选择什么,一是看自己具体需求,二是类本身的性能和用法;J...

88760
来自专栏小灰灰

JDK容器学习之List: CopyOnWriteArrayList,ArrayList,LinkedList对比

列表 List, ArrayList, LinkedList, CopyOnWriteArrayList, Vector 简述 1. 列表划分为线程安全和线程...

219100
来自专栏项勇

笔记72 | 将姓放在名的后面,排序按姓氏首字母排列的修改笔记

19550
来自专栏java思维导图

【一分钟知识】HashSet和TreeSet,HashMap与HashTable

java思维导图 xmind导图配合精美文章,可视化学习,让java不再难懂。 ? ? HashSet和TreeSet HashSet 哈希表实现的,HashS...

37070
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

322120
来自专栏数据结构与算法

洛谷P3380 【模板】二逼平衡树(树套树)

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

30130
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

22480
来自专栏Java编程

Java HashMap那点事

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

43500

扫码关注云+社区

领取腾讯云代金券