2018年國家電網(wǎng)考試備考計(jì)算機(jī)之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(7)

插入

插入，在以zz為頭的鏈表第w個(gè)的前面插入nn元素，函數(shù)返回值正常是0，如果w超過了鏈表的長(zhǎng)度，函數(shù)返回鏈表的長(zhǎng)度

5.樹 (Tree)

數(shù)據(jù)結(jié)構(gòu)中為了存儲(chǔ)和查找的方便，用各種樹結(jié)構(gòu)來存儲(chǔ)文件。樹結(jié)構(gòu)包括：二叉查找樹(二叉排序樹)、平衡二叉樹(AVL樹)、紅黑樹、B-樹、B+樹、字典樹(trie樹)、后綴樹、廣義后綴樹。各種樹的表示方法、特點(diǎn)及各自的用途如下：

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

(圖a)

二叉查找樹是一種動(dòng)態(tài)查找表(圖a)，具有這些性質(zhì)：

(1)若它的左子樹不為空，則左子樹上的所有節(jié)點(diǎn)的值都小于它的根節(jié)點(diǎn)的值;

(2)若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于它的根節(jié)點(diǎn)的值;

(3)其他的左右子樹也分別為二叉查找樹;

(4)二叉查找樹是動(dòng)態(tài)查找表，在查找的過程中可見添加和刪除相應(yīng)的元素，在這些操作中需要保持二叉查找樹的以上性質(zhì)。

2、平衡二叉樹(AVL樹)

(圖b)

含有相同節(jié)點(diǎn)的二叉查找樹可以有不同的形態(tài)，而二叉查找樹的平均查找長(zhǎng)度與樹的深度有關(guān)，所以需要找出一個(gè)查找平均長(zhǎng)度最小的一棵，那就是平衡二叉樹(圖b)，具有以下性質(zhì)：

(1)要么是棵空樹，要么其根節(jié)點(diǎn)左右子樹的深度之差的絕對(duì)值不超過1;

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

(3)二叉樹節(jié)點(diǎn)的平衡因子定義為該節(jié)點(diǎn)的左子樹的深度減去右子樹的深度。則平衡二叉樹的所有節(jié)點(diǎn)的平衡因子只可能是-1,0,1。