数据结构树专题

零、结点定义

一般的二叉树的结点定义（线索二叉树除外）：

struct TreeNode
{
    ElementType data;
    TreeNode *lp;
    TreeNode *rp;
    TreeNode(ElementType d): data(d), lp(NULL), rp(NULL) {}
};

一、递归遍历

//前序遍历
void PreOrder(TreeNode* root)
{
    if(root==NULL)
        return;
    Visit(root->data);
    PreOrder(root->lp);
    PreOrder(root->rp);
}

//中序遍历
void InOrder(TreeNode* root)
{
    if(root==NULL)
        return;
    InOrder(root->lp);
    Visit(root->data);
    InOrder(root->rp);
}

//后序遍历
void PostOrder(TreeNode* root)
{
    if(root==NULL)
        return;
    PostOrder(root->lp);
    PostOrder(root->rp);
    Visit(root->data);
}

二、非递归遍历

1、前序非递归遍历

void PreOrder(TreeNode* root)
{
    stack<TreeNode*> s; //初始化栈
    TreeNode* p = root; //p作为遍历指针
    while(p || !s.empty()) //栈不空或p不空时循环
    {
        if(p) //一路向左
        {
            Visit(root->data); //先访问当前（根）节点
            s.push(p); //当前结点入栈
            p = p->lp; //继续往左走
        }
        else //出栈，并转向出栈结点的右子树
        {
            p = s.top();
            s.pop();
            p = p->rp;
        }
    }
}

2、中序非递归遍历

这个与前序非递归遍历类似，只需把访问结点操作调整到栈顶元素出栈之后即可。

void inOrder(TreeNode* root)
{
    stack<TreeNode*> s;
    TreeNode* p = root;
    while(p || !s.empty())
    {
        if(p) //先一直向左找（先去找最左下方的结点）
        {
            s.push(p);
            p = p->lp;
        }
        else //出栈，访问出栈结点，并转向出栈结点的右子树
        {
            p = s.top();
            s.pop();
            Visit(root->data);
            p = p->rp;
        }
    }
}

3、后序非递归遍历

这个相比上两个会难一些，难点在于在读取栈顶元素的时候必须要分清此时是从左子树返回的还是从右子树返回的，必须要在右子树已经访问过后才能访问当前的根节点。因此可以通过一个辅助指针r指向最近访问过的结点。也可以在结点中增加一个标志域以记录结点是否被访问过。（以下代码为采用辅助指针r实现的方法）：

void PostOrder(TreeNode* root)
{
    stack<TreeNode*> s;
    TreeNode* p = root;
    TreeNode* r = NULL; //用于记录最近访问结点的指针
    while(p || !s.empty())
    {
        if(p) //还是先一直往左找到尽头
        {
            s.push(p);
            p = p->lp;
        }
        else
        {
            p = s.top(); //注意这时只是取栈顶的值（即最左下方的结点），并不弹栈！（因为有可能还需要访问它的右子树的）
            if(p->rp && p->rp!=r) //若右子树存在，且未被访问过
            {
                p = p->rp; //这里只需将指针指向右孩子即可，这里无需入栈，因为如果右孩子存在的话，下次循环一开始是会入栈的
            }
            else
            {
                s.pop(); //此时结点的左右孩子均不存在了，可以弹栈了（不用再次给p赋值了，易知此时p的值就是栈顶的值）
                Visit(root->data); //访问该结点
                r = p; //一定不要忘了记录此时访问的结点
                p = NULL; //让p指向空，这样可以保证下次循环继续检查栈中的下一个栈顶是否有右子树（因为后序遍历最后指向的是根节点，不同于上面两种遍历，不会是空，所以必须手动给它赋成空值）
            }
        }
    }
}

三、层次遍历

void LevelOrder(TreeNode* root)
{
    queue<TreeNode*> myQueue;
    if(root!=NULL)
        myQueue.push(root);
    while(!myQueue.empty())
    {
        TreeNode* current = myQueue.front();
        myQueue.pop();
        Visit(current->data);
        if(current->lp != NULL)
            myQueue.push(current->lp);
        if(current->rp != NULL)
            myQueue.push(current->rp);
    }
}

四、由先序与中序序列确定二叉树

给定前序遍历字符串序列s1和中序遍历字符串序列s2，要求确定出对应的二叉树：

TreeNode* buildTree(string s1, string s2)
{
    if(s1.length()==0)
        return NULL;
    char nc = s1[0]; //当前前序序列的首个字符，应该作为当前树的根结点
    TreeNode* root = new TreeNode(nc); //创建新结点
    int position = s2.find(nc); //寻找前序序列的首个字符在中序序列中所在的位置，将其作为划分左右子树部分的切分点
    root->lp = buildTree(s1.substr(1, position), s2.substr(0, position));
    root->rp = buildTree(s1.substr(position+1), s2.substr(position+1));
    return root;
}

