树同学她是个好同志

思前想后我决定递归先鸽了，相比于我们的递归同学。我觉得树同学才是我的真爱！！！当然我只是选择先爱我们的树同学，递归同学您就往后稍稍得嘞。

树

对于少量的数据我们可以用链表快速高效的访问，但对于大量的输入数据，链表就显得完全力不从心了，因为链表的线性访问，实在是太慢了。虽然链表可以提供比数组更大的灵活性，但很难使用他们对组织分层表示。栈和队列虽然也反映了某些层次，但他们是一维的。基于总总，终于万众期待的转学生树…于是我们创建了一个新的数据类型，称为树。

  • 定义树的一种自然的方法是递归，一棵树是一些节点的集合

  • 这个集合可以是空集

  • 若非空，则一棵树有称作根(root)的节点r以及0个或者多个非空的子树T1，T2，T3…组成

  • 这些子树中每一课都被来自根r的一条有向的边（eage）所连接

  • 每一棵子树的根叫做根r的儿子(child)，而r是每一棵子树的父亲(parent)

    }树大部分操作的运行时间都在O(log N)

树的种类

我们可能已经听过很多树的名词，例如，红黑树，霍夫曼树，B树，B+树，平衡二叉树等等，而本文将要介绍二叉查找树，很多其他树都是它的变种，不像链表的线性访问，二叉查找树的大部分操作时间复杂度都为O(logN)。

关于父亲儿子外祖父兄弟孙子之类的

我觉得这就没有必要讲的吧，各位不懂的…代入啊代入

树的实现

