二叉树的概念

二叉树的定义和基本术语

二叉树：二叉树由结点的有限集合构成这个有限集合或者为空集 (empty)或者为由一个根结点 (root) 及两棵互不相交、分别称作这个根的左子树 (left subtree) 和右子树 (right subtree) 的二叉树组成的集合
注意：每个结点至多两棵子树，且有左右之分，不能随意交换
二叉树的五种基本形态：二叉树可以为空，结点的左、右子树也可空
1. 空
2. 独根
3. 空左
4. 空右
5. 左右都不空

根：引出二叉树结点的起始结点
父结点：任何非根结点的前驱结点
子结点：左子结点(左孩子，左子女)。右子结点(右孩子，右子女)
兄弟结点：具有相同的父结点
叶结点：没有子结点的结点
度：一个结点子树数目
内部结点(分支结点)：除叶结点外非终端结点
边：父结点k与子结点k’之间的有向连线<k，k’>
路径：从结点k0到结点ks存在一些边相连

满二叉树、完全二叉树、扩充二叉树

满二叉树：一棵二叉树的任何结点，或是树叶，或者左右结点均非空(没有度为1的情况)
完全二叉树：一棵二叉树最多只有最下面的两层结点度数可以<2，并且最下面一层的结点都集中在该层最左边的连续位置上(其叶结点只可能在层次最大的两层出现)
完全二叉树中由根结点到各个节点的路径长度总和在具有同样结点个数的二叉树中达到了最小
扩充二叉树：在二叉树中出现空子树的位置增加空树叶(度数为1的分支下面增加空树叶，度为0的分支下增加两个空树叶)
扩充二叉树是满二叉树，新增空树叶(外部结点)的个数等于原二叉树的结点个数(内部结点)+1
扩充二叉树外部路径长度 E 和内部路径长度 I 满足：E = I + 2n (n 是内部结点个数)

二叉树的主要性质

在二叉树中，第i层上最多有2^i哥结点(i >= 0)
深度为k的二叉树至多有2^(k+1) - 1个结点
任何一个二叉树，若其终端结点数为n0(度为0的结点)，度为2的结点数为n2，则n0 = n2 + 1
满二叉树定理：非空满二叉树树叶数目等于其分支结点数+1
满二叉树定理推论：一个非空二叉树的空子树数目等于其节点数+1
n个结点的完全二叉树的高度为[log2(n+1)]，深度为[log2(n+1)]-1，其中高度定义为二叉树中层数最大的叶结点层数+1
对于具有n个结点的完全二叉树，有
1. 如果i=0.结点i是二叉树的根结点；若i>0则其父结点编号为[(i-1)/2]
2. 当2i+1<=n-1时，结点i的左子结点是2i+1，否则i没有左子结点；当2i+2<=n-1时，结点i的右子结点是2i+2，否则i没有右子结点；
3. i为偶数且0<i<n时，结点i的左兄弟结点是结点i-1，否则没有左兄弟结点；i为奇数且i+1<n时，结点i的右兄弟结点是结点i+1，否则没有左兄弟结点

二叉树的周游

二叉树的ADT

对二叉树的操作和运算主要在访问二叉树的结点信息上

// 二叉树结点的ADT
template <class T>
class BinaryTreeNode {
friend class BinaryTree<T>; // 声明二叉树类为友元类
private:
    T info; // 二叉树结点数据域
public:
    BinaryTreeNode(); // 缺省构造函数
    BinaryTreeNode(const T& ele); // 给定数据的构造
    BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l,BinaryTreeNode<T> *r); // 子树构造结点
    T value() const; // 返回当前结点数据
    BinaryTreeNode<T>* leftchild() const; // 返回左子树
    BinaryTreeNode<T>* rightchild() const; // 返回右子树
    BinaryTreeNode<T>* Parent(); // 返回父结点
    BinaryTreeNode<T>* LeftSibling(); // 返回左兄结点
    BinaryTreeNode<T>* RightSibling(); // 返回右兄结点
    BinaryTreeNode<T>& operator = (const BinaryTreeNode<T>& Node);
    bool isLeaf() const; // 判断是否为叶结点
    void setLeftchild(BinaryTreeNode<T>*); // 设置左子树
    void setRightchild(BinaryTreeNode<T>*);// 设置右子树
    void setValue(const T& val); // 设置数据域
};

