【数据结构】二叉树、AVL树(4)

?

采用链式存储结构实现二叉树

1. 二叉树在插入的时候通过判断待插入数据与根节点数据的大小，若小于根数据，插入左树，反之插入右树（我们规定不许有重复元素）；二叉树的存储结构常用于搜索等。但搜索的效率常依赖于树的结构。而树的结构与元素插入顺序有很大关系，用上述方法插入时若插入的元素是有序的，则得到的树与队列几乎没有区别，也起不到优化搜索的目的。
2. 二叉树的遍历算法最为重要的一点是递归，递归使我们不必关心于具体的遍历每个节点的顺序，而只是将其看做三个部分，即左子树，根节点，右子树，具体子树的遍历仍是调用其递归函数。
   3.在打印树的时候，我写的并不完美，因为对于叶子节点，理想应该不再打印括号，但我通过判断根节点不为空而调用递归函数，即只要节点有元素就会输出（，），还是表达出了树的意思，但并没有想到怎样达到简洁的效果。

实现AVL树的相关运算

1. AVL树每插入，删除一个节点就会判断树的高度并改变相应节点的平衡因素，每当有节点不再满足AVL树的性质，立即通过旋转得到AVL树
2. 旋转的函数及其巧妙。而插入和删除元素的函数要考虑的情况非常多，一种情况没有考虑到就可能达不到我们想要的效果，函数的编写需要极大的耐心和对编程语句的熟练掌握。很多地方我是参考书上的，别人的代码我可以理解，但我自己写可能还是会漏掉很多情况。
   

转载请注明出处：http://www.voidcn.com/article/p-mgfuopiu-vo.html

（编辑：ASP站长网）