大家懂二叉树吗？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 3483 天前的主题，其中的信息可能已经有所发展或是发生改变。

首先：** 申明，我不是看到二叉树招聘门** 发这个主题的。

是在解决问题的时候，看到[数据结构]这本书，看到二叉树这个概念，我是菜鸟，这才知道二叉树是数据结构。所以我想问问，二叉树是必须学会的知识吗？他在我们的日常编程中有很大作用吗？

结构

申明

编程

46 条回复 • 2015-06-16 16:23:25 +08:00

unionx

2015-06-15 10:42:01 +08:00

是基础知识

lecher

2015-06-15 10:49:40 +08:00

简单的说,数据结构和算法这类的基础知识,看起来在开发的时候是没什么用处的,因为很多框架和库都封装好了,可以直接拿来用.
但是基础扎实的人debug和基础不扎实的人debug能力可以差出很远很远.
单纯是拿到需求再写代码的阶段,这些技术知识没多大用处的感觉,但是真的到了需要自己去构建业务的实现逻辑和代码的结构的时候,这些知识就很有用处了.
同样的业务,两个方案哪个效率高,那个方便管理,为什么?
因为数据结构和算法这类的基础知识,其实都是计算机领域的思维方式,如果不了解这些计算机的思维方式,出了问题就没办法去分析了.

redhatping

2015-06-15 10:52:08 +08:00

@lecher 经典～～～必须关注你

binux

2015-06-15 10:52:47 +08:00

比如 DOM 就是一棵树

est

2015-06-15 11:06:09 +08:00

不要说二叉树了，会写链表都可以鄙视ruby圈子一大波人了 https://github.com/rubygems/rubygems/pull/1188

101

2015-06-15 11:14:18 +08:00

数据结构基础知识，哪本数据结构不讲，别闹

21grams

2015-06-15 11:17:27 +08:00

其实没啥用，写了这么多年程序，还真没发现哪里要用到树结构。

yueyoum

2015-06-15 11:30:18 +08:00

最近这事闹的这么大，周末赶紧用C写了 binary search tree 来压压惊！

顺便写了写四叉数

zonghua

2015-06-15 11:37:27 +08:00

@binux 但是感觉比用C写的好理解得多。用上指针我脑袋就昏了。

Andiry

2015-06-15 11:54:46 +08:00

基本的二叉树没啥用。有用的是平衡二叉树

XadillaX

2015-06-15 11:56:34 +08:00

基础而已，不会的话不是不能写代码，只是基本功不扎实而已。

loading

2015-06-15 12:01:19 +08:00 via Android

不知道这究竟是什么

otakustay

2015-06-15 12:05:05 +08:00

二X树我能写，但二B树我真写不来，大学时被这个折磨得要死要死的……

mouhong

2015-06-15 12:25:58 +08:00

开发框架/类库型的产品时，知道一下应该是会有帮助的，至少当你在使用基础库提供的现成实现时，对它们的时空复杂度会有一定的概念，要不然面对链表和平衡树(都是实现好的)时，就不知道怎么选择咯~~

不过现在要是让我写出一个红黑树出来，我是真的不会写，但要是有 Google，查查应该也是可以写得出来。不过不要误解，我不引以为荣，我还是觉得算法很重要，倒不是说要把某些特定的算法背下来(我想这永远背不完，不同领域有不同的算法)，我觉得更多的是通过学习来培养算法设计能力，所以我也准备找个时间再好好学习一下的 (太惭愧也有点后悔，大学睡了一年，翘了两年)

yaqink

2015-06-15 12:41:49 +08:00 via iPad

不懂。
數據結構還是在費腦筋解決一個問題之後，自己才意識到，原來使用不同數據類型，可以減輕大量的工作量。
然而一牽扯到各種算法，自己就懵了。
基本功不扎實的我，需要學。
然而學校算法課講師連基本數據類型都不說w

yxzblue

2015-06-15 13:03:51 +08:00

红黑树算不算

0x61

2015-06-15 13:05:53 +08:00 via iPhone

二叉树是离散数学里面的，楼主可以去看离散数学，里面说的很详细

hahasong

2015-06-15 13:53:52 +08:00

不知道，还是最近看新闻才知道的，找本书了解了一下，业务开发中完全用不到，无所谓了

ibcker

2015-06-15 13:58:56 +08:00

听过，哈哈

aphantee

2015-06-15 14:19:21 +08:00

必须学，因为这是一个最经典、最简单的展现如何以几何速度降低运算复杂度的范例。

likuku

2015-06-15 14:31:50 +08:00

想象成原子核裂变反应吧。

bramblex

2015-06-15 14:38:31 +08:00

@est

Ruby圈子里很多人基本功真是太差了……

est

2015-06-15 14:46:48 +08:00

@bramblex 这个事情希尔伯特也做过。他的名言是：“我们大哥廷根，街上随便一个十七八岁的孩子懂得四维几何知识都比爱因斯坦多”。