template <class T> class BinaryTree {
private:
    BinaryTreeNode<T>* root; // 二叉树根结点
public:
    BinaryTree() {root = NULL;}; // 构造函数
    ~BinaryTree() {DeleteBinaryTree(root);}; // 析构函数
    bool isEmpty() const; // 判定二叉树是否为空树
    BinaryTreeNode<T>* Root() {return root;} // 返回根结点
    void CreateTree(const T& info,
    BinaryTree<T>& leftTree, BinaryTree<T>& rightTree); // 构造新树
    void PreOrder(BinaryTreeNode<T> *root); // 前序遍历二叉树或其子树
    void InOrder(BinaryTreeNode<T> *root); // 中序遍历二叉树或其子树
    void PostOrder(BinaryTreeNode<T> *root); // 后序遍历二叉树或其子树
    void LevelOrder(BinaryTreeNode<T> *root); // 按层次遍历二叉树或其子树
    void DeleteBinaryTree(BinaryTreeNode<T> *root); // 删除二叉树或其子树
};

二叉树的周游(遍历)：按照一定顺序依次访问(操作)树中的所有结点
二叉树是一种非线性结构，每个结点可以有一个以上的直接后继，因袭需要把二叉树中的结点转化为顺序结构才能周游整个二叉树。周游二叉树的过程实际上就是把二叉树的结点放入一个线性序列的过程，即对二叉树进行线性化
线性化的方法：
1. 深度优先周游
2. 广度优先周游

深度优先周游二叉树

深度优先周游算法的思想：尽可能地沿分支结点向深度方向进行周游。先沿着分支结点向左下降，当左子树为空的时候，返回分支结点再转向右结点
二叉树的基本单元组成：根结点，左子树，右子树。用LtR分别表示周游左子树，访问当前结点，周游右子树
深度优先周游二叉树的分类：
1. 前序遍历 (tLR次序, preorder traversal)：
  1. 访问根结点
  2. 按前序周游左子树
  3. 按前序周游右子树
2. 中序遍历 (LtR次序, inorder traversal)，也称对称序
  1. 按中序周游左子树
  2. 访问根节点
  3. 按中序周游右子树
3. 后序遍历 (LRt次序, postorder traversal)
  1. 按后序周游左子树
  2. 按后序周游右子树
  3. 访问根节点

二叉树的前序(中序、后序)序列：前序(中序、后序)周游二叉树得到二叉树结点的一个有序序列

递归算法实现二叉树的深度优先周游

template<class T>
void BinaryTree<T>::DepthOrder (BinaryTreeNode<T>* root) 
{
    if(root!=NULL) 
    {
        Visit(root); // 前序
        DepthOrder(root->leftchild()); // 递归访问左子树
        Visit(root); // 中序
        DepthOrder(root->rightchild()); // 递归访问右子树
        Visit(root); // 后序
    }
}

非递归算法实现二叉树的深度优先周游

关键：设置一个栈，记录尚待遍历的结点，以备后续访问
非递归前序遍历二叉树的思想：
1. 遇到一个结点，访问之，并将其非空右子结点压栈；
2. 下降去前序遍历其左子树；
3. 按前序方式遍历完左子树后，从栈顶弹出一个结点，访问之，并继续按前序方式遍历其右子树
4. 最开始压入一个空指针作为监视哨，当这个空指针被弹出来，周游结束

// 非递归前序遍历二叉树
template<class T> void BinaryTree<T>::PreOrderWithoutRecursion(BinaryTreeNode<T> *root) 
{
    using std::stack; // 使用STL中的栈
    stack<BinaryTreeNode<T>* > aStack; 
    BinaryTreeNode<T> *pointer = root; 
    aStack.push(NULL); // 栈底监视哨
    while (pointer) 
    { // 或者!aStack.empty()
        Visit(pointer->value()); // 访问当前结点
        if (pointer->rightchild() != NULL) // 非空右子入栈
            aStack.push(pointer->rightchild());
        if (pointer->leftchild() != NULL)
            pointer = pointer->leftchild(); // 左路下降
        else 
        { // 左子树访问完毕，转向访问右子树
            pointer = aStack.top(); // 获得栈顶元素
            aStack.pop(); // 栈顶元素退栈
        }
    } 
}

非递归中序遍历二叉树思想：
1. 遇到一个结点，将其压栈后，遍历其左子树
2. 遍历完左子树后，从栈顶弹出该结点并访问之
3. 然后下降到其右子树再去遍历其右子树

