二叉树的遍历

二叉树节点的结构

typedef char ElemType;
typedef struct bt_node{
  ElemType data;
  struct bt_node *leftchild;
  struct bt_node *rightchild;
}bt_node;

创建二叉树,将二叉树树补充为完全二叉树，空的用“#”代替
　　图如下所示：
二叉树的遍历

//通过用户输入创建二叉树
bt_node * Creat1() 
{
  bt_node *root = NULL;
  ElemType item;
  scanf("%c", &item);  //ABC##DE##F##G#H##
  if (item != '#') 
  {
      root = (bt_node *)malloc(sizeof(bt_node));
      root->data = item;
      root->leftchild = creat();
      root->rightchild = creat();
  }
  return root;
}
//事先写好，直接传入字符串创建二叉树
bt_node * Create2(char *&str)  //引用传参
{
  bt_node *s = NULL;
  if (str != NULL && *str != '#')
  {
      s = (bt_node *)malloc(sizeof(bt_node));
      s->data = *str;
      s->leftchild = Create(++str);
      s->rightchild = Create(++str);
  }
  return s;
}
bt_node * Create3(char ** const pstr)  //二级指针传参
{
  bt_node *s = NULL;
  if(pstr != NULL && *pstr != NULL && **pstr != '#')
  {
      s = (bt_node *)malloc(sizeof(bt_node));
      s->data = **pstr;
      s->leftchild = CreateTree3(&++*pstr);
      s->rightchild = CreateTree3(&++*pstr);
  }
  return s;
}

二叉树的递归深度遍历

//二叉树的先序遍历
void PreOrder(bt_node *ptr)
{
  if(ptr != NULL)
  {
      printf("%c ",ptr->data);
      PreOrder(ptr->leftchild);
      PreOrder(ptr->rightchild);
  }
}
//二叉树的中序遍历
void InOrder(bt_node *ptr)
{
  if(ptr != NULL)
  {
      InOrder(ptr->leftchild);
      printf("%c ",ptr->data);
      InOrder(ptr->rightchild);
  }
}
//二叉树的后序遍历
void PastOrder(bt_node *ptr)
{
  if(ptr != NULL)
  {
      PastOrder(ptr->leftchild);
      PastOrder(ptr->rightchild);    
      printf("%c ",ptr->data);
  }
}

二叉树的非递归深度遍历，用栈实现
　树的后序遍历的思考流程图如下所示：
二叉树的遍历

//二叉树的先序遍历
void NicePreOrder(bt_node *ptr)
{
  if(ptr == NULL) return ; // if(NULL == ptr) return ;
  Stack st;
  Init_Stack(&st);
  push(&st,ptr);
  while(!empty(&st))
  {
      ptr = top(&st); pop(&st);
      printf("%c ",ptr->data);
      if(ptr->rightchild != NULL)
          push(&st,ptr->rightchild);
      if(ptr->leftchild != NULL)
          push(&st,ptr->leftchild);
  }
}
//二叉树的中序遍历
void NiceInOrder(bt_node *ptr)
{
  if(ptr == NULL) return ;
  Stack st;  // 元素类型为bt_node*;
  Init_Stack(&st);

  while(ptr !=  || !empty(&st))
  {
      while(ptr != NULL)
      {
          push(&st,ptr);
          ptr = ptr->leftchild;
      }
      ptr = top(&st); pop(&st);
      printf("%c ",ptr->data);
      ptr = ptr->rightchild;
  }
}
//二叉树的后序遍历
void NicePastOrder(bt_node *ptr)
{
  if(ptr == NULL) return ;
  Stack st; // 元素类型为bt_node *;
  Init_Stack(&st);
  bt_node *tag = NULL;  //记录前一个访问的几点

  while(ptr != NULL || !empty(&st))
  {
      while(ptr != NULL)
      {
          push(&st,ptr);
          ptr = ptr->leftchild;
      }
      ptr = top(&st); pop(&st);
      if(ptr->rightchild == NULL || ptr->rightchild == tag)  //该节点无左右孩子节点或者右节点已访问过，则打印
      {
          printf("%c ",ptr->data);
          tag = ptr;
          ptr = NULL;
      }
      else 
      {
          push(&st,ptr);
          ptr = ptr->rightchild;
      }
  }
}

二叉树的层次遍历(广度遍历)，用队列实现

int levelorder(bt_node *ptr)
{
  if (ptr == NULL)
  {
      return 0;
  }
  sq_queue q; //定义一个 顺序队列 
  init_squeue(&q);
  in_squeue(&q, ptr);
  while (lenth_squeue(&q) != 0)
  {
      bt_node *temp=(bt_node*)malloc(sizeof(bt_node));
      temp=out_squeue(&q);
      printf("%c ", temp->data);
      if (temp->leftchild != NULL)
      {
          in_squeue(&q, temp->leftchild);
      }
      if (temp->rightchild != NULL)
      {
          in_squeue(&q, temp->rightchild);
      }
  }
}

二叉树的遍历

二叉树的遍历

相关推荐