五、线索二叉树

规定：若无左子树，令lp指向其前驱结点；若无右子树，令rp指向其后继结点。还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继）。

lp	ltag	data	rtag	rp
左孩子结点	左标志域	数据域	右标志域	右孩子结点

其中标志域的含义：
$\rm ltag = \begin{cases} 0, \rm lp域指示结点的左孩子\\ 1, \rm lp域指示结点的前驱\end{cases}\\ \rm rtag = \begin{cases} 0, \rm rp域指示结点的右孩子\\ 1,\rm rp域指示结点的后继\end{cases}\\$
线索二叉树的存储结构：

struct ThreadTreeNode
{
    ElemType data;
    ThreadTreeNode *lp, *rp;
    int ltag, rtag; //左、右线索标志
    ThreadTreeNode(char c): data(c), lp(NULL), rp(NULL), ltag(0), rtag(0) {}
};

首先先把基本的二叉树建立好，这个过程中先不管标志域。
之后在上面建好的基础二叉树上构造线索化二叉树。

线索化二叉树的构造

1、前序线索二叉树的构造：

注意这里参数pre需要用引用。因为一方面递归函数中pre = p这一步是需要对pre做改变的，这个改变需要维持下去，而不是说退到上一层递归后pre就变成之前的值了。另一方面在建线索二叉树的主过程函数中，调用完此函数之后还要对pre结点进行一些后处理（即处理遍历的最后一个结点），因此必须保证使用的pre指针是经过此函数中修改之后的。

void PreThread(ThreadTreeNode* &p, ThreadTreeNode* &pre) //前序线索二叉树的构造
{
    if(p==NULL)
        return;

    if(!p->lp) //若左孩子不存在，则将左指针指向其前驱结点
    {
        p->lp = pre;
        p->ltag = 1;
    }
    if(pre!=NULL && pre->rp==NULL) //若前一个结点的右孩子不存在，则将前一个节点的后继节点指向当前节点
    {
        pre->rp = p;
        pre->rtag = 1;
    }
    pre = p; //标记当前结点成为刚刚访问过的结点
    if(p->ltag==0) //注意这时p的左指针可能已经用作指向前驱结点了，所以要用p->ltag判断是否有左孩子
        PreThread(p->lp, pre);
    if(p->rtag==0) //如果p的右孩子存在
        PreThread(p->rp, pre);
}

void CreatePreThread(ThreadTreeNode* root) //通过前序遍历建立前序线索二叉树的主过程
{
    ThreadTreeNode* pre = NULL; //线索化序列的第一个结点的前驱一定是空的
    if(root!=NULL)
    {
        PreThread(root, pre); //线索化二叉树
        pre->rp = NULL; //处理遍历的最后一个结点
        pre->rtag = 1;
    }
}

2、中序线索二叉树的构造：

void InThread(ThreadTreeNode* &p, ThreadTreeNode* &pre) //中序线索二叉树的构造
{
    if(!p)
        return;
    
    InThread(p->lp, pre); //递归，线索化左子树
    if(!p->lp) //左子树为空，建立前驱线索
    {
        p->lp = pre;
        p->ltag = 1;
    }
    if(pre!=NULL && pre->rp==NULL)
    {
        pre->rp = p;
        pre->rtag = 1;
    }
    pre = p; //标记当前结点成为刚刚访问过的结点
    InThread(p->rp, pre);
}

void CreateInThread(ThreadTreeNode* root) //通过中序遍历建立中序线索二叉树的主过程
{
    ThreadTreeNode* pre = NULL; //线索化序列的第一个结点的前驱一定是空的
    if(root!=NULL)
    {
        InThread(root, pre); //线索化二叉树
        pre->rp = NULL; //处理遍历的最后一个结点
        pre->rtag = 1;
    }
}

3、后序线索二叉树的构造：

由于要得到某结点的后序序列后继可能会需要知道其双亲结点，因此要实现后序线索二叉树的话必须对之前线索二叉树的存储结构做进一步的修改，增加一个指向双亲结点的指针。

具体代码略。

线索化二叉树的遍历

1、前序线索二叉树的遍历

void PreThreadOrder(ThreadTreeNode *p) //遍历前序线索二叉树输出前序序列
{
    if(!p)
        return; //p为空的话无法遍历

    while(1)
    {
        Visit(p->data); //访问当前根结点
        if(p->rp==NULL && p->rtag==1) //p是中序遍历序列的最后一个结点
            break; //遍历结束

        if(p->rtag==0) //p存在右孩子，因此此时p的后继不能直接得到
        {
            if(p->ltag==0) //如果p的左子树存在
                p = p->lp; //那么p的后继就是它的左孩子结点
            else //如果p的左子树不存在而右子树存在（因为上面的if已经限定了p存在右孩子）
                p = p->rp;
        }
        else //p不存在右孩子，因此可以直接通过p->rp得到它的后继结点
            p = p->rp;
    }
    cout<<endl;
}

2、中序线索二叉树的遍历

void InThreadOrder(ThreadTreeNode *p) //遍历中序线索二叉树输出中序序列
{
    if(!p)
        return; //p为空的话无法遍历

    while(p->ltag==0)
        p = p->lp; //找到中序序列下的第一个结点
    Visit(p->data); //访问第一个结点
    while(1)
    {
        if(p->rp==NULL && p->rtag==1) //p是中序遍历序列的最后一个结点
            break; //遍历结束
        if(p->rtag==0) //p存在右孩子，因此此时p的后继不能直接得到，需要到它的右子树中去找
        {
            p = p->rp; //到p的右子树中去找p的后继
            while(p->ltag==0)
                p = p->lp; //和上面找整棵树的第一个结点类似，只不过这里是要找右子树中的第一个结点
        }
        else //p不存在右孩子，因此可以直接通过p->rp得到它的后继结点
            p = p->rp;
        Visit(p->data); //访问新找到的结点
    }
    cout<<endl;
}

其中，求中序线索二叉树中中序序列下的第一个结点，可以单独写成函数：

ThreadTreeNode *Firstnode(ThreadTreeNode *p)
{
    while(p->ltag==0)   
        p = p->lp;
    return p;
}

求中序线索二叉树中结点p在中序序列下的后继，可以写成下面的函数（利用到上面的求第一个结点的函数）：

ThreadTreeNode *Nextnode(ThreadTreeNode *p)
{
    if(p->rtag==0)
        return Firstnode(p->rp);
    else
        return p->rp; //rtag==1直接返回后继线索
}

如果要求倒序输出中序线索二叉树序列，那么可以对上面的两个函数做这样的修改：
Firstnode函数中将ltag和lp换成rtag和rp；
Nextnode函数中将rtag和rp换成ltag和lp。

六、二叉排序树

二叉排序树插入结点

输入一系列整数，建立二叉排序树（输入的数中可能会有相等的情况，实现过程中如果已经有与要插入的数相等的数在树中，那么就不再插入该数了）：

TreeNode* Insert(TreeNode* root, int x)
{
    if(root==NULL) //原树为空，新插入的记录为根结点
        root = new TreeNode(x);
    else if(x < root->data)
        root->lp = Insert(root->lp, x);
    else if(x > root->data)
        root->rp = Insert(root->rp, x);
    //注意x==root->data的情况直接略过，即这种情况便不再插入
    return root;
}

二叉排序树删除结点

删除要求在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。

可分为以下3种情况处理：
①若被删除结点z是叶子结点，则直接将其删除（其双亲结点中相应指针域的值改为NULL）
②若被删结点z只有左子树或者只有右子树，则让其双亲结点的相应指针域的值改为指向被删结点的左子树或右子树。
③如果被删节点z的左右子树均存在，那么需要考虑到该树的中序遍历序列。

结点左右子树均存在的情况.PNG

设情况如上图所示，则该树的中序遍历序列为： $\rm ...,P_L,s,p,P_R,f,...$ 。s是结点*p左子树中最右下方的结点，而且p的直接前驱是s。

有两种方法：
法1：令*p的左子树为*f的左子树，*p的右子树接为*s的右子树。
法2：直接令*s替代*p，*s若有左子树，则将其接为*s的双亲的右子树。（*s没有右子树，因为我们已规定了s是*p左子树中最右下方的结点）

（代码暂略，后续补充）

七、平衡二叉树（AVL树）

保证任意结点的左、右子树高度差的绝对值不超过1，这样的二叉树成为平衡二叉树。左子树与右子树的高度差为该结点的平衡因子，易知平衡二叉树结点的平衡因子的值只可能是-1、0或1。

我们往往希望构成的二叉排序树成为平衡二叉树。于是在二叉排序树进行插入新结点的操作之后，可能就会导致树不再是平衡树，于是需要重新调整树使其变成平衡树。这个过程可归纳为以下4种情况：
①单向右旋平衡处理（LL型）
②单向左旋平衡处理（RR型）
③先左旋后右旋平衡处理（LR型）
④先右旋后左旋平衡处理（RL型）

平衡二叉树.jpg