template<class T> void
BinaryTree<T>::InOrderWithoutRecusion(BinaryTreeNode<T>* 
root) 
{
    using std::stack; // 使用STL中的stack
    stack<BinaryTreeNode<T>* > aStack;
    BinaryTreeNode<T>* pointer = root;
    while (!aStack.empty() || pointer) 
    {
        if (pointer ) 
        {
        // Visit(pointer->value()); // 前序访问点
        aStack.push(pointer); // 当前结点地址入栈
        // 当前链接结构指向左孩子
        pointer = pointer->leftchild();
        } //end if
        else 
        { //左子树访问完毕，转向访问右子树
        pointer = aStack.top();
        aStack.pop(); //栈顶元素退栈
        Visit(pointer->value()); //访问当前结点
        //当前链接结构指向右孩子
        pointer=pointer->rightchild();
        } //end else
    } //end while
}

非递归后序遍历二叉树思想：
1. 遇到一个结点，将其压栈，遍历其左子树
2. 遍历结束后，尚不能马上访问处于栈顶的该结点，须向右下降去遍历其右子树
3. 遍历完右子树后方可从访问栈顶元素并弹出4
4. 栈中的元素增加一个特征位，以区别栈顶弹出结点时是从其左子树（仍需遍历右子树），还是从右子树返回。L 表示进入左子树并从其返回。R 表示进入右子树并从其返回

enum Tags{Left,Right}; // 定义枚举类型标志位
template <class T>
class StackElement { // 栈元素的定义
public:
    BinaryTreeNode<T>* pointer; // 指向二叉树结点的指针
    Tags tag; // 标志位
};
template<class T>
void BinaryTree<T>::PostOrderWithoutRecursion(BinaryTreeNode<T>* root) 
{
    using std::stack; // 使用STL的栈
    StackElement<T> element;
    stack<StackElement<T > > aStack;
    BinaryTreeNode<T>* pointer;
    pointer = root;
    while (!aStack.empty() || pointer) 
    {
        while (pointer != NULL) 
        { // 沿非空指针压栈，并左路下降
            element.pointer = pointer; element.tag = Left;
            aStack.push(element); // 把标志位为Left的结点压入栈
            pointer = pointer->leftchild();
        }
        element = aStack.top(); aStack.pop(); // 获得栈顶元素，并退栈
        pointer = element.pointer;
        if (element.tag == Left) 
        { // 如果从左子树回来
            element.tag = Right; aStack.push(element); // 置标志位为Right
            pointer = pointer->rightchild();
        }
        else 
        { // 如果从右子树回来
            Visit(pointer->value()); // 访问当前结点
            pointer = NULL; // 置point指针为空，以继续弹栈
        }
    }
}

深度优先遍历二叉树时间代价 : 遍历具有 n 个结点的二叉树需 O(n)时间
深度优先遍历二叉树空间代价 : 遍历过程中栈的最大容量，与树的高度成正比
1. 最坏情况：高度为 n，所需空间复杂度为O(n)
2. 最好情况：O(1)
3. 平均情况：O(log n)

广度优先周游二叉树

过程：从二叉树的第0层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问
需要使用队列作为辅助的存储结构。在周游开始的时候，首先将根结点放入队列中；然后每次从队列中取出队头元素进行处理，每处理一个结点时，按从左至右的顺序把它所有子结点放入队列

void BinaryTree<T>::LevelOrder(BinaryTreeNode<T>* root)
{
    using std::queue; // 使用STL的队列
    queue<BinaryTreeNode<T>*> aQueue;
    BinaryTreeNode<T>* pointer = root; // 保存输入参数
    if (pointer) 
        aQueue.push(pointer); // 根结点入队列
    while (!aQueue.empty()) 
    { // 队列非空
        pointer = aQueue.front(); // 取队列首结点
        aQueue.pop(); // 当前结点出队列
        Visit(pointer->value()); // 访问当前结点
        if(pointer->leftchild())
            aQueue.push(pointer->leftchild()); // 左子树进队列
        if(pointer->rightchild())
            aQueue.push(pointer->rightchild());// 右子树进队列
    } 
}

广度优先遍历二叉树时间代价为 O(n)
广度优先遍历二叉树空间代价与树的最大宽度相关
1. 最佳 O(1)
2. 最坏 O(n)

二叉树的存储结构

二叉树的链式存储结构(用指针实现)

二叉树是非线性结构，二叉树的各结点随机地存储在内存空间中，结点之间的逻辑关系用指针来链接
对于每一个节点，除了存储自身的信息外，还要设置两个指向左右子结点的指针。结点包含三个域：数据域和左、右指针域
二叉链表：有两个指针域的结点结构

// BinaryTreeNode类中增加两个私有数据成员实现二叉链表
private:
    BinaryTreeNode<T> *left; // 指向左子树的指针
    BinaryTreeNode<T> *right; // 指向右子树的指针
