树知识点汇总
算法動態(tài)展示網(wǎng)站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
樹中任意節(jié)點具有孩子的數(shù)目，成為度。
節(jié)點含孩子數(shù)目無限制的樹成為廣義樹， general tree。
樹的平衡
對于一棵樹，如果樹的所有葉子都位于同一層或者相差不超過一層。
完全樹
樹是平衡的，且底層所有葉子都位于樹的左邊，認為樹是完全的。
滿樹
如果n元樹所有的葉子都位于同一層且每個結(jié)點要么是葉子結(jié)點要么具有n個孩子，則稱此樹是滿的。
一般而言，含有m個元素的平衡n元樹高度為lognm.
遍歷
前序
中序
后序
層序：創(chuàng)建結(jié)點隊列，創(chuàng)建結(jié)果list，將根節(jié)點入隊列，while(節(jié)點隊列不為空){
節(jié)點隊列出隊，當節(jié)點不為空，加入list，并將節(jié)點子女入隊列，否則，加入空到結(jié)果列表中。
}
對于表達式樹
遞歸
public int evaluate(BinaryTreenode root){ int result, op1, op2; if(root==null) {result=0; } else{ExpressionTreeOp result=root.getElement();if(result.isOperator()){op1=evaluate(root.getLeft());op2=evaluate(root.getRight());result=Comput(temp.getOperator,op1,op2);} else{result=temp.getValue(); }return result; } }二叉搜索樹
在二叉搜索樹中：
① 若任意結(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均不大于它的根結(jié)點的值；② 若任意結(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均不小于它的根結(jié)點的值；③ 任意結(jié)點的左、右子樹也分別為二叉搜索樹。插入一個節(jié)點
1 看是否為空，為空成為根節(jié)點
2. 不為空與根節(jié)點比較，比其小，根節(jié)點是否有左孩子，沒有，插入
3. 根節(jié)點有左孩子，遞歸，新的函數(shù)，傳入element與根節(jié)點的左孩子，繼續(xù)比較。
二叉搜索樹中刪除一個元素還不會
標注一下好難啊
AVL樹
是由GM Adelson - Velsky和EM Landis于1962年發(fā)明的。為了紀念其發(fā)明者，這樹結(jié)構(gòu)被命名為AVL。
AVL樹可以定義為高度平衡二叉搜索樹，其中每個節(jié)點與平衡因子相關(guān)聯(lián)，該平衡因子通過從其左子樹的子樹中減去其右子樹的高度來計算。
如果每個節(jié)點的平衡因子在-1到1之間，則稱樹是平衡的，否則，樹將是不平衡的并且需要平衡。
平衡系數(shù)(k)=高度(左(k)) - 高度(右(k))
如果任何節(jié)點的平衡因子為1，則意味著左子樹比右子樹高一級。如果任何節(jié)點的平衡因子為0，則意味著左子樹和右子樹包含相等的高度。如果任何節(jié)點的平衡因子是-1，則意味著左子樹比右子樹低一級。
AVL樹如下圖所示。
堆
堆是一個完全二叉樹，其中每一個節(jié)點都小雨或等于他的兩個孩子
最大堆：節(jié)點大于等于左右孩子
最小堆：節(jié)點小于等于左右孩子。
addElement: 先添加到最后，再向上與父元素進行兌換。
removeMin:移除
Set
Map
containsKey()
containsValue()
get(key)
put(key,value)
B 樹 B+樹
2-3查找樹
每個節(jié)點2個孩子（2節(jié)點）或3個孩子（3節(jié)點）
2節(jié)點要么沒有孩子，要么兩個孩子，2節(jié)點只有一個元素
3節(jié)點要么滅有孩子，要么三個孩子，3節(jié)點有2個元素，三個孩子分別是小于最小元素，大于最小小于大的，和大于大的
對于這種樹
仍然是左小右大。
2-3樹插入刪除操作，由于時間原因，僅僅只實現(xiàn)了插入操作。
2-3樹插入操作，分三類。
1.在頭節(jié)點插入這個可以直接生成一個二節(jié)點容納就行。
2.插入的是一個二節(jié)點直接將二節(jié)點升級成為三節(jié)點，保留原本的節(jié)點連接信息就ok了。
3.插入的是三節(jié)點：雖然別人分了很多種情況，但他們都有一個本質(zhì)，就是如果待插入位置如果是三節(jié)點那么就分解它，向上拋擲，如果上面也是三節(jié)點，那么仍然需要拆解，向上拋擲，…等到如果拋擲到頭節(jié)點，如果頭節(jié)點也是三節(jié)點那么說明，這個樹高度不夠存放這個結(jié)構(gòu)，就需要分解頭節(jié)點終止操作增加樹的高度。因為在往上沒有節(jié)點可以執(zhí)行操作。
那好我們假定我們記錄的數(shù)據(jù)是1，2，3，4，5，6，7，8，9不失一般性，就從1開始按順序插入模擬程序運行。
原文：https://blog.csdn.net/qq_41657315/article/details/80571893
F 比e大，且e是一個點，插入，a比b小，先插入，發(fā)現(xiàn)是三個點，然后分裂，中間的b上去。
按大小插入，達到3個之后就進行分裂，中間的上去。
** 2-4樹**
一個節(jié)點包含3個元素（4節(jié)點）要么沒有孩子要么四個孩子
圖
遍歷：
廣度優(yōu)先
深度優(yōu)先
最小生成樹：
prim: 加點法：選擇一個點，他周圍最小的邊對應的點加入，這個點和新加入的點構(gòu)成新的集合，再選擇他們周圍最小的邊，對應的節(jié)點加入。
krustal ：加邊法：選擇最小的邊依次加入 ，只要不成環(huán)即可。
總結(jié)
