+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(57)

2019-09(98)

2019-10(11)

2019-11(6)

2019-12(14)

数据结构-二叉树的所有遍历

发布于2020-04-23 18:56     阅读(668)     评论(0)     点赞(17)     收藏(5)


准备

typedef struct TressNode
{
  ElementType Date;
  struct TressNode * Left, *Right;
  int num;
}*Tress;

先序遍历

若二叉树非空:

  1. 访问根节点
  2. 先序遍历左子树
  3. 先序遍历右子树

递归实现:

//先序遍历(递归)
void Preorder_TreeWalk(Tress T)
{
  if (T)
  {
    visit(T);
    Preorder_TreeWalk(T->Left);
    Preorder_TreeWalk(T->Right);
  }
}

栈实现:

//先序遍历(栈)
void Preorder(Tress T)
{
  Stack S = Init_Stack(MaxSize);     //初始化栈
  while (T || !Is_Empty(S))          //树为空只代表遍历到了叶子节点,要树为空且堆栈为空才是真正遍历完成
  {
    while (T)
    {
      visit(T);
      Push(S,T->Right);
      T = T->Left;
    }
    if (!Is_Empty(S))
    {
      T = Pop(S);
    }
  }
}

中序遍历

若二叉树非空:

  1. 中序遍历左子树
  2. 访问根节点
  3. 中序遍历右子树

递归实现:

//中序遍历(递归)
void Inorder_TreeWalk(Tress T)
{
  if (T)
  {
    Inorder_TreeWalk(T->Left);
    visit(T);
    Inorder_TreeWalk(T->Right);
  }
}

栈实现:

//中序遍历(栈)
void Inorder(Tress T)
{
  Stack S = Init_Stack(MaxSize);     //初始化栈
  while (T || !Is_Empty(S))          //树为空只代表遍历到了叶子节点,要树为空且堆栈为空才是真正遍历完成
  {
    while (T)
    {
      Push(S,T);
      T = T->Left;
    }
    if (!Is_Empty(S))
    {
      T = Pop(S);
      visit(T);
      T = T->Right;
    }
  }
}

后序遍历

若二叉树非空:

  1. 后序遍历左子树
  2. 后续遍历右子树
  3. 访问根节点

递归实现:

//后序遍历(递归)
void Postorder_TreeWalk(Tress T)
{
  if (T)
  {
    Postorder_TreeWalk(T->Left);
    Postorder_TreeWalk(T->Right);
    visit(T);
  }
}

栈实现:

//后序遍历(栈)
void Postorder(Tress T)
{
  Stack S = Init_Stack(MaxSize);     //初始化栈
  while (T || !Is_Empty(S))
  {
    while (T)
    {
     T->num = 1;
     Push(S,T);
     T = T->Left;
    }
    if (!Is_Empty(S))
    {
      T = Pop(S);
      while (T->num == 2)
      {
        visit(T);
        if (Is_Empty(S))break;
        T = Pop(S);
      }
      if (!Is_Empty(S))
      {
        T->num++;
        Push(S,T);
        T = T->Right;
      }
    }
  }
}

层次遍历

队列实现:
遍历从根节点开始,先将其根节点入队,然后循环:出队,访问,将左右儿子入队。

//层次遍历
void Level_Traversal(Tress T)
{
  if (!T)return;
  Queue Q = Init_Queue(MaxSize);
  EnQueue(Q,T);
  while (!Is_Empty(Q))
  {
    T = DeQueue(Q);
    visit(T);
    if (T->Left)EnQueue(Q,T->Left);
    if (T->Right)EnQueue(Q,T->Right);
  }
}

原文链接:https://blog.csdn.net/lmrcxj/article/details/105663492



所属网站分类: 程序员的那点事

作者:黎明要到来了

链接: https://www.pythonheidong.com/blog/article/339592/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

17 0
收藏该文
已收藏

评论内容:(最多支持255个字符)