template <class T> class BinaryTreeNode 
{
friend class BinaryTree<T>; // 声明二叉树类为友元类
private:
    T info; // 二叉树结点数据域
public:
    BinaryTreeNode(); // 缺省构造函数
    BinaryTreeNode(const T& ele); // 给定数据的构造
    BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l, BinaryTreeNode<T> *r);
    // 子树构造结点
    ...
}

三叉链表：有三个指针域的结点结构，提供“向上”访问的能力,容易查找某个结点的父结点

递归框架寻找父结点——注意返回

template<class T>
BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *rt, BinaryTreeNode<T> *current) 
{
    BinaryTreeNode<T> *tmp;
    if (rt == NULL) return(NULL);
    if (current == rt ->leftchild() || current == rt->rightchild())
            return rt; // 如果子结点是current则返回parent
    if (tmp = Parent(rt->leftchild(), current) != NULL)
        return tmp;
    if (tmp =Parent(rt->rightchild(), current) != NULL)
        return tmp;
    return NULL;
}

非递归框架找父结点

BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *current) 
{
    using std::stack; // 使用STL中的栈
    stack<BinaryTreeNode<T>* > aStack;
    BinaryTreeNode<T> *pointer = root;
    aStack.push(NULL); // 栈底监视哨
    while (pointer) 
    { // 或者!aStack.empty()
        if (current == pointer->leftchild() || current == pointer->rightchild())
            return pointer; // 若current为pointer子结点则返回parent
        if (pointer->rightchild() != NULL) // 非空右子结点入栈
            aStack.push(pointer->rightchild());
        if (pointer->leftchild() != NULL)
            pointer = pointer->leftchild(); // 左路下降
        else // 访问完左子转右子
            pointer = aStack.top(); aStack.pop(); // 取栈顶并退栈
    }
}

穿线二叉树:将空指针穿起来

中序线索化二叉树：递归实现

template <class T> 
void ThreadBinaryTree<T>::InThread(ThreadBinaryTreeNode<T>*root,ThreadBinaryTreeNode<T>* &pre) 
{
    if (root!=NULL) 
    {
        InThread(root->leftchild(), pre); //中序线索化左子树
        if (root->leftchild() == NULL) 
        {
            root->left=pre; //建立前驱线索
            if (pre != NULL) 
                root->lTag=1; 
        }
        if ((pre!=NULL) && (pre->rightchild()==NULL)) 
        { //建立后继线索
            pre->right=root; 
            pre->rTag=1; 
        }//end if
        pre=root;
        InThread(root->rightchild(),pre); //中序线索化右子树
    }//end if
}

穿线二叉树空间代价分析
1. 总空间 (2p + d)n
2. 结构性开销 2pn
链式存储特点
1. 优点：运算方便，通过指针可直接访问相关结点
2. 缺点：根据满二叉树定理：一半的指针是空的。空指针 n+1，存储密度低。结构性开销较大

完全二叉树的顺序存储结构

二叉树的顺序存储：按照一定次序，用一组地址连续的存储单元存储二叉树上的各个结点
完全二叉树的层次序列足以反映其结构。完全二叉树的顺序存储，存储结构上是线性的，但依然完整反映了二叉树的逻辑结构
按广度优先周游二叉树形成顺序存储，自上至下，自左至右的对所有结点进行编码，根据结点的存储地址可计算其左、右子结点、父结点、兄弟结点的存储地址
顺序结构数组的下标仍能满足完全二叉树的性质

二叉搜索树

二叉搜索树(BST)的属性：
1. 或为一棵空树
2. 或任何一个检索码为 K 的结点满足
  1. 其左子树（若非空）任一结点的检索码均小于 K
  2. 其右子树（若非空）任一结点的检索码均大于或等于 K
  3. 其左、右子树分别为二叉搜索树
二叉搜索树的特点：中序遍历是正序的（由小到大的排列）

二叉搜索树的检索

BST的检索：从根结点开始，在二叉搜索树中查找检索码为 K 的结点。若根结点检索码为 K，则检索成功并结束
1. 若 K 小于根结点的值，则只需检索左子树
2. 若 K 大于根结点的值，只检索右子树
3. 如此，一直持续到 K 被找到或遇上叶结点仍没发现 K ，则检索失败
检索代价：只需检索两个子树之一：每比较1次，待检子树的高度降1，代价为O(h) 树高 h

二叉搜索树的插入

BST的插入：需要保持BST的性质和性能(中序遍历有序)
1. 从根结点开始，若根结点为空，则将 K 结点作为根插入，操作结束
2. 若 K 小于根结点的值，将其插入左子树
3. 若 K 大于根结点的值，将其插入右子树
4. 直到叶结点，确定插入位置，把待插入节点作为一个新叶结点插入到二叉树搜索树中

