树

树是由n个结点构成的有限集合。当n=0时称为空树。

对于任一棵非空树，树中有一个称为“根（root）”的特殊结点，用r表示。其余结点可以分为m个互不相交的有限集，其中每个集合本身又是一棵树，称为原来树的子树。子树是不相交的，除了根结点外，每个结点有且仅有一个父结点，一棵N个结点的树有N-1条边。

二叉树的定义：一个有穷的结点集合。这个集合可以为空。若不为空，则它是由根结点和称为其左子树和右子树的两个不相交的二叉树组成。

对任何非空二叉树T，若n0表示叶结点的个数，n2表示度为2的非叶节点个数，那么两者满足关系n0=n2+1。

二叉树的存储结构

1.顺序存储结构，完全二叉树，从上至下，从左到右顺序存储n个结点的完全二叉树的结点父子关系。对于非根节点的父节点的序号是i/2.结点（序号为i）的左孩子节点的序号是2i，（若2i<=n，否则没有左孩子）。结点(序号为i)的右孩子节点的序号是2i+1（若2i+1<=n,否则没有右孩子)。
2.链式存储结构，就是把结点分成左孩子指针和兄弟指针。

二叉树的遍历

1.先序遍历，遍历过程为访问根结点，先序遍历其左子树，先序遍历其右子树。
2.中序遍历，遍历过程为中序遍历其左子树，访问根结点，然后中序遍历其右子树。
3.后序遍历，遍历过程为后序遍历其左子树，后序遍历其右子树最后访问根结点。

先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各节点的时机不同。

二叉树中序遍历非递归遍历算法，使用非递归算法实现 。遇到一个结点就把他压栈，并且取遍历他的左子树。当左子树遍历结束后，从栈顶弹出这个节点并且访问它，然后按其右指针再去中序遍历该节点的右子树。

void InOrderTraversal(BinTree BT){
    BinTree T=BT;
    Stack S = CreatStack(MaxSize);//创建并初始化堆栈S
    while(T|| !IsEmpty(s)){
        while(T){   //一直向左并将沿途结点压入堆栈
            Push(S,T);
            T = T->Left;
        }
        if(!IsEmpty(s)){
            T = Pop(S); //结点弹出堆栈
            printf("%5d",T->Data);  //打印节点
            T = T->Right;   //转向右子树
        }
    }
}

二叉树的层序遍历

二叉树遍历的核心问题：二维结构的线性化。层序基本过程：先根结点入队，然后从队列中取出一个元素，访问该元素所指结点，若该元素所指结点的左右孩子结点为空，则将其左右孩子的指针顺序入队。

void LevelOrderTraversal(BinTree BT){
    Queue Q; BinTree T;
    if (!BT) return;
    Q = CreateQueue(MaxSize);
    AddQ(Q，BT)；
    while(!IsEmptyQ(Q)){
        T = DeleteQ(Q);
        printf("%d\n",T->data);
        if(T->Left) AddQ(Q,T->Left);
        if(T->Right) AddQ(Q,T->Right);
    }
}

先序和中序遍历序列来确定一棵二叉树，先根据先序遍历序列第一个结点确定根结点，然后根据根结点在中序遍历序列中分割出左右两个子序列，最后对左子树和右子树分别递归使用相同的方法继续分解。

二叉搜索树的查找操作

查找从根结点开始，如果树为空，返回NULL。若搜索数为空，则根结点关键字和X进行比较，并进行不同处理。若X小于根结点键值，只需在左子树中继续搜索，如果X大于根结点的键值，在右子树中继续搜索，如果两者比较结果是相等的，则搜索完成，返回指向此结点的指针。

二叉搜索树的插入，关键是要找到元素应该插入的位置。

BinTree Insert(ElementType X,BinTree BST)
{
    if(!BST){
        //若原树为空，生成并返回一个结点的二叉搜索树
        BST = malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }else //开始找要插入元素的位置
        if(x<BST->Data)
            BST->Left = Insert(x,BST->Left);
            //递归插入左子树
        else if(x>BST->Data)
            //递归插入右子树
            BST->Right = Insert(x,BST->Right);
        //else x已经存在，什么都不做
    return BST;
}

