《数据结构》复习笔记--二叉树2

前端之家收集整理的这篇文章主要介绍了《数据结构》复习笔记--二叉树2前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

二叉树的非递归遍历:

中序遍历非递归遍历算法
非递归算法实现的基本思路:使用堆栈:

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

 
 
 
 
void PostOrder_NoRecurse(BinTree BT,void (*Do)(BinTree))//非递归实现后序遍历
{
    BinTree T = BT;
    Stack s = CreateStack(20);
    int Tag[20];   //Tag用来标记第几次遇到堆栈内的元素,本身是一个整形堆栈
    while(T || !Stack_IsEmpty(s))
    {
        while(T)    //每遇到一个新元素,则到控制到此处
        {
            Stack_Push(s,T); //放入堆栈并循环至其最左
            Tag[s->size - 1] = 0;
            T = T->Left;
        }
        while (!T && !Stack_IsEmpty(s))
        {
            T = Stack_Pop(s); //取出堆栈中的一个元素,并判断它的Tag
            if(Tag[s->size])
            {
                (*Do)(T);   //Tag != 0 说明是第三次遇见该节点,对它进行操作
                T = 0;        //将T设为0以触发While条件,继续循环
            }
            else            //Tag = 0 说明是第二次遇见(第一次是将Tag设为0)
            {
                if (!T->Right) (*Do)(T);   //如果右儿子不存在,则直接输出
                else
                {
                    Stack_Push(s,T);      //如果右儿子存在,则将它放回堆栈
                    Tag[s->size - 1]++;        //并累加相应的Tag
                }
                T = T->Right;  //返回右儿子。注意,如果右儿子不存在,则会触发While继续循环
            }                   //否则会判定为遇见新元素跳出循环,继续外部外部的大While循环
        }
    }
}
由两种遍历序列确定二叉树?

已知三种遍历中的任意两种遍历序列,能否唯一确定一棵二叉树呢?我们知道,无论哪一种,必须要先知道先序遍历。

比如:先序和中序遍历序列来确定一棵二叉树
〖分析〗
1根据先序遍历序列第一个结点确定根结点;
2根据根结点在中序遍历序列中分割出左右两个子序列
3对左子树和右子树分别递归使用相同的方法继续分解。

题目练习:过几天再贴上。

猜你在找的数据结构相关文章