野生前端的数据结构基础练习（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树，也就是字典树，感兴趣的读者可以自行查阅。

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

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

六. 关于二叉树

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