二叉搜索树的删除

要删除的结点只有一个孩子结点，将其父结点的指针指向要删除结点的孩子结点

要删除的结点有左右两棵子树，用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素。

BinTree Delete(ElementType X,BinTree BST)
{
    Position Tmp;
    if(!BST)printf("要删除的元素未找到");
    else if(X<BST->Data)
            BST->Left = Delete(X,BST->Left);    //左子树递归删除
    else if(x>BST->Data)
            BST->Left = Delete(X,BST->Right);   //右子树递归删除
    else //找到要删除的结点
        if(BST->Left && BST->Right){ //被删除结点有左右两个子节点
            Tmp = FindMin(BST->Right);  //在右子树中找最小的元素填充删除的结点
            BST->Data = Tmp->Data;
            BST->Right = Delete(BST->Data,BST->Right);
                                            //在删除结点的右子树中删除最小元素
        }else{  //被删除结点有一个或无子结点
            Tmp = BST;
            if(!BST->Left) //有右孩子或无子结点
                BST = BST->Right;
            else if(!BST->Right)
                BST = BST->Left;
            free(Tmp);
        }
    return BST; 
}

平衡二叉树（avl树）

BF(T) = hL-hR,其中hL和hR分别为T的左、右子树的高度。
空树或者任一结点左右子树高度差的绝对值不超过1，即|BF(T)|<=1

堆

优先级队列，顾名思义，它首先应该是一个队列。我们前面讲过，队列最大的特性就是先进先出。不过，在优先级队列中，数据的出队顺序不是先进先出，而是 按照优先级来，优先级最高的，最先出队。 如何实现一个优先级队列呢？方法有很多，但是用堆来实现是最直接、最高效的。这是因为，堆和优先级队列非常相似。一个堆就可以看作一个优先级队列。很 多时候，它们只是概念上的区分而已。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆 顶元素。

堆是一种完全二叉树。它最大的特性是：每个节点的值都大于等于（或小于等于）其子树节点的值。因此，堆被分成了两类，大 顶堆和小顶堆。 堆中比较重要的两个操作是插入一个数据和删除堆顶元素。这两个操作都要用到堆化。插入一个数据的时候，我们把新插入的数据放到数组的最后，然后从下往 上堆化；删除堆顶数据的时候，我们把数组中的最后一个元素放到堆顶，然后从上往下堆化。这两个操作时间复杂度都是logn。

堆的两个特性

结构性：用数组表示完全二叉树。
有序性：任一结点的关键字是其子树所有节点的最大值。最大堆，也称大顶堆：最大值。最小堆也称小顶堆：最小值。

最大堆的创建

typedef struct HeapStruct "MaxHeap";
struct HeapStruct{
        ElementType *Elements; //存储堆元素的数组
        int Size;   //堆的当前元素个数
        int Capacity; //堆的最大容量
};

MaxHeap Create(int MaxSize){
    //创建容量为MaxSize的空的最大堆
    MaxHeap H = malloc(sizeof(struct HeapStruct));
    H->Elements = malloc((MaxSize+1)*sizeof(ElementType));
    H->size = 0;
    H->Capacity = MaxSize;
    H->Elements[0] = MaxData;
        //定义哨兵为大于堆中所有可能元素的值，便于以后更快操作
    return H;
}

将新增节点插入到其父节点到根结点的有序序列中

void Insert(MaxHeap H,ElementsType item){
    //将元素item插入最大堆H，其中H->Elements[0]已经定义为哨兵
    int i;
    if(IsFull(H)){
        printf("最大堆已满");
        return ;
    }
    i = ++H->Size;  //i指向插入后堆中的最后一个元素位置
    for(;H->Elements[i/2] < item;i/2)
        H->Elements[i] = H->Elements[i/2]; //向下过滤节点
    H->Elements[i] = item;  //将item插入
    
}