// 二叉搜索树的结点插入算法
template <class T>
void BinarySearchTree<T>::InsertNode(BinaryTreeNode<T>* root,BinaryTreeNode<T>* newpointer)
{
    BinaryTreeNode<T>* pointer = NULL;
    if (root == NULL)               // 如果是空树
    {
        Initialize(newpointer);     // 则用指针newpointer作为树根
        return;
    }
    else
    {
        pointer = root;
    }
    while (pointer != NULL)
    {
        if (newpointer->value() == pointer->value())    // 如果存在相等的元素就不插入
        {
            return;
        }
        else if (newpointer->value < pointer->value())  // 待插入结点小于pointer
        {
            if (pointer->leftchild() == NULL)           // 如果pointer没有左孩子
            {
                pointer->left = newpointer;             // newpointer作为左子树
            }
            return;
            else
            {
                pointer = pointer->leftchild();         // 向左下降
            }
        }
        else                                            // 待插入结点大于pointer
        {
            if (pointer->rightchild == NULL)            // 如果pointer没有右孩子
            {
                pointer->right = newpointer;            // newpointer作为右子树
                return;
            }
            else
            {
                pointer = pointer->rightchild();        // 向右下降
            }
        }
    }
}

时间复杂度与根到插入位置的路径长度相关，O(h)

二叉搜索树的删除

BST上的删除：删除一个结点后仍能保持BST性质，且树高变化较小
改进的BTS删除算法思想：
1. 若结点pointer没有左子树，则用pointer右子树的根代替被删除节点pointer
2. 若结点有左子树，则在左子树中找到按中序周游的最后一个节点temppointer(即左子树最大结点)并将其从二叉树中删去。由于temppointer没有右子树，只需用左子树代替temppointer，然后用temppointer代替删除的结点pointer

template <class T> 
void BinarySearchTree<T>::DeleteNodeEx(BinaryTreeNode<T>* pointer) 
{
    if ( pointer == NULL ) 
        return; //若待删除结点不存在，返回
    BinaryTreeNode<T> * temppointer; //保存替换结点
    BinaryTreeNode<T> * tempparent = NULL; //保存替换结点的父结点
    BinaryTreeNode<T> * parent = GetParent(root ,pointer ); //保存待删除结点的父
    if (pointer->leftchild() == NULL) 
    {//如果待删除结点的左子为空，将其右子树代替
        if (parent == NULL)
            root = pointer->rightchild();
        else if (parent->leftchild() == pointer)
            parent->left = pointer->rightchild();
        else 
            parent->right=pointer->rightchild();
    delete pointer; pointer=NULL;
    return;
    }//end if
    else 
    { //在非空左子树中寻找最大结点替换
    temppointer = pointer->leftchild();
    while (temppointer->rightchild() != NULL ) 
    {
        tempparent = temppointer;
        temppointer = temppointer->rightchild();
    } // end of while
// 替换结点脱链
    if (tempparent == NULL) //如下图E，第一个左且没有右子
        pointer->left = temppointer->leftchild();
    else 
        tempparent->right = temppointer->leftchild();
//用替换结点去替代真正的删除结点
    pointer->info = temppointer->info;
    delete temppointer; temppointer= NULL;
    } // end of else
}

树高h，时间代价O(h)

堆与优先队列

如果在一组对象中查找最大值或最小值，堆能提供较高的效率

堆的定义及其实现

堆：一个关键码序列{K0, K1, …, Kn-1} 若具有下述特性：
1. Ki ≤ K2i+1 / Ki ≥ K2i+1
2. Ki ≤ K2i+2 / Ki ≥ K2i+2
最小值堆(min-heap)：任一结点的值小于或等于其子结点的值,根结点存储着树中所有结点的最小值,是特殊的完全二叉树
堆序只是局部有序，只满足内部结点的值不大于其左右子结点，但是一个结点与兄弟结点之间没有必然联系
堆是不唯一的

建堆

时间复杂度O(n)
将一棵完全二叉树调整成堆，假设根的左、右子树都已是堆，且根为T，思路：
1. T 的值小于或等于其两个子结点的值，此时为堆，无须调整
2. T 的值大于两个子结点至少一个的值，此时 T 应与两个子结点中较小者交换，若 T 仍大于其新的子结点，需将 T 继续往下 “筛”（siftdown）
3. 直至到某一个层使 T 不再大于其子结点，或已为叶结点
筛选法建堆：
1. 将 n 个关键码组织到一维数组中
2. 以叶结点为根的子树都已满足堆的特性，亦即，当 i ≥ [n/2] 时，以关键码 Ki 为根的子树已为堆
3. 最后一个分支结点 i = [n/2] - 1 开始，采用 siftdown 从右向左、自底向上将以各个分支结点为根的子树调整成堆，直到树根为止,调整方式如“思路”
堆的ADT

