非递归后序遍历二叉树版本二,数据结构学习第四弹

思路:

二叉树的遍历

二叉树的操作有许各个,当中最常用的是二叉树的遍历。二叉树的遍历是指依据某种顺序访谈二叉树中的每种结点,使得各种结点都被仅且采访贰次。
通过叁回完整的遍历,可使二叉树中的结点由原先的非线性系列变为某种意义的线性系列。依照根节点访谈的相继不一致,遍历的相继分为前序遍历,中序遍历,后序遍历。

标识一个结点的左右子树是还是不是早就被访问过,叶子节点也拓宽标志

二叉树的遍历方法与算法达成

澳门新葡亰平台官网 1

二叉树

拓展:

先序遍历

先序遍历的递归定义:要是二叉树为空,则遍历的结果为空,不然:

  • 拜会根节点
  • 先序遍历左子树
  • 先序遍历右子树

以上海教室作为遍历对象的话:

  • 先拜谒根节点A
  • 先序遍历根节点的左子树,然后继续依据先序遍历的黄金年代生龙活虎

  • 先拜访结点B

  • 访谈结点D
    • 左子树为空
    • 访问结点E
  • 做客结点f
    • 访谈结点G
    • 右子树为空
  • 会见右子树结点C

最终获得的遍历种类为: ABDEfGC

遍历进程中读者会开采,某有时刻,从栈底到栈顶的元素刚好构成当前访谈节点的到根节点的门路。利用那大器晚成特点能够兑现七个算法:(1)根到某节点的门道(2)八个节点的近日公共祖先

二叉树先序遍历递归算法的兑现

void Preorder(BinTree t)
{
    if(t!=NULL)
    {
        printf("%c ",t->data);
        preOrder(t->leftChild);
        preOrder(t->rightChild);
    }
}

typeDef struct{

二叉树先序遍历非递归算法的落实

因为举办的依次为从根节点起始,沿着左子树一向找下去,找到底,然后回来到这两日找过的结点的右子树。所以必要记录探问过的根节点,便于往回走,由于是先让根节点二个个记录起来,然后在回来的时候找前段时间刚找过的根节点,所以相符栈的特征(先进先出),用顺序栈存款和储蓄就可以。

#define MAXSIZE 100
void Preorder2(BinTree t)
{
    if(t==NULL)
        return ;
    BinTree stack[MAXSIZE],p;
    int top = 0;
    p = t;
    //找到底,且栈中没有可以回去的结点时,遍历结束
    while(p!=NULL || top>0)
    {
        //找左子树,找到头为止
        while(p!=NULL)
        {
            printf("%c ",p->data);  //访问结点的指针域
            if(top<MAXSIZE-1)
            {
                stack[top] = p;
                p++;
            }
            else
            {
                printf("errorn");
                return ;
            }
        }
        //找右子树
        --top;
        p = stack[top];
        p = p->rightChild;
    }
}
BiTree t;
int tag;

澳门新葡亰平台官网 ,按先序系列建设构造二叉树

创建二叉树时的输入的树为把树的每一个叶子结点的孩子结点填充为’#’。

void CreatBintree(BinTree *root)
{
    char ch;
    if((ch=getchar())=='#') //从键盘上输入二叉树结点数值到#截止
        *root = NULL
    else
    {
        *root = (BinNode*)malloc(sizeof(BinNode));
        (*root)->data = ch;
        CreatBintree(&((*root)->leftChild));
        CreatBintree(&((*root)->rightChild));
    }
}

}Stack

中序遍历

中序遍历的递归定义:倘诺二叉树为空,则遍历的结果为空,不然:

  • 中序遍历根节点的左子树
  • 拜会根节点
  • 中序遍历根节点的右子树

有了先序遍历的经历,以上海教室作为遍历对象的话:
终极获得的遍历连串为:DEBGfAC

发表评论

电子邮件地址不会被公开。 必填项已用*标注