树与二叉树 - 树与二叉树代码必背 - 《算法设计》

二叉树的遍历与线索二叉树

二叉树的遍历与线索二叉树

中序遍历非递归

// 使用栈结构，23王道书p141
void InOrder(BiTree T)
{
    InitStack(S);            // 初始化栈
    BiTree p = T;            // p为遍历指针
    while(p || !IsEmpty(S)) // p非空或者栈非空,后者为了保证出栈的合法性
    {
        if(p)               // 一路向左
        {
            Push(S,p);        // 当前节点入栈
            p = p->lchild;    // 用左孩子更新p
        }
        else
        {
            Pop(S,p);         // 出栈
            visit(p);        // 访问出栈节点，弹出后才可以
            p = p->rchild;  // 用右孩子更新p
        }
    }
}

先序遍历非递归

// 使用栈结构，23王道书p141
void InOrder(BiTree T)
{
    InitStack(S);            // 初始化栈
    BiTree p = T;            // p为遍历指针
    while(p || !IsEmpty(S)) // p非空或者栈非空,后者为了保证出栈的合法性
    {
        if(p)               // 一路向左
        {
            visit(p);        // 访问出栈节点
            Push(S,p);        // 当前节点入栈
            p = p->lchild;    // 用左孩子更新p
        }
        else
        {
            Pop(S,p);         // 出栈
            p = p->rchild;  // 用右孩子更新p
        }
    }
}

后序遍历非递归

// 使用栈结构，23王道书p157
// 王道视频中说可以改先序为后序(先序互换左右孩子+一个新栈控制出栈的时机)，如果考场忘了以下代码
void PostOrder(BiTree T)
{
    InitStack(S);            // 初始化栈
    BiTree p = T;            // p为遍历指针
    r = NULL;                // 增加辅助指针r，指向最近被访问过的节点
    while(p || !IsEmpty(S)) // p非空或者栈非空,后者为了保证出栈的合法性
    {
        if(p)               // 一路向左
        {   Push(S,p);        // 当前节点入栈
            p = p->lchild;    // 用左孩子更新p
        }
        else
        {
            GetTop(S,p);    // 读取栈顶元素，与先中序的差异，重点记忆理解区别
            if(p->rchild&&p->rchild! = r)// 右子树存在且未被访问过
                p= p->rchild;             // 用右孩子更新p
            else
            {
            Pop(S,p);         // 出栈
            visit(p);        // 访问该节点，弹出后才可以
            r = p             // 用右孩子更新p
            p = NULL;          // 节点访问完，重置p,让第一个if不执行
            }
        }
    }
}

计算树的高度

递归

int Btdepth2(BiTree T)
{
    int ldep,rdep;// 分别定义左右树高度
    if(T == NULL)// 空树为0
        return 0;
    ldep = Btdepth(T->lchild);// 左子树高度
    rdep = Btdepth(T->rchild);// 右子树高度
    if(ldep > rdep)
        return ldep+1;        // 树的高度为子树最大高度加根节点
    else
        return rdep+1;
}

非递归

// 层次遍历非递归算法,使用一般的队列,统一++k的模式
int Btdepth(BiTree T){
    if(!T)
        return 0;
    int front = -1, rear = -1;// 初始队头队尾-1
    int last = 0,level = 0;  // last只被rear赋值，与front比较,记录每一层最右侧节点
    BiTree Q[MaxSize];         // 队列Q，存储指针元素，空间足够
    Q[++rear] = T;             // 根节点入队
    BiTree p;                 // 工作指针p
    while(front < rear)     //     队列非空
        p = Q[++front];
    if(p->lchild)
        Q[++rear] = p->lchild; // 左孩子入队
    if(p->rchild)
        Q[++rear] = p->rchild; // 右孩子入队
    if (front == last)           // 处理该层最右侧节点
    {
        ++level;              //层数+1
        last = rear;          // last改变为下一层
    }  
}

拓展：该算法可以修改用于验证是否一棵二叉树是满二叉树，利用 2^h-1 =n

// 队列判完全二叉树,算法的关键部分可以嵌套记忆
bool IsComplete(BiTree T){
    InitQueue(Q);
    if(!T)
         reuturn 1;       // 空树为满二叉树
    EnQueue(Q,T);
    while(!IsEmpty)
        DeQueue(Q,p);
        if(p)
        {            
            EnQueue(Q,p->lchild); 
            EnQueue(Q,p->rchild);
        }
         else
         {
        while(!IsEmpty)
        DeQueue(Q,p);
        if(p)             // 结点非空，则二叉树为非完全二叉树
            return 0;
         }
}

判断完全二叉树

// 队列判完全二叉树,算法的关键部分可以嵌套记忆
bool IsComplete(BiTree T){
    InitQueue(Q);
    if(!T)
         reuturn 1;       // 空树为满二叉树
    EnQueue(Q,T);
    while(!IsEmpty(Q))
        DeQueue(Q,p);
        if(p)
        {            
            EnQueue(Q,p->lchild); 
            EnQueue(Q,p->rchild);
        }
         else
         {
        while(!IsEmpty)
        DeQueue(Q,p);
        if(p)             // 结点非空，则二叉树为非完全二叉树
            return 0;
         }
}

删除树中x为root的子树