template <class T>
class MinHeap
{
    // 最小堆ADT定义
    T* heapArray; // 存放堆数据的数组
    int CurrentSize; // 当前堆中元素数目
    int MaxSize; // 堆所能容纳的最大元素数目
    void BuildHeap(); // 建堆
public:
    MinHeap(const int n); // 构造函数,n为最大元素数目
    virtual ~MinHeap(){delete []heapArray;}; // 析构函数
    bool isLeaf(int pos) const; // 如果是叶结点，返回TRUE
    int leftchild(int pos) const; // 返回左孩子位置
    int rightchild(int pos) const; // 返回右孩子位置
    int parent(int pos) const; // 返回父结点位置
    bool Remove(int pos, T& node); // 删除给定下标的元素
    bool Insert(const T& newNode); // 向堆中插入新元素newNode
    T& RemoveMin(); // 从堆顶删除最小值
    void SiftUp(int position); // 从position向上开始调整，使序列成为堆
    void SiftDown(int left); // 筛选法函数，参数left表示开始处理的数组下标
}

对最小堆用筛选法 SiftDown 调整，时间复杂度O(logn)

template <class T>
void MinHeap<T>::SiftDown(int position) 
{
    int i = position; // 标识父结点
    int j = 2*i+1; // 标识关键值较小的子结点
    T temp = heapArray[i]; // 保存父结点
    while (j < CurrentSize) 
    {
        if ((j < CurrentSize-1) && (heapArray[j] > heapArray[j+1]))
            j++; // j 指向数值较小的子结点
        if (temp > heapArray[j]) 
        {// 判断结点与其子结点关键码大小
            heapArray[i] = heapArray[j];
            i = j; j = 2*j + 1; // 向下继续
        }
        else 
            break; // 调整结束
    }
    heapArray[i] = temp;
}

对最小堆用筛选法 SiftUp 向上调整

template<class T>
void MinHeap<T>::SiftUp(int position) 
{
    // 从position向上开始调整，使序列成为堆
    int temppos=position;
    // 不是父子结点直接swap
    T temp=heapArray[temppos];
    while((temppos>0) && (heapArray[parent(temppos)] > temp)) 
    {
        heapArray[temppos]=heapArray[parent(temppos)];
        temppos=parent(temppos);
    }
    heapArray[temppos]=temp;// 找到最终位置
}

建最小堆

template<class T>
void MinHeap<T>::BuildHeap()
{
    // 反复调用筛选函数
    for (int i=CurrentSize/2-1; i>=0; i--)
        SiftDown(i);
}

堆的插入算法

思路：
1. 插在堆的最后
2. 与其父结点比较，若不满足堆的性质则往上“拉” （SiftUp）
3. 逐步向上，直到与其父结点满足堆的性质

template <class T>
bool MinHeap<T>::Insert(const T& newNode) 
{
    // 向堆中插入新元素newNode
    if (CurrentSize == MaxSize) // 堆空间已经满
        return false;
    heapArray[CurrentSize] = newNode; // 新元素添加到最后
    SiftUp(CurrentSize); // 向上调整
    CurrentSize++;
}

时间复杂度O(logn)

堆的删除算法

思路：
1. 删除某个位置的元素后将最末端的结点填入这个位置
2. 末端元素需要与被删除位置的子结点比较交换，直到过滤到该结点的正确位置位置(siftdown)
最小堆的删除操作

template<class T>
bool MinHeap<T>::Remove(int pos, T& node) 
{
    if((pos<0)||(pos>=CurrentSize))
        return false;
    T temp=heapArray[pos];
    heapArray[pos]=heapArray[--CurrentSize];
    if (heapArray[parent(pos)]> heapArray[pos])
        SiftUp(pos); //上升筛
    else 
        SiftDown(pos); // 向下筛
    node=temp;
    return true;
}

删除根结点

template <class T> T MinHeap<T>:: RemoveRoot() 
{
    if (CurrentSize == 0) exit(1);
    Item tmpItem = heapArray[0];
    heapArray[0] = heapArray[CurrentSize - 1];
    heapArray[CurrentSize - 1] = tmpItem;
    CurrentSize --;
    SiftDown(0);
    return tmpItem;
}

堆删除算法的时间代价O(logn)

优先队列

根据需要释放具有最小／大值的对象
改变已存储于优先队列中对象的优先权

