数据结构与算法（c 描述）-k8凯发旗舰

讲解第7章的内容 220-235页

重点理解:

1、线性表、散列表、树表的各种查找技术

2、折半查找判定树

3、平衡二叉树的调整方法

重点: 二叉排序树、折半查找算法

难点: 平衡二叉树

师说:

本周讲述的查找二叉树是不少企业面试题的热点，而平衡二叉树是第七章的重点和难点，这里提供几个题目、讲解视频给各位进行了解和复习所用。

查找二叉树的几道面试题

1、判断一个单词是否拼写正确；

直接将所有单词入搜索二叉树，判断单词是否正确时只需搜索二叉树中是否存在该单词即可。

2、请模拟实现一个简单的中英互译的字典；

本题利用搜索二叉树的key、value模式。如果是英译汉时，key存放英文，value存放中文，再根据英文找到结点所在，查找结点的value即可得到中文；英译汉时，key存放中文，value存放英文，再根据中文找到结点所在,查找结点的value即可得到中文。

3、log文件中有许多异常重复的ip地址，请统计出每个异常ip出现了多少次。

也是利用搜索二叉树的key、value模式。key存放异常ip，而value为int计数，每找到一个将该ip所在的结点的value加1，最后遍历每个结点的value即可得到每个异常ip出现的次数。

1、平衡二叉树的概念

2、平衡二叉树的调整

3、平衡二叉树的练习

推荐阅读:

1.

2.实时搜索的现实需求与发展应用问题浅析

3.漫画:什么是二分查找