数据结构----树，引言

太过爱你忘了你带给我的痛 2023-03-01 06:02 2阅读 0赞

欢迎来到“树”这一章节。这里的树不是自然界的植物，而是一种新的数据结构。从这一章开始，我们要真正开始学习比较复杂的数据结构以及相关的算法了。

树这种数据结构有什么用？其实很多情况下，我们用数组、链表、以及队列和栈这些简单的数据结构就可以实现我们需要的功能了，根本没必要用树。但是这些简单的数据结构往往意味着较低的效率，如果用树实现相同的功能，效率就会有巨大的提升。这就是树的最大价值。不信？我们举几个例子。  
在第三章“查找”中，我们仔细讲解了“二分查找”。例如对于1~10这10个数据，如果采用顺序查找，最差的情况下需要查找10次才能找到目标数据，时间复杂度为O(N)，但是如果使用“二分查找”，最多只需要查找4次，时间复杂度为O(logN)。随着数据量的增大，这种优势急剧扩大。例如10个数据时，“二分查找”最差情况的效率是“顺序查找”的2.5倍，100个数据时，效率是15倍，1000个数据时，效率是100倍，10000个数据时，效率是752倍，100000个数据时，效率是6020倍。。。。。。相同的电脑，相同的数据，采用不同的算法，一台电脑可能早就运行完成在休息了，另一台电脑却还在“呼哧呼哧”的跑着呢。。。这里的“二分查找”就是用到了二叉树的概念。

第二个例子：在考试中，学生的成绩分布大致是这样：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
如果有100个学生，现在我们要对每个学生的成绩进行评级，我们该怎么写代码。很简单，就按照上面的表格进行编写即可：

if(score >= 90) level = “优”;
    else if(score >= 80) level = “良”;
    else if(score >= 70) level = “中”;
    else if(score >= 60) level = “及格”;
    else if(score < 60) level = “不及格”;

我们计算一下，这个代码一共需要判断多少次。  
获得“优”的学生一共10人，每人判断1次，一共判断10次。  
获得“良”的学生一共20人，每人判断2次，一共判断40次。  
获得“中”的学生一共40人，每人判断3次，一共判断120次。  
获得“及格”的学生一共20人，每人判断4次，一共判断80次。  
获得“不及格”的学生一共10人，每人判断5次，一共判断50次。  
所以总共需要判断300次。

我们只是把代码的次序稍微调整一下，再来计算一共需要判断多少次。

if(score >= 70) level = “中”;
    else if(score >= 80) level = “良”;
    else if(score >= 60) level = “及格”;
    else if(score < 60) level = “不及格”;
    else if(score >= 90) level = “优”;

获得“中”的学生一共40人，每人判断1次，一共判断40次。  
获得“良”的学生一共20人，每人判断2次，一共判断40次。  
获得“及格”的学生一共20人，每人判断3次，一共判断60次。  
获得“不及格”的学生一共10人，每人判断4次，一共判断40次。  
获得“优”的学生一共10人，每人判断5次，一共判断50次。  
所以总共需要判断230次。  
从这个例子可以看到，仅仅是代码的次序进行调整，我们就可以减少23.3%的判断。也就是说提高了23.3%的效率。想象一下，如果是对上亿的数据进行评级，这个调整可以节约多少资源。你可能没明白这个例子跟“树”有什么关系，实际上，后面一种方式就是使用到了Huffman树，本章第六小节中会仔细讲解Huffman树。

第三个例子：在OI竞赛中经常要求在规定时间内，在含有大量数据的图中找到最短路径。如果用原始的Dijkstra算法，基本上只能等着超时，而使用堆优化之后，速度就变的杠杠的。这里提到的“堆”就是一种二叉树。好了，有了这三个例子，我想你已经明白“树”的价值了，那么我们就开始正式学习“树”吧。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/a8b29907d1ad4ef8944408e9c5649230.png