野生前端的数据结构基础练习(7)——二叉树

网上的相关教程非常多,基础知识自行搜索即可。 习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。 参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/btree

一.二叉树的基本知识

基本概念

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称为,二叉树每个节点的度只能是0,1,2中的一个,度为0的节点称为叶节点

基本特点

二叉查找树是一种特殊的二叉树,其插入查找和删除都非常高效。

二.基本练习

  1. 实现二叉查找树(BST) TIP:BST在插入数据时的逻辑,本身就是一种二分法思维。
  2. 树的遍历 TIP:树的遍历一般分为先序遍历,中序遍历,后序遍历,这里的序是指对于一个节点以及它的左子节点和右子节点的访问次序。具体使用场景的例子包括:先序遍历时,可以用于查看树结构,中序遍历,可以用于显示排序结果,后序遍历,可用于计算目录内文件占用的数据大小。
  3. 值的查找 3.1查找给定值 TIP:实际上就是二分法查找 3.2查找最小值 TIP:BST中最左侧的节点。 3.3查找最大值 TIP:BST中最右侧的节点。
  4. 删除节点 TIP:主要注意删除同时包含左右孩子节点的节点时逻辑,由BST插入的规则可以知道,节点右子树中所有的节点都是大于当前节点值的,所以右子树中找出的最小值是大于当前节点左子树上所有值的,所以将其上浮至当前待删除节点位置,是不影响二叉树特性的。
  5. 计数

三.课后习题(书中第十节习题)

  1. BST增加一个新方法,返回BST中节点个数。
  2. BST增加一个新方法,返回BST中边的个数。
  3. BST类增加一个新方法max( ),返回最大值。
  4. BST类增加一个新方法min( ),返回最小值。
  5. 写一段程序,读入一个较大的文本文件,并将其中的单词保存到BST中,显示每个单词出现的次数

四.习题思路

  1. BST构造函数中增加一个count属性,在增删节点成功时修改count值实现计数即可。
  2. BST边的数量比节点数量少1.
  3. (略)
  4. (略)
  5. 分解出的单词实际上就是字符串,字符串的比较实际上就是从第一位开始逐个比较ASCII码,用上面实现的BST做练习就好,词频统计更多会用到Trie树,也就是字典树,感兴趣的读者可以自行查阅。

五. 根据遍历序还原二叉树

【先序+中序】或者【后序+中序】都可以还原出唯一的二叉树,只根据【先序+后序】还原出的二叉树不是唯一的(感兴趣的可以看看这篇《 为什么只给出前序和后序,不能唯一确定一个二叉树 》),这里的二叉树指的是一般二叉树,不是二叉搜索树。或者相关的文章已经很多了,随手贴一篇带图的《由遍历序列还原二叉树结构》,理解难度并不高,同样建议自己编码实现一下。

六. 关于二叉树

二叉树是非常重要的数据结构,书中介绍的只是最基本的知识,更进一步的学习会涉及二叉树的数学特性,限制更多性能也更优的平衡二叉树,满二叉树,红黑树等等,以及相关的深度优先和广度优先算法,路还很长,静下心慢慢走。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

32660
来自专栏数据处理

leetcode222求完全二叉树节点个数

38040
来自专栏IT笔记

ArrayList和LinkedList的区别

首先来看ArrayList和LinkedList的集成类和接口的区别。 public class ArrayList<E> extends AbstractLi...

33280
来自专栏Java 源码分析

二叉树

1.二叉树的性质 1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点 2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点 3.度...

28040
来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

9930
来自专栏coolblog.xyz技术专栏

TreeMap 源码分析

TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 ...

63090
来自专栏向治洪

基本数据结构概念

一、线性结构 顺序存储线性表:将元素依次存储在地址连续的存储单元中,物理上相邻; 链式存储线性表:将元素按照逻辑顺序链接在依次,不要求地址连续; ...

20660
来自专栏fangyangcoder

leetcode(二)

给定一个二叉数(root),二叉树中一个node(target)以及整数K,求二叉树中所有与target距离K的节点值。问题描述与example如下。

15120
来自专栏木子昭的博客

明星程序员被Google挂掉的故事

首先要提一个软件Homebrew Homebrew可能是Mac上最好用的包管理器, 地位相当于Ubuntu的apt, 也相当于命令行版的AppStore ? ...

38550
来自专栏C/C++基础

二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

二叉树是一类简单而又重要的树形结构,在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构,简单的逻辑,广泛的应用和大量的指针操作,在面试过程屡见不鲜,快...

1.7K10

扫码关注云+社区

领取腾讯云代金券