实现树的一种最常见的方法就是在每一个节点除数据外还需要一些指针，使得该节点每一个son都有一个指针指向它。树并没有规定子节点数量，所以子节点数可以变化很大而且事先不知道。因此没办法建立到各个子节点之间的链接，因为这样太浪费空间了。但是其实解法也很简单：`我们可以将每个节点的所有儿子都放在树节点的链表中。

我们简单声明一个树的节点

1
2
3
4
5
6
7
typedef int ElementType;
typedef struct TreeNode *PtrToNode;
struct TreeNode{
    ElementType Element;
    PtrToNode firstchild;//第一个儿子
    PtrToNode nextSibling;//下一个兄弟
};

emmmmmm看起来很简单对吧

树的遍历及应用

树有很多应用，比如Unix，dos在内的许多操作系统中的目录结构大多数反映分层结构的都是使用树来完成的。树的遍历有这难以比拟的优势。对于一个链表来说如果我们要查找他的一个元素，最坏的情况要从第一个遍历到最后一个，假如说有10000个元素我们就需要遍历到9999个元素才能找到。那么假如是我们是定义在树中即使要定义到最远的那个位置，测试次数也会大大减少。不同节点的树可能也有不同的算法。事实上，人们也已经开发出了这种算法。这里我们重点讨论二叉树。

二叉树

~~二叉树顾名思义就是很二。~~一个节点要分为左节点和右节点。

节点层次:就是从根到该节点所有的弧加一,所以根节点的层次是0,非空节点最低就是2了

以此类推

  • 第一层有1=2^0【由于mathjax的奇怪报错，我放弃使用渲染了，凑合看吧】

  • 第二层有2=2^1

  • 第三层有4=2^2

  • 第四层…

  • 第五层…

  • 第六层…

咦？你们铐我干什么？？什么！！！我没有水博客啊你们相信我啊！！！！

满足该条件被称为完全二叉树

不难看出所有的非终端节点都有两个节点，所有叶节点都在同一节点上，第i+1层有2^i个节点。

对于非空二叉树来说，若其所有的非终端节点都有两个子节点，则叶节点的数目m大于非终端节点数目k，且m=k+1

对于一般二叉树来说她的深度要比n小得多，这个平均深度为O（


N


）【这里出现的是根号n，这里用的是mathml，如果出现其他奇怪的符号那就没办法了，火狐上测试是可以正常显示的】对于二叉查找树也被称为有序二叉树 其平均深度是O(log N)，但是呢我们有可能会遇到最糟糕的情况，没错就是完完全全笔笔直直一条直线这种情况深度就大到了N-1；

二叉树的实现

不出意外的来说一个二叉树最多有两个儿子【废话】，我们可以用指针直接指向他们，树节点在声明上和双链表很像。

在声明中，一个节点就是由key加上两个指向其他节点的指针（Left and Right)组成的结构。链表上的很多东西放在树上也同样适用，当进行一次插入操作时调用malloc创建节点【俺一般都用new，毕竟懒】节点调用后可以调用free删除后被释放。树一般华城圆圈并用一些直线连接起来。二叉树本身就是图。当然涉及到树时我们也没有必要画出Null指针，因为N个节点的一颗二叉树就需要N+1NULL指针；

1
2
3
4
5
6
7
8
typedef int ElementType;
typedef struct PtrToNode Tree;
typedef struct TreeNode *PtrToNode;
struct TreeNode{
    ElementType Element;
    PtrToNode Left;
    PtrToNode Right;
};

表达式树

声明一点表达式树的树叶就是操作数。比如是常数或者变量，而其他的节点为操作符，由于这里的所有操作都是二元的，因此棵特定的树为二叉树。

大致过程为

  • 如果符号是操作数，那么我们就建立一个单节点树并将一个指向它的指针推入栈中
  • 如果符号是操作数，则从栈中弹出两棵树T1和T2（先弹出T1），并形成一颗以操作符为根的树，其中T1为右儿子，T2为左儿子；
  • 然后将新的树压入栈中，继续上述过程。

来看一个栗子吧假如说输入为a b + c d e + * *

（1）依次读入操作数a 和 b，并压入栈中

（2）紧接着“+”被读入，因此指向这两科树的指针被弹出，一颗新的树形成了，而指向该树的指针被压入栈中

（3）然后c，d，e被读入，在每个单节点被创建后，指向对应的树的指针被压入到栈中。

接下来读入“+”号，因此两棵树合并。

再次读入“+”号，因此，我们弹出两个树指针并形成一个新的树，“ * ”是它的根。

读入最后一个符号，两棵树合并，而指向最后的树的指针留在栈中。

查找树ADT-------二叉查找树

二叉树一个非常非常非常重要的应用应该就是查找了吧！！！如果要使一个二叉树变成二叉查找树的性质是，对于每个节点X，他的左子树的所有关键字值小于X的关键字值，而他的右子树中的所有关键字值大于X关键字值。这意味着该树所有的元素都可以使用某一种统一的方式排序,这点非常重要。

初始化MakeEmpty

这个操作主要用于初始化

1
2
3
4
5
6
7
8
SearchTree makeEmpty(SearchTree Tree){
    if(Tree==nullptr){
        makeEmpty(Tree->Left);
        makeEmpty(Tree->Right);
        free(Tree);
    }
    return nullptr;
}

一般的写法是初始化为单节点树，比如TreeNode *tree = nullptr;但是这里用了树的递归定义建立了一棵空树。

Find

这个操作一般需要返回指向树T中具有关键字X节点的指针，如果这种节点不存在就返回NULL；如果T是NULL我们就返回NULL，如果存储在T中的关键字是X，我们就可以返回T；然后还需要注意测试顺序：

  • 判断是否为空树，否则就要一直在NULL兜圈子了
  • 最不可能的情况应该放在最后进行
  • 尾递归尽量用赋值+goto解决，否则可能导致栈空间被用尽，但这里使用时合理的，因为栈空间的量不过才O（log N)而已
1
2
3
4
5
6
7
8
9
10
11
Posttion Find(ElementType X, SearchTree Tree)
{
    if (Tree == nullptr)
        return nullptr;
    if (X < Tree->Element)
        return Find(X, Tree->Left);
    else if (X > Tree->Element)
        return Find(X, Tree->Right);
    else
        return Tree;
}

嘛。这里吧goto代替尾递归的也给加上吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Posttion Find(ElementType X, SearchTree Tree)
{
next:
    if (Tree == nullptr)
        return nullptr;
    if (X < Tree->Element)
        Tree = Tree->Left;
    else if (X > Tree->Element)
    {
        Tree = Tree->Right;
        goto next;
    }
    else
        return Tree;
}

FindMin和FindMax

返回树中的最大元和最小元的位置

  • 对于FindMin从根开始只要有左儿子就向左进行，终止点是最小元素。

  • 至于FindMax当然是反过来啊！！

递归是如此的简单以至于很多程序猿都不厌其烦的使用它。这里我偏不。

FindMIn的递归实现

1
2
3
4
5
6
7
Posttion FindMin(SearchTree Tree){
    if(Tree==nullptr)
    return nullptr;
    else if(Tree->Left==nullptr)
     return Tree;
     else return FindMin(Tree->Left);
}

FindMax的非递归实现

1
2
3
4
5
6
Posttion FindMax(SearchTree Tree){
    if(Tree!=nullptr)
    while(Tree->Right!=nullptr)
    Tree=Tree->Right;
    return Tree;
}

要小心处理空树这种情况，小心原地兜圈圈

Insert

插入的操作是相对简单的啊！将X插入到树T中这件事，可以用Find那样沿着树来查找。如果找到X可以做一些更新啊，否则将X插入到遍历路径的最后一点上。必如说我们要入5，先找到关键字4的节点出，我们需要向右行进，但是右边不存在子树，所以5不在这棵树上。因此我们需要插入5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SearchTree insert(ElementType X, SearchTree Tree)
{
    if (Tree == nullptr)
    {
        Tree = new TreeNode;
        if (Tree == nullptr)
            cout << "error";
        else
        {
            Tree->Element = X;
            Tree->Left = Tree->Right = nullptr;
        }
    }
    else if (X < Tree->Element)
        Tree->Left = insert(X, Tree->Left);
    else if (X > Tree->Element)
        Tree->Right = insert(X, Tree->Right);
    return Tree;
}
  • 初始的T指向该树的根，根在插入时变化，因此Insert被写成一个指向新树根的指针，所以的两次递归把X插到适当的子树中

Delete

删除算是比较难的操作了，一旦发现要删除的节点我们需要考虑以下几种情况

  • 节点只有一片树叶，可以立刻被删除
  • 如果节点有一个儿子，那该节点可以在其父节点调整指针绕过该节点后被删除

比较复杂的情况

相对来说比较复杂的情况是处理具有两个儿子的节点，比较常用的策略是用其右子树的最小数据代替该节点的数据并递归删除那个节点（现在它是空的），因为右子树的最小节点不可能有左儿子，所以第二次删除相对容易。

抱歉啊一不留神做完图发现2没换？？？第二个图的2应该换成3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
SearchTree Delete(ElementType X, SearchTree Tree)
{
    Posttion TemCell;
    if (Tree == nullptr)
        cout << "Element not found"
             << "\n";
    else if (X < Tree->Element)
        Tree->Left = Delete(X, Tree->Left);
    else if (X > Tree->Element)
        Tree->Right = Delete(X, Tree->Right);
    else if (Tree->Left && Tree->Right)
    {
        TemCell = FindMin(Tree->Right);
        Tree->Element = TemCell->Element;
        Tree->Right = Delete(Tree->Element, Tree->Right);
    }
    else
    {
        TemCell = Tree;
        if (Tree->Left == nullptr)
            Tree = Tree->Right;
        else if (Tree->Right = nullptr)
            Tree=Tree->Left;
        free(TemCell);
    }
    return Tree;
}

这个程序的效率并不高，因为它沿该树进行两趟搜索一查找和删除右子树中最小的节点。

平均情况

在之前，出了MakeEmpty之外我们所有的操作都花费了O（log N）因为我们用常数时间在树中降低了一层，这样对树的操作大概降低了一半左右。出了前面提到的MakeEmpty其他都是O（d），其中d表示所访问的关键字深度。

一棵树所有的节点深度的和被称为内部路径长,如果我们现在要计算二叉查找树的平均内部路径长，其中的平均是对向二叉查找树中所有的可能的插入序列进行的。

D（N）是N个节点的内部路径长

D(1) 0
具有i节点的左子树 D(i)
右子树 D(N-i-1)
D(N) D(i)+D(n-i-1)+N-1
D(N)=2/N{(j=0->N-1)D(j)}+N-1 D(N)=O(N log N)

在原树中所有节点要加深1度

这个看起来让人感觉非常愉悦，但是仅凭这个我们是无法保证这个O（log N）是完全正确的，原因在于去删除操作，我们并不清楚是否所有二叉查找树都是等可能出现的，在删除的时候我们选择该元素的最小右子树代替，这种算法有利于左子树比右子树深，当我们进行大量的删除之后高达几十万次就可以明显的看待两边显著的差别。左子树明显会比右子树要深。为了保证所有的节点不得过深所以就搞来了所谓的AVL树。这是一种超老的平衡查找树。

溜了溜了【猝不及防】