Huffman树及其应用

Huffman树

一个具有 n 个外部结点的扩充二叉树，每个外部结点 di 有一个与之对应的权 wi，这个扩充二叉树的带权外部路径长度总和最短。
权越大的叶结点离根越近
建立Huffman树思路：
1. 按照“权”(诸如，频率) 将字符组成有序序列
2. 取走当前序列的前两个字符（“权”最小），将其标记为Huffman树的叶结点，并将这两个叶结点作为一个（新生成）分支结点的两个子结点，该分支结点的权为两叶结点的权之和
3. 将所得子树的“权”放回序列中适当位置，保持“权”的有序性
4. 重复上述步骤直至序列中只剩一个元素，则Huffman树建立完毕

Huffman编码

编码：采用一组无歧义的规则将字符集中每个字符编码为唯一可标识的代码串
1. 定长编码：所有字符的编码长度均相同，编码一个具有 n 个字符的字符集最少需要 log2n 位
2. 变长编码：根据字符出现频率编码，高频编码较短，低频字符编码较长
待编码的字符集D = {d0，…，dn-1} ，D中各个字符的出现频率为W = {w0，…，wn-1} ，对字符集D进行二进制编码，使得通信编码总长度最短Huffman编码过程如下：
1. 用d0,…,dn-1作为外部结点构造具有最小带权外部路径长度的扩充二叉树
2. 把每个结点引向其左子结点的边标0，引向其右子结点的边标1
  3。从根结点到每个叶结点路径上的编号连接起来就是这个外部节点所代表字符的编码
Huffman编码的空间效率：字符的平均编码长度
1. 各字符的编码长度ci 乘以其出现概率 pi ，即: c0p0 + c1p1 + … + cn-1pn-1
2. fi 表示第i个字符的出现频率，fT 表示所有字符出现的总次数(c0f0 + c1f1 + … + cn-1fn-1) / fT

第五章二叉树 OJ作业

1:Huffman编码树

/*描述
构造一个具有n个外部节点的扩充二叉树，每个外部节点Ki有一个Wi对应，作为该外部节点的权。
使得这个扩充二叉树的叶节点带权外部路径长度总和最小：
Min( W1 * L1 + W2 * L2 + W3 * L3 + … + Wn * Ln)
Wi:每个节点的权值。
Li:根节点到第i个外部叶子节点的距离。
编程计算最小外部路径长度总和。
输入
第一行输入一个整数t，代表测试数据的组数。
对于每组测试数据，第一行输入一个整数n，外部节点的个数。第二行输入n个整数，
代表各个外部节点的权值。
2<=N<=100
输出
输出最小外部路径长度总和。
样例输入
2
3
1 2 3
4
1 1 3 5
样例输出
9
17
提示
仅考查huffman树的建立，数据范围小，可以不需要使用堆结构.
不过鼓励使用第一题实现的堆来寻找最小和次小元素。*/
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

int huff(int n,int w[])
{
    int depth = n;
    vector<int> weight(w,w + n);
    int result = 0;
    while (weight.size() > 1)
    {
        sort(weight.begin(),weight.end());
        int newWeight = weight[0] + weight[1];
        result += newWeight;
        weight.erase(weight.begin());
        weight.erase(weight.begin());
        weight.push_back(newWeight);
    }
    return result;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int w[100];
        for(int i = 0;i < n;i++)
        {
            cin >> w[i];
        }
        cout << huff(n,w) << endl;
    }
    return 0;
}

2:Pre-Post-erous!