// 后序递归删除
void DeleteXTree(BiTree *bt)
{
    //先删除左右孩子才能free根节点x
    DeleteXTree((*bt)->lchild);//左
    DeleteXTree((*bt)->rchild);//右
    free((*bt));               //根
}
// 层次遍历+队列，不是删除的节点就入队列，是就删除该节点
// 用层次遍历容易找到某个节点的父节点,要遍历完整二叉树
void Search(BiTree T)
{    BiTree Q[];// 二叉树队列
    BiTNode *p;
     if(T)
    {
    if(T->data == x)
    {
        DeleteXTree(&T);
        exit(0);
    }
    InitQueue(Q);
    EnQueue(Q,bt);
    while(!isEmpty(Q)){// 如果队列不为空
        DeQueue(Q,p);
        if(p->lchild)                   // 左子女非空
        {
           if(p->lchild->data == x)        // 符合x的节点，删除
                DeleteXTree(&(p->lchild));
                p->lchild = NULL;        // 左孩子置空，防止野指针
            else                          
                EnQueue(Q,p->lchild);   // 不符合x的节点，入队
        }
        if(p->rchild)                     // 右子女非空
        {
            if(p->rchild->data == x)   // 符合x的节点，删除
                DeleteXTree(&(p->rchild));
                p->rchild = NULL;     // 右孩子置空，防止野指针
            else
                EnQueue(Q,p->rchild); // 不符合x的节点，入队
        }
    }
}

任意两节点找公共祖先结点（链式存储的存储结构）

// 方法一：递归来自知乎
BiTNode * Ancestor(BiTNode *ROOT,BiTNode *p,BiTNode*q)
{
    if(ROOT== NULL || node1 == NULL || node2 == NULL)
                       return NULL;
    if(node1 == ROOT || node2 == NULL)
                       return ROOT;
    BiTNode * lacs = Ancestor(ROOT->left,p,q);
    BiTNode * racs = Ancestor(ROOT->right,p,q);
       if(lacs && racs)
        return root;
    if(lacs == NULL)
        return racs;
    else
       return lacs;
}

// 容易想到是后序遍历，而且容易想到非递归的后序遍历，即利用栈
// 来自csdn,几乎是两遍后序非递归，代码长，但对称度极高,比王道参考书给出的更容易想到
void Ancestor(BiTNode *ROOT,BiTNode *p,BiTNode*q)
{
    Stack S1;
    Stack S2;
    InitStack(S1);            // 初始化栈S1
    InitStack(S2);            // 初始化栈S2
    BiTree b1 = T;            
    BiTree b2 = T;             
    BiTree r = NULL;        // 增加辅助指针r，指向最近被访问过的节点
    while(b1 || !IsEmpty(S1)) // p非空或者栈非空,后者为了保证出栈的合法性
    {
        if(b1)               // 一路向左
        {   Push(S,b1);        // 当前节点入栈
            b1 = b1->lchild;    // 用左孩子更新p
        }
        else
        {
            GetTop(S1,b1);    // 读取栈顶元素，与先中序的差异，重点记忆理解区别
            if(b1->data == p)
                break;
            if(b1->rchild&&b1->rchild! = r)// 右子树存在且未被访问过
                b1= b1->rchild;             // 用右孩子更新p
            else
            {
            Pop(S1,b1);         // 出栈
            r = b1                // 更新r
            b1 = NULL;          // 节点访问完，重置p,让第一个if不执行
            }
        }
    }
    // 以下while以上面完全对称
     while(b2 || !IsEmpty(S2)) // b2非空或者栈非空,后者为了保证出栈的合法性
    {
        if(b2)               // 一路向左
        {   Push(S2,b2);        // 当前节点入栈
            b2 = b2->lchild;    // 用左孩子更新b2
        }
        else
        {
            GetTop(S2,b2);    // 读取栈顶元素，与先中序的差异，重点记忆理解区别
            /*****/
            if(b2->data == q)
                break;
            /*****/
            if(b2->rchild&&b2->rchild! = r)// 右子树存在且未被访问过
                b2= b2->rchild;             // 用右孩子更新b2
            else
            {
            Pop(S2,b2);         // 出栈
            r = b2                // 更新r
            b2 = NULL;          // 节点访问完，重置b2,让第一个if不执行
            }
        }
    }
    while( !IsEmpty(S1)&&!IsEmpty(S2))
    {
    BiTNode *m1,*m2;
    Pop(S1,m1);
    Pop(S2,m2);
    if(m1->data == m2->data)
        return p;
    }
   return NULL;
}

任意两节点找最近公共祖先结点（顺序存储的存储结构）

按照完全二叉树的顺序，空结点用0元素填充，完全二叉树的性质，任意节点，其左节点为2i,右节点2i-1

tips:可以采取栈的方式记录人一个节点的查询路径，查询任意一个节点的根节点的index

// 顺序存储二叉树的最近公共祖先
// 自写参考
int ComAncestor(SqTree T,int i,int j)
{    int p,q;                    // 取栈顶元素
    InitStack(S1);
     InitStack(S2);
    if(T.data[i])
         Push(S1,i])     // 元素入栈
    if(T.data[j])
         Push(S1,j)     // 元素入栈
    while(T.data[i]&&i>=1)
        Push(S1,i/2]) // 父节点入栈，只到根节点入栈     
    while(T.data[j]&&j>=1)
        Push(S2,j/2]) // 父节点入栈，只到根节点入栈   
    // 逆向出栈，index大的先出栈
     while(!IsEmpty(S1)&&!IsEmpty(S2))
     {
         p = GetTop(S1);
         q = GetTop(S2);
          if (p < q)
             q = GetTop(S2);
         else if(p > q)
             p = GetTop(S1);
         else if(p == q)
             return p;
     }
}

// 标准答案,思路差不多，就是节点的index大的减半,不过最后返回元素
ElemType Comm_Ancestor(SqTree T,int i,int j)
{
    //本算法目的判断顺序存储的二叉树的最近公共节点
    if(T[i]!="#"&&T[j]!="#")
    {
        while(i != j)
        { 
         if(i > j)
            i = i/2;
        else 
            j = j/2;
        }
        return T[i];
    }
}