然而发明相对论的只能是老爱，搞出Rails的也只有Ruby一家。

nowcoder

2015-06-15 14:54:54 +08:00

@21grams 以前写输入法用了字典树，思路一样的。

Heartwork

2015-06-15 15:19:45 +08:00

以前写过树的几种数据结构，简单讲，这玩意用处不如hash那么糙快猛，也不如hash用的广。

以前用过的使用树的场景：
数据库索引（B+树）
业务系统内部的一个查找非常频繁但是非常少修改的结构（BBT）
自己写的类lisp解释器（AST）

bramblex

2015-06-15 15:29:31 +08:00

@est 嗯啊，对的。但是基础扎实个人觉得还是很重要的啦。没必要以偏概全的说 OwO

akira

2015-06-15 17:26:10 +08:00

如果你的工作不需要用到2叉树，那说明你不需要懂这玩意。

当然，常规的数据结构和算法，个人建议还是多少学一下吧。

some0ne

2015-06-15 17:35:37 +08:00

@est 我来打脸，首先那个PR基本没链表什么事，然后那段代码后来又被改回来了。
https://github.com/rubygems/rubygems/pull/1202

shakoon

2015-06-15 17:37:35 +08:00

看来本站半路出家的码农很多啊

sciooga

2015-06-15 18:23:08 +08:00 via Android

当初为了弄清楚自己一个对压缩数据的想法看了一堆资料就懂这个了

blackbeans

2015-06-15 18:29:41 +08:00

面试问过很多人关于二叉树的问题，基本都不会写.......几年工作经验的都有

jacob

2015-06-15 18:43:15 +08:00

是知识不？
是。

应该掌握不？
应该。

有用没？
有用。

你能用上不？
用不上。

wingoo

2015-06-15 19:14:21 +08:00

忘了差不多了, 不过大学里数据结构是全部都写过的
现在看看定义, 试了下还是能写出来的:)

dallaslu

2015-06-15 19:48:30 +08:00

如何判断某个集合中是否包含某元素？

最笨的办法是循环比较。

如果该集合中包含42亿个元素，需要比较多少次？

Java 中的 HashSet 只需要比较32次，因为应用了二叉树。

WispZhan

2015-06-15 20:08:08 +08:00

毕业前，基本无任何压力。
毕业后……，你能不翻书记得几个就说明：
1.要么你长期记忆力好；
2.要么你经常看，经常用，从事的是高端算法研究或者数学研究；
3.要么经常刷题或刚刚参加面试；
4.要么你经常/最近主持面试；
………………

目前的高级语言基本上常用数据结构的都有现成封装与抽象接口。

WispZhan

2015-06-15 20:10:13 +08:00

@WispZhan 忘记说了。如果你从事c/c++ 开发，那么这必须是你的会的。

zhyu

2015-06-15 20:16:58 +08:00

@dallaslu HashSet 用的不是哈希表么。。或者你想说 TreeSet? TreeSet 用的倒是红黑树

jedihy

2015-06-15 21:33:27 +08:00 via iPhone

工作用不到二叉树说明你们业务并不偏重于数据结构相关的东西，并且瓶颈也不在这一块。在大部分底层，或者说内核开发里面都用到了二叉树，其实一般是红黑树。你的linux系统基本上时时刻刻都在查询或者增删一颗二叉树，只是你察觉不到。

dallaslu

2015-06-15 21:42:00 +08:00

@zhyu 可以从添加元素的方法开始看源码，用到了红黑树。不过你这么一说，我有点不确定我说的是 HashSet 还是 HashMap 了……

sydneyzh

2015-06-15 21:43:15 +08:00

主要是锻炼逻辑思考能力。这比死记硬背条条框框其实要不容易。面试考这些，换句话说就是考人的聪明程度。很多人其实是“背”程而不是编程，遇到这种题目就比较痛苦。所以这样就达到了刷人的目的。

caoyue

2015-06-15 21:57:39 +08:00

记得之前在博客园看到过一篇文章
大概是讲有个年纪很大的大叔自学编程，为了一个程序用各种土办法自己优化了很长时间
最后找到一个程序员，告诉他用 HashTable，一下就解决了他的问题

有什么用呢，对知道的人来说，也许会有用
对不知道的人来说，肯定没用

sdcg1994

2015-06-15 22:23:03 +08:00 via iPhone

二叉树在金融数学里面应用很广泛的

Septembers

2015-06-16 09:39:20 +08:00 via Android

算法/设计模式学习的不是实现而是思路

Septembers

2015-06-16 09:46:30 +08:00 via Android

@otakustay B tree / B+ tree / B* tree / Bx tree

wizardoz

2015-06-16 13:06:33 +08:00

有的东西吧，当你不懂的时候你觉得没啥用。
学会了你就发现太有用了。
41楼举的例子很好，我想表达的大概就是这个意思。

williamx

2015-06-16 16:23:25 +08:00

这个事情是这样的：如果你不觉得有用，那就是没什么用——大抵如此。