5.1樹(shù)的概念
公司主營(yíng)業(yè)務(wù)：成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶(hù)真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶(hù)帶來(lái)驚喜。創(chuàng)新互聯(lián)推出商河免費(fèi)做網(wǎng)站回饋大家。
樹(shù)的遞歸定義如下：（1）至少有一個(gè)結(jié)點(diǎn)（稱(chēng)為根）（2）其它是互不相交的子樹(shù)
1.樹(shù)的度——也即是寬度，簡(jiǎn)單地說(shuō)，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹(shù)各結(jié)點(diǎn)中最大的度作為該樹(shù)的度，如上圖的樹(shù)，其度為3;樹(shù)中度為零的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹(shù)中度不為零的結(jié)點(diǎn)稱(chēng)為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱(chēng)為內(nèi)部結(jié)點(diǎn)。
2.樹(shù)的深度——組成該樹(shù)各結(jié)點(diǎn)的最大層次，如上圖，其深度為4；
3.森林——指若干棵互不相交的樹(shù)的集合，如上圖，去掉根結(jié)點(diǎn)A，其原來(lái)的二棵子樹(shù)T1、T2、T3的集合{T1,T2,T3}就為森林；
4.有序樹(shù)——指樹(shù)中同層結(jié)點(diǎn)從左到右有次序排列，它們之間的次序不能互換，這樣的樹(shù)稱(chēng)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。
5.樹(shù)的表示
樹(shù)的表示方法有許多，常用的方法是用括號(hào)：先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)由左至右的順序放入括號(hào)中，而對(duì)子樹(shù)也采用同樣的方法處理；同層子樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹(shù)之間用逗號(hào)隔開(kāi)，最后用閉括號(hào)括起來(lái)。如上圖可寫(xiě)成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5. 2 二叉樹(shù)
1.二叉樹(shù)的基本形態(tài)：
二叉樹(shù)也是遞歸定義的，其結(jié)點(diǎn)有左右子樹(shù)之分，邏輯上二叉樹(shù)有五種基本形態(tài)：
(1)空二叉樹(shù)——(a)；
(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)——(b)；
(3)右子樹(shù)為空的二叉樹(shù)——(c)；
(4)左子樹(shù)為空的二叉樹(shù)——(d)；
(5)完全二叉樹(shù)——(e)
注意：盡管二叉樹(shù)與樹(shù)有許多相似之處，但二叉樹(shù)不是樹(shù)的特殊情形。
2.兩個(gè)重要的概念：
(1)完全二叉樹(shù)——只有最下面的兩層結(jié)點(diǎn)度小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹(shù)；
(2)滿(mǎn)二叉樹(shù)——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子女且葉結(jié)點(diǎn)都處在最底層的二叉樹(shù),。
如下圖：
完全二叉樹(shù)
滿(mǎn)二叉樹(shù)
3.二叉樹(shù)的性質(zhì)
(1) 在二叉樹(shù)中，第i層的結(jié)點(diǎn)總數(shù)不超過(guò)2^(i-1)；
(2) 深度為h的二叉樹(shù)最多有2h-1個(gè)結(jié)點(diǎn)(h=1)，最少有h個(gè)結(jié)點(diǎn)；
(3) 對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，
則N0=N2+1；
(4) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int（log2n）+1
(5)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：
若I為結(jié)點(diǎn)編號(hào)則 如果I1，則其父結(jié)點(diǎn)的編號(hào)為I/2；
如果2*I=N，則其左兒子（即左子樹(shù)的根結(jié)點(diǎn)）的編號(hào)為2*I；若2*IN，則無(wú)左兒子；
如果2*I+1=N，則其右兒子的結(jié)點(diǎn)編號(hào)為2*I+1；若2*I+1N，則無(wú)右兒子。
4.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：
(1）順序存儲(chǔ)方式
type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n] of node;
(2)鏈表存儲(chǔ)方式，如：
type btree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;
5.普通樹(shù)轉(zhuǎn)換成二叉樹(shù)：凡是兄弟就用線(xiàn)連起來(lái)，然后去掉父親到兒子的連線(xiàn)，只留下父母到其第一個(gè)子女的連線(xiàn)。
6.二叉樹(shù)的遍歷運(yùn)算（遞歸定義）
(1)先序遍歷
訪(fǎng)問(wèn)根；按先序遍歷左子樹(shù)；按先序遍歷右子樹(shù)
(2)中序遍歷
按中序遍歷左子樹(shù)；訪(fǎng)問(wèn)根；按中序遍歷右子樹(shù)
(3)后序遍歷
按后序遍歷左子樹(shù)；按后序遍歷右子樹(shù)；訪(fǎng)問(wèn)根
例1.用順序存儲(chǔ)方式建立一棵有31個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)，并對(duì)其進(jìn)行先序遍歷。
program erchashu1;
var b:array[1..31] of char;
e:array[1..63] of byte;
n,h,i,k:integer;
procedure tree(t:integer);
begin
if e[t]=0 then exit
else
begin
write(b[t]);e[t]:=0;
t:=2*t;tree(t);
t:=t+1;tree(t);
end;
end;
begin
repeat
write('n=');readln(n);
until (n0) and (n6);
fillchar(e,sizeof(e),0);
k:=trunc(exp(n*ln(2)))-1;
for i:=1 to k do e[i]:=1;
for i:=1 to 26 do b[i]:=chr(64+i);
for i:=1 to 5 do b[26+i]:=chr(48+i);
h:=1 ;tree(h);
writeln;
end.
例2.用順序存儲(chǔ)方式建立一棵如圖所示的二叉樹(shù)，并對(duì)其進(jìn)行先序遍歷。
program tree1;
const n=15;
type node=record
data:char;
l,r:0..n;
end;
var tr:array[1..n] of node;
e:array[1..n] of 0..1;
i,j:integer;
procedure jtr;
var i:integer;
begin
for i:=1 to n do
with tr[i] do
readln(data,l,r);
end;
procedure search(m:integer);
begin
with tr[m] do
begin
write(data);
if l0 then search(l);
if r0 then search(r);
end;
end;
begin
jtr;search(1);writeln;
end.
例3 用鏈表存儲(chǔ)方式生成上述二叉樹(shù)，中序遍歷之。
1.將上述二叉樹(shù)用廣義表表示為A(B(D,E(G)),C(F(,H)))
2.根據(jù)廣義表串（以#結(jié)束）生成二叉樹(shù)。
program ltree;
const n=8;
type trlist=^node;
node=record
da:char;
l,r:trlist;
end;
var s:array[1..n] of trlist;
p,root:trlist;
ch:char;
top,k:integer;
procedure creat(var head:trlist);
begin
read(ch);
top:=0;
while ch'#' do
begin
case ch of
'A'..'Z':begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil;
if top0 then
case k of
1:s[top]^.l:=p;
2:s[top]^.r:=p;
end
end;
'(':begin top:=top+1;s[top]:=p;k:=1;end;
')': top:=top-1;
',': k:=2;
end;
read(ch);
end;
head:=s[1];
end;
procedure inorder(head:trlist);
begin
if head^.lnil then inorder(head^.l);
write(head^.da);
if head^.rnil then inorder(head^.r);
end;
begin
write('Input tree string:');
creat(root);
inorder(root);
end.
5.3 二叉樹(shù)的應(yīng)用
1. 哈夫曼樹(shù)與哈夫曼碼
樹(shù)的路徑長(zhǎng)度：一棵樹(shù)的每一個(gè)葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度的和。
帶權(quán)二叉樹(shù)：給樹(shù)的葉結(jié)點(diǎn)賦上某個(gè)實(shí)數(shù)值（稱(chēng)葉結(jié)點(diǎn)的權(quán)）。
帶權(quán)路徑長(zhǎng)度：各葉結(jié)點(diǎn)的路徑長(zhǎng)度與其權(quán)值的積的總和。
哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）：帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。
如何構(gòu)建哈夫樹(shù)：（思想是：權(quán)越大離跟越近）
program gojiantree;
const n=4;m=7;
type node=record
w:real;
parent,lchild,rchild:0..m
end;
htree=array[1..m] of node;
var htree1:htree;
procedure gjtree(var ht:htree);
var i,j:integer;
small1,small2:real;
p1,p2:0..m;
begin
for i:=1 to m do
with ht[i] do
begin
w:=0;lchild:=0;rchild:=0;parent:=0;
end;
for i:=1 to n do read(ht[i].w);
for i:=n+1 to m do
begin
p1:=0;p2:=0;
small1:=1000;small2:=1000;
for j:=1 to i-1 do
if ht[j].parent=0 then
if ht[j].wsmall1 then
begin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end
else if ht[j].wsmall2 then begin small2:=ht[j].w;p2:=j end;
ht[p1].parent:=i;
ht[p2].parent:=i;
ht[i].lchild:=p1;
ht[i].rchild:=p2;
ht[i].w:=ht[p1].w+ht[p2].w;
end;
end;
begin
gjtree(htree1);
end.
哈夫曼碼：哈夫曼樹(shù)的非葉結(jié)點(diǎn)到左右孩子的路徑分別用0，1 表示，從根到葉的路徑序列即為哈夫曼碼。
哈夫曼碼是不會(huì)發(fā)生譯碼多義性的不等長(zhǎng)編碼，廣泛應(yīng)用實(shí)際中。
（原因是任何一字符的編碼不是更長(zhǎng)編碼的前綴部分，為什么？）
2.排序二叉樹(shù)
排序二叉樹(shù)：每一個(gè)參加排列的數(shù)據(jù)對(duì)應(yīng)二叉樹(shù)的一個(gè)結(jié)點(diǎn)，且任一結(jié)點(diǎn)如果有左（右）子樹(shù)，則左（右）子樹(shù)各結(jié)點(diǎn)的數(shù)據(jù)必須?。ù螅┯谠摻Y(jié)點(diǎn)的數(shù)據(jù)。中序遍歷排序二叉樹(shù)即得排序結(jié)果。程序如下：
program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
begin
if leftnil then hyt1(left);
write(w:4);
if rightnil then hyt1(right);
end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a[i],first);
hyt1(root);writeln;
end.
3.堆排序
堆：設(shè)有數(shù)據(jù)元素的集合（R1,R2,R3,...Rn)它們是一棵順序二叉樹(shù)的結(jié)點(diǎn)且有
Ri=R2i 和Ri=R2i+1(或=)
堆的性質(zhì)：堆的根結(jié)點(diǎn)上的元素是堆中的最小元素，且堆的每一條路徑上的元素都是有序的。
堆排序的思想是：
1）建初始堆（將結(jié)點(diǎn)[n/2],[ n/2]-1,...3,2,1分別調(diào)成堆）
2）當(dāng)未排序完時(shí)
輸出堆頂元素，刪除堆頂元素，將剩余的元素重新建堆。
程序如下：
program duipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procedure sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a[i];
while j=m do
begin
if (jm) and (a[j]a[j+1]) then j:=j+1;
if ta[j] then
begin a[i]:=a[j];i:=j;j:=2*i; end
else exit;
end;
a[i]:=t;
end;
begin
for i:=1 to n do read(a[i]);
for i:=(n div 2) downto 1 do
sift(a,i,n);
for i:=n downto 2 do
begin
write(a[1]:4);
a[1]:=a[i];
sift(a,1,i-1);
end;
writeln(a[1]:4);
end
2021-11-10
列表是一種非連續(xù)的存儲(chǔ)容器，有多個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)通過(guò)一些變量記錄彼此之間的關(guān)系
單鏈表和雙鏈表就是列表的兩種方法。
原理：A、B、C三個(gè)人，B懂A的電話(huà)，C懂B的電話(huà)只是單方知道號(hào)碼，這樣就形成了一個(gè)單鏈表結(jié)構(gòu)。
如果C把自己的號(hào)碼給B，B把自己的號(hào)碼給A，因?yàn)槭请p方都知道對(duì)方的號(hào)碼，這樣就形成了一個(gè)雙鏈表結(jié)構(gòu)
如果B換號(hào)碼了，他需要通知AC，把自己的號(hào)碼刪了，這個(gè)過(guò)程就是列表的刪除操作。
在Go語(yǔ)言中，列表使用 container/list 包來(lái)實(shí)現(xiàn)，內(nèi)部的實(shí)現(xiàn)原理是雙鏈表，列表能夠高效地進(jìn)行任意位置的元素插入和刪除操作。
列表初始化的兩種辦法
列表沒(méi)有給出具體的元素類(lèi)型的限制，所以列表的元素可以是任意類(lèi)型的，
例如給列表中放入了一個(gè) interface{} 類(lèi)型的值，取出值后，如果要將 interface{} 轉(zhuǎn)換為其他類(lèi)型將會(huì)發(fā)生宕機(jī)。
雙鏈表支持從隊(duì)列前方或后方插入元素，分別對(duì)應(yīng)的方法是 PushFront 和 PushBack。
列表插入函數(shù)的返回值會(huì)提供一個(gè) *list.Element 結(jié)構(gòu)，這個(gè)結(jié)構(gòu)記錄著列表元素的值以及與其他節(jié)點(diǎn)之間的關(guān)系等信息，從列表中刪除元素時(shí)，需要用到這個(gè)結(jié)構(gòu)進(jìn)行快速刪除。
遍歷完也能看到最后的結(jié)果
學(xué)習(xí)地址：
圖例如下:
結(jié)果應(yīng)該是分別是：
廣度優(yōu)先: a - b - c - d - f - e - g
先序遍歷: a - b - d - e - f - g - c
中序遍歷: e - d - b - g - f - a - c
后序遍歷: e - d - g - f - b - c - a
結(jié)果存在result里面，如果不存可以少一層變量
這個(gè)地方強(qiáng)烈建議讀一下下面的第一個(gè)鏈接，我遵照著那篇文章實(shí)現(xiàn)的，只是用Go改寫(xiě)了而已。
首先定義一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來(lái)存儲(chǔ)一些Node的信息。
這里是可以運(yùn)行的，但是總會(huì)拋出一個(gè)數(shù)組越界的錯(cuò)誤，我看了半天也沒(méi)看出來(lái)哪里有問(wèn)題，Mac版的devel我這邊又有bug，沒(méi)用起來(lái)。至少思路對(duì)了，我后面再看一下哪里的問(wèn)題。(感謝 @RiXu 指正)
重慶分公司
重慶分公司
