急求数据结构二叉树的遍历-平衡二叉树课程设计

来源：蜘蛛抓取(WebSpider) 时间：2022-11-29 15:10 标签： 数据结构二叉树的遍历

这 个恐怕是整个《数据结构》教科书里面最难的和最“没用”的数据结构了（现在的教科书还有部分算法内容）。说它没用，恰恰是因为它太有用——有着和普通的二 叉搜索树完全一样的接口界面，绝大多数情况下比普通的二叉搜索树效率高（很多）。因此，通常情况下，人们都是一劳永逸的——写完后就重用，而不会再写了。 所以说，你虽然学完了平衡二叉树，但很可能你永远也不会亲自写一个。你现在随便在身边拉个人，让他来写一个，能顺利的写出来的恐怕不多，玩笑之词，且勿当 真。

在开始写之前，我很担心，能不能把这部分写清楚，毕竟书上满天的switch…case，并且还只是一半——有左旋没有右旋，有插入没有删除。后来，我变得有信心了——因为书上都没有说清楚，都在那里说梦话。我没有找到AVL树的发明者的原著（G. 1962.）也不知道我下面所写的是不是体现了发明者的本意，但至少，我认为现在的教科书歪曲了发明者的本意。

科技文都比较好懂，本人翻译水平比较差，就不献丑了，我只想让大家注意最后一段的画线部分，平衡化应该是易于操作的，而绝不是现在你在书上看到的铺天盖地的switch…case。

平衡化靠的是旋转。参与旋转的是3个节点（其中一个可能是外部节点NULL），旋转就是把这3个节点转个位置。注意的是，左旋的时候p->right一定不为空，右旋的时候p->left一定不为空，这是显而易见的。

    可以看到，左旋确实是在向“左”旋转，还是很形象的。右旋是左旋的镜像，就不再另行说明了。下表是左旋和右旋各个节点的指针变换情况。（括号表示NULL的情况不执行）

AVL树的平衡化靠旋转，而是否需要平衡化，取决于树中是否出现了不平衡。为了避免每次判断平衡时，都求一下左右子树的高度，引入了平衡因子。很可能是1962年的时候AV&L没有亲自给出定义，时下里平衡因子的定义乱七八糟——我看了4本书，两本是bf ＝ 左高－右高，两本是bf ＝ 右高－左高。最有意思的是两本中国人（严蔚敏和殷人昆）写的一本左减右，一本右减左；两本外国人写的也是这样。虽然没什么原则上的差别，可苦了中国的莘莘学子们——考试的时候可不管你是哪个门派的。我照顾自己的习惯，下面的bf = 左高－右高，习惯不同的请自己注意。

这样一来，是否需要平衡化的条件就很明了了——| bf | > 1。如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf ==

在AVL树插入和删除，实际上就是先按照普通二叉搜索树插入和删除，然后再平衡化。可以肯定的说，插入和删除需要的最多平衡化次数不同（下面会给出根本原因），但这不表明插入和删除时的平衡化的思路有很大差别。现有的教科书，仅仅从表面上看到了到了平衡化操作次数不同的假象，而没有从根本上认识到插入和删除对称的本质，搞得乱七八糟不说（铺天盖地的switch…case），还严重的误导了读者——以为删除操作复杂的不可捉摸。

AVL树体现了一种平衡的美感，两种旋转是互为镜像的，插入删除是互为镜像的操作，没理由会有那么大的差别。实际上，平衡化可以统一的这样来操作：

current指向插入节点或者实际删除节点的父节点，这是普通二叉搜索树的插入和删除操作带来的结果。*p初始值是插入节点或者实际删除节点的data。因为删除操作可能实际删除的不是data。

break;这时，以current为根的子树的高度和插入前的高度相同。

break;这时，以current为根的子树的高度和删除前的高度相同

之所以删除操作需要的平衡化次数多，就是因为平衡化不会增加子树的高度，但是可能会减少子树的高度，在有有可能使树增高的插入操作中，一次平衡化能抵消掉增高；在有可能使树减低的删除操作中，平衡化可能会带来祖先节点的不平衡。

完整的插入删除函数如下：

你可以看到，他们是多么的对称。

我要回帖

更多关于 数据结构二叉树的遍历 的文章

 

随机推荐