[TOC]
tree和graph不再是线性的数据结构
貌似课件里默认root是level0 同理,树的的height也会那个一点
Binary Tree
显而易见
Full Binary Tree(满二叉树)
height = h 的树刚好有 2^h+1^ - 1 elements
Complete Binary Tree（完全二叉树）
一个最后一层可以不被填满,但是元素一定都从左向右依次排好的,其余层和full binary tree一样的树
也就是说它的height如果是h,那它就会2^h+1^-i(1<=i<=k)个节点
节点编号
我们需要给每个节点编个号,如何去映射呢?
if 0 <= i <= n - 1
i = 0 => root
i > 0 => i的parent在Math.floor((i - 1)/2)
2 * i + 1 => i 的 left child
2 * i+ 2 => i 的 right child
Representation
Array (Formula-Based Representation)
Linked(L-R linked storage)
Class node{
....Leftchild
.....data
.....Rightchild
................
}
Cursor
Common binary tree operations
其他不是特别复杂,主要在于遍历顺序
preorder inorder postorder
/**
* 使用递归方法，先序遍历二叉树
* @param root 当前树
* @return 遍历后的序列
* @Example
* BinTree.PreOrderTraversal(root)
*/
public static StringBuilder PreOrderTraversal(BinTree root) {
// please enter your code here...
StringBuilder sb = new StringBuilder();
sb.append(root.element);
if(root.left != null){
sb.append(PreOrderTraversal(root.left));
}
if(root.right != null){
sb.append(PreOrderTraversal(root.right));
}
return sb;
}
/**
* 使用递归方法，中序遍历二叉树
* @param root 当前树
* @return 遍历后的序列
* @Example
* BinTree.InOrderTraversal(root)
*/
public static StringBuilder InOrderTraversal(BinTree root) {
// please enter your code here...
StringBuilder sb = new StringBuilder();
if(root.left != null){
sb.append(InOrderTraversal(root.left));
}
sb.append(root.element);
if(root.right != null){
sb.append(InOrderTraversal(root.right));
}
return sb;
}
/**
* 使用递归方法，后序遍历二叉树
* @param root 当前树
* @return 遍历后的序列
* @Example
* BinTree.PostOrderTraversal(root)
*/
public static StringBuilder PostOrderTraversal(BinTree root) {
// please enter your code here...
StringBuilder sb = new StringBuilder();
if(root.left != null){
sb.append(PostOrderTraversal(root.left));
}
if(root.right != null){
sb.append(PostOrderTraversal(root.right));
}
sb.append(root.element);
return sb;
}
//上面三个还可以用非递归实现 仅用inorder举个例子吧
public staticStringBuilder InOrder(BinaryTree root){
stack[] a;
StringBuilder sb = new Stringbuilder();
Binarynode p = root;
while(1){
while(p != null){
a.push(p);
p = p.left;
}
if(!a.IsEmpty()){
p = a.pop();
sb.append(p.element);
p = p.right;
}
else{
return sb;
}
}
}
public static void preorderTraversal(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
System.out.print(current.val + " ");
// 先右后左，保证左子树先处理
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
Class StkNode{
BinaryNode ptr;
int tag;
}
public static StringBuilder Postorder(BinaryTree root){
Stack<StkNode> s = new stack<StkNode>();
StringBuilder sb = new StringBuilder();
Binarynode p = root;
StkNode Cnode;
while(1){
while(p != null){
Cnode.ptr = p;
Cnode,tag = 0;
s.push(Cnode);
p = p,left;
}
Cnode = s.pop();
p = Cnode.ptr;
//下面处理从右子树回来
while(Cnode.tag == 1){
sb.append(p.element);
if(!s.IsEmpty()){
Cnode = s.pop();
p = Cnode.ptr;
}
else{
return;
}
}
//下面处理从左子树回来
Cnode.tag = 1;
s.push(Cnode);
p = p.right;
}
}//太复杂了 其实是这么做的,先把最左边的压进栈,然后一通操作下来你会发现,虽然中间节点会比右节点先tag变成1,但是他会在栈里面比右节点排的低
public static StringBuilder LevelOrder(BinTree root){
StringBuilder sb = new StringBuilder();
Queue[] a...........;
while(root){
vistit(root);
if(t->left){
a.add(root->left);
}
if(t->right){
a.add(root->right);
}
try{
(a.Delete(root));//删除队列第一个节点,并赋值给root
}
catch(OutOfBounds){
return;
}
}
}
递归简单,非递归太难了
Create BinaryTree
/**
* 使用递归方法，根据先序遍历和中序遍历结果，创建一棵二叉树
* @param pres 先序遍历字符数组
* @param ins 中序遍历字符数组
* @Example
* BinTree root = BinTree.CreateBT("ABDCEGFHI", "DBAEGCHFI");
*/
public static BinTree CreateBT(char[] pres, char[] ins){
// please enter your code here...
if(pres.length == 0 || ins.length == 0){
return null;
}
BinTree root = new BinTree(pres[0], null, null);
int i = 0;
for(; i < ins.length; i++){
if(ins[i] == pres[0]){
break;
}
}
char[] leftPres = new char[i];
char[] leftIns = new char[i];
char[] rightPres = new char[pres.length - i - 1];
char[] rightIns = new char[pres.length - i - 1];
for(int j = 0; j < i; j++){
leftPres[j] = pres[j + 1];
leftIns[j] = ins[j];
}
for(int j = 0; j < pres.length - i - 1; j++){
rightPres[j] = pres[j + i + 1];
rightIns[j] = ins[j + i + 1];
}
root.left = CreateBT(leftPres, leftIns);
root.right = CreateBT(rightPres, rightIns);
return root;
}
关键在于找到root,左分支,右分支,找到这些就可以递归求解了.
Application
Binary-Tree Representation of a Tree
森林->二叉树
深度遍历->先序\后序\中序
广度遍历->分层访问
Thread Tree
关键在于这里面的前驱和后继是哪个 这得根据前/中/后序线索树来判断
构造中序线索树如下
这其实挺好理解的,用pre记录前驱,这样就可以在每次循环记录pre的后继和p的前驱
Huffman Tree(霍尔曼树)
Huffman算法
其实有种类似并查集的感觉,每次取两个最小的union,意味着她两是兄弟,他们的parent的他们的合
Binary Search Tree
进阶定义Indexed binary search tree:比正常的二叉搜索树多一个leftSize用来标记该节点的 左子树元素数量+1
Find Operation
private BinaryNode find( Comparable x, BinaryNode t ){
if( t = = null )
return null;
if( x. compareTo( t.element ) < 0 )
return find( x, t.left );
else if( x.compareTo( t.element ) > 0 )
return find( x, t.right );
else
return t; //Match
}
这个很简单吧
Insertion Operation
public BinaryNode insert(Comparable x, BinaryNode t){
if(t == null){
t = new BinaryNode(x, null, null);
}
if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left);
}
else if(x.compareTo(t.element) > 0){
t,right = insert(x, t.right);
}
else{
//do nothing 我要插入的已经在里面了
}
return t;
}
这个也不复杂吧
Deletion Operation
public BinaryNode delete(Comparable x, Binary t){
if(t == null){
return t;
}
if(x.compareTo(t.element) > 0){
t.right = delete(x, t.right);
}
else if(x.compareTo(t.element) < 0){
t.left = delete(x, t.left);
}
else{
if(t.left != null && t.right != null){
t.element = t,finMin(t.right).element;
delete(t.findMin(t.right).element, t.right);
}
else{
t = (t.left != null)? t.left: t.right;
}
}
return t;
}
如果左右都有节点就替补上左最大or右最小
稍微思考一下
AVL Tree(自平衡的二叉搜索树)
Insertion Operation
关键是找到最小不平衡子树
private AVLNode insert(Comparable x, AVLNode t){
if(t == null){
t = new AVLNode(x, null, null);
}
else if(x.compareTo(t.element) < 0){
t.left = insert(x,t.left);//由于递归调用,所以其实只有最小不平衡子树的节点会进入到底下那个if里面
if(height(t.left) - height(t.right) == 2){
if(x.compareTo(t.left.element) < 0){
t = rotateWithLeftChild(t);
}
else{
t = doubleWithLeftChild(t);
}
}
else if(x.compareTo(t.left.element) > 0){
.............
}
}
else{
......
}
t.height = max(height(t.left), height(t.right)) + 1;
return t;
}
private static AVLNode rotateWithLeftChild(AVLNode k2){
AVLNode k1 = k2.left;
//k1就是即将替代k2位置的新的"根"
//我们需要做几个调整 k2的右节点应该变成k1,而k2原来的右节点应该变成k1的左节点
k2.left = k1.right;
k1.right = k2;
//下面更新高度
k2.height = max(height(k2.left),height(k2.right)) + 1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
return k1;
}//左单旋
private static AVLNode doubleWithLeftChild(AVLNode k3){
//双旋主要就是需要先进行一次单旋转,使得原来不在一条直接上的节点变成一条直线
k3.left = rotateWithRightChild(k3.left);
k3 = rotateWithLeftChild(k3);
return k3;
}
....................................................
处理好单旋和双旋的判断是关键
AVL树的插入:
- 首先要正确地插入
- 找到有可能发生的最小不平衡子树
- 判别插入在不平衡子树的外侧还是内侧
- 根据3的判别结果,再进行单旋还是双旋
Deletion Operation
ppt没给代码说明没那么重要,其实就是和insert差不多,把insert换成delete就好,也就是一个调整的问题
m-way search tree
注意m-way对应的是elements最多m-1个
Find Operation
find其实倒是没那么难,反正就是一顿比较递归下去
Insertion Operation
insert或许也没那么多讲究
Deletion Operation
像这种删了就删了,无所谓,它底下没子树
像这种删除就很有说法了,一般是左边的最大or右边最小来替代它
其他
值得注意的是levelh没有element
B-Tree（未完全掌握）
底下那些没有元素的节点必须在同一个level
root必须至少两个元素
Math.ceiling(m / 2) <= child数量 <= m
Insertion Operation
两种case
case1确实舒服
case2较为复杂,有个分裂的过程,所谓分裂就是把一个超出数量的节点分成两半,然后把分裂出来的三个节点的根并到parent里面,然后看看parent是否需要进一步分裂,以次类推
Deletion Operation
第一个情况没啥好说的,直接删
这个是删了之后,节点数量不够,所以得找兄弟借,借的时候就有一个相当于单左旋/单右旋的过程.
兄弟借不了,那只能和兄弟合并了.
上左最大或者右最小 再删除对应节点
要是邻居也借不了该怎么办呢，这时候就需要和parent去合并了，然后再做调整
森林先根和后根
先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
void PreOrder(TreeNode *R){
if(R!=NULL){
visit(R); //访问根节点
while(R还有下一个子树T)
PreOrder(T); //递归，先根遍历下一个子树
}
}
后根遍历。若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。
void PostOrder(TreeNode *R){
if(R!=NULL){
while(R还有下一个子树T)
PostOrder(T); //递归，后根遍历下一个子树
visit(R); //访问根节点
}
}
注意，树的先根后根和森林的不是一个东西