2018年国家电网考试备考计算机之数据结构与算法(7)

插入

插入，在以zz为头的链表第w个的前面插入nn元素，函数返回值正常是0，如果w超过了链表的长度，函数返回链表的长度

5.树 (Tree)

数据结构中为了存储和查找的方便，用各种树结构来存储文件。树结构包括：二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典树(trie树)、后缀树、广义后缀树。各种树的表示方法、特点及各自的用途如下：

1、二叉查找树(二叉排序树)

(图a)

二叉查找树是一种动态查找表(图a)，具有这些性质：

(1)若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值;

(2)若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值;

(3)其他的左右子树也分别为二叉查找树;

(4)二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。

2、平衡二叉树(AVL树)

(图b)

含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树(图b)，具有以下性质：

(1)要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1;

(2)其左右子树也都是平衡二叉树;

(3)二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。