手把手教你数组、链表和二叉树的比较
1、鼠标双击或者右击打开桌面上DEVc++软件，让其运行起来。Dev-C++是一个电脑Windows窗口运行环境下的一款非常适合于刚开始学习c++学者使用的入门级C/C++ 集成开发环境（IDE）。这款软件很自由，遵守GPL许可协议分发源代码。它大大集成了MinGW中的GCC编译器、GDB调试器和 AStyle格式整理器等众多自由软件。非常的试用，而且界面分类清楚，具有很强大的功能
2、点开文件，选择新建源代码，这时候新建的代码文本还是没有命名的，是一个空命名的文件，下面我们可以通过界面左上角的文件选项，选择另存为，可以存在电脑里任何一个盘，小编为了下次可以更好的找到文件，我存在电脑的桌面上。当然你们可以选择任何一个盘，根据各人所需
3、数组、链表和二叉树的比较
用来表示数据元素集合的办法
数组
链表
二叉树
数组：按序号访问元素
连续存储，元素可以有序、也可以无序
用下标来定位元素
元素的数量确定(有上限)
按下标访问很快
插入和删除元素、排序的开销比较大：元素的移位操作
数组元素无序时，元素的查找速度比较慢：依次比较
数组元素有序时，元素的查找速度比较慢：二分查找
4、 链表：插入、删除方便；元素数量不受限制
非连续存储，元素可以有序、也可以无序
查找、访问元素的开销比较大：依次比较每一个元 素
元素的数量不受限制
插入和删除元素、排序的开销比较小：修改指针域
5、 二叉树：插入、删除方便；查找快
非连续存储，元素一定是有序：建树时判定在左子 树、还是右子树上需要有依据
查找、访问元素的开销比较小：比较的次数不超过 二叉树的深度
元素的数量不受限制
插入和删除元素、排序的开销比较小：修改指针域
6、 数组、链表、二叉树各自适用的场合
数组：数据集合中元素的数量基本可以确定；不需要频繁的插入、删 除
链表：需要频繁的插入、删除元素；不可预知元素的数量范围
二叉树：需要频繁的插入、删除、查找元素
发挥二叉数的优势：必须降低二叉数的深度
同样的深度，完全二叉树能够保存的元素数量最多。但除非在建树 时，就按照顺序添加节点，否则构造的难度大
7、 退而求其次：建立平衡二叉树。每个节点，它的左子树与右子树的深 度之差不超过1
对大规模的元素序列进行排序，比如有几万个、甚至更多的元素
用数组：频繁的数组元素交换
链表：越往后，插入一个元素需要的比较次数与已排序元素的数量呈 线性增加
平衡二叉树来：越往后，插入一个元素需要的比较次数与已排序元素 的数量按对数关系增加
8、建立平衡二叉树
在一棵平衡二叉树上，插入一个新的节点
插入到子树son1上，结果
son1的深度未变：整个二叉树是平衡的
son1的深度增加到与另一棵子树son2的深度一致：整个二叉树是平 衡的
son1的深度增加到比另一棵子树son2的深度大1： son1父节点father是 平衡的，要检查father的父节点是否平衡
son1的深度增加到比另一棵子树son2的深度大2：分4种情况进行二 叉树的结构调整
情形1：右子树为空、左子树的深度为2
情形2：右子树非空、左子树的深度比右子树的深度大2
情形3：左子树为空、右子树的深度为2
情形4：左子树非空、右子树的深度比左子树的深度大2