/*描述
We are all familiar with pre-order, in-order and post-order 
traversals of binary trees. A common problem in data structure 
classes is to find the pre-order traversal of a binary tree when 
given the in-order and post-order traversals. Alternatively, 
you can find the post-order traversal when given the in-order 
and pre-order. However, in general you cannot determine the in-order 
traversal of a tree when given its pre-order and post-order traversals. 
Consider the four binary trees below:

    a   a   a   a
   /   /     \   \
  b   b       b   b
 /     \     /     \
c       c   c       c

All of these trees have the same pre-order and post-order traversals. 
This phenomenon is not restricted to binary trees, 
but holds for general m-ary trees as well.
输入
Input will consist of multiple problem instances. 
Each instance will consist of a line of the form
m s1 s2
indicating that the trees are m-ary trees, s1 is the pre-order traversal 
and s2 is the post-order traversal.All traversal strings will 
consist of lowercase alphabetic characters. For all input instances, 
1 <= m <= 20 and the length of s1 and s2 will be between 1 and 26 
inclusive. If the length of s1 is k (which is the same as the length 
of s2, of course), the first k letters of the alphabet will be used 
in the strings. An input line of 0 will terminate the input.
输出
For each problem instance, you should output one line containing the 
number of possible trees which would result in the pre-order and 
post-order traversals for the instance. All output values will be 
within the range of a 32-bit signed integer. For each problem instance, 
you are guaranteed that there is at least one tree with the given 
pre-order and post-order traversals.
样例输入
2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
0
样例输出
4
1
45
207352860*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

const int maxn=35;
char pre[maxn];
char post[maxn];
 
vector<int>branch;
 
void branch_count(int pr1,int pr2,int po1,int po2)
{
    if(pr1==pr2&&po1==po2){
        return ;
    }else{
        int a,b,len,branchcnt=0;
        a=pr1+1;
        b=po1;
        len=0;
        while(b<po2){
            while((pre[a]!=post[b+len])&&(b+len<=po2)){
                len++;
            }
            branchcnt++;
            branch_count(a,a+len,b,b+len);
            a=a+len+1;
            b=b+len+1;
            len=0;
        }
        branch.push_back(branchcnt);
    }
}

int cal(int n,int m)
{
    int a=n-m+1,ans=1;
    for(int i=1;i<=m;i++){
        ans*=a++;
        ans/=i;
    }
    return ans;
}

int main()
{
    int m;
    while(scanf("%d",&m)!=EOF&&m){
        scanf("%s%s",pre,post);
        int len=strlen(pre);
        branch_count(0,len-1,0,len-1);
        int ans=1;
        int len2=branch.size();
        for(int i=0;i<len2;i++){
            ans*=cal(m,branch[i]);
        }
        printf("%d\n",ans);
        branch.clear();
    }
    return 0;
}

3:由中根序列和后根序列重建二叉树

/*描述
我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。
反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可以重建一二叉树。
本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。
用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树
中根序列是9 5 32 67
后根序列9 32 67 5
前根序列5 9 67 32
输入
两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。
输出
一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。
样例输入
9 5 32 67
9 32 67 5
样例输出
5 9 67 32*/
#include <iostream>
#include <vector>
using namespace std;
struct node
{
    int value;
    node *left;
    node *right;
    node(int v) : value(v), left(NULL), right(NULL) {}
};

node *build(vector<int> &inorder, int i_start, int i_end, vector<int> &postorder, int p_start, int p_end)
{
    if (i_start > i_end || p_start > p_end)
    {
        return nullptr;
    }

    int rootVal = postorder[p_end];
    node *root = new node(rootVal);

    int inRoot = i_start;
    for (int i = inRoot; i < i_end; i++)
    {
        if (inorder[i] == rootVal)
        {
            inRoot = i;
            break;
        }
    }

    int leftNum = inRoot - i_start;
    root->left = build(inorder, i_start, inRoot - 1, postorder, p_start, p_start + leftNum - 1);
    root->right = build(inorder, inRoot + 1, i_end, postorder, p_start + leftNum, p_end - 1);
    return root;
}

void out_preorder(node *root)
{
    if (root == nullptr)
    {
        return;
    }
    cout << root->value << " ";
    out_preorder(root->left);
    out_preorder(root->right);
    delete root;
}

int main()
{
    vector<int> inorder, postorder;
    int input;
    while (cin >> input)
    {
        inorder.push_back(input);
        if (cin.peek() == '\n')
        {
            break;
        }
    }
    while (cin >> input)
    {
        postorder.push_back(input);
        if (cin.peek() == '\n')
        {
            break;
        }
    }
    int i_end = inorder.size() - 1;
    int p_end = postorder.size() - 1;
    node *root = build(inorder, 0, i_end, postorder, 0, p_end);
    out_preorder(root);
    cout << endl;
    return 0;
}

二叉树的概念

二叉树的定义和基本术语

满二叉树、完全二叉树、扩充二叉树

二叉树的主要性质

二叉树的周游

二叉树的ADT

深度优先周游二叉树

递归算法实现二叉树的深度优先周游

非递归算法实现二叉树的深度优先周游

广度优先周游二叉树

二叉树的存储结构

二叉树的链式存储结构(用指针实现)

完全二叉树的顺序存储结构

二叉搜索树

二叉搜索树的检索

二叉搜索树的插入

二叉搜索树的删除

堆与优先队列

堆的定义及其实现

建堆

堆的插入算法

堆的删除算法

优先队列

Huffman树及其应用

Huffman树

Huffman编码

第五章 二叉树 OJ作业

1:Huffman编码树

2:Pre-Post-erous!

3:由中根序列和后根序列重建二叉树

第五章二叉树 OJ作业