非递归遍历二叉树.cpp

遍历是二叉树经常要遇到的一种操作.可以运用到二叉树结点计数,线索化二叉树,求二叉树的深度,表达式求值等算法中.在遍历的过程中,对结点的访问具有普遍的含义,可以是输出各结点的数据域信息,也可以是对结点作

#include <stdio.h>
#include <stdlib.h>
typedef struct Bitree_Node       /*树节点结构体*/
{
  int adjvex;
  struct Bitree_Node *lchild;
  struct Bitree_Node *rchild;
}BN;

typedef struct relation_list       /*保存节点关系的链表*/
{                         
  BN *father;
  BN *rchild;
  struct relation_list *next;
}RL;

typedef struct Bitree_Stack_Node
{
  BN *elem;
  struct Bitree_Stack_Node *next;
}BSN;

typedef struct Bitree_Stack     
{
  BSN *bottom;
  BSN *top;
}BS;

typedef struct Bitree     /*树结构体*/
{
  int Vnum;
  BN *head;
}Bitree;

typedef struct Bitree_List_Node       /*"树节点链表"的节点*/
{
  BN *elem;
  struct Bitree_List_Node *next;
}BLN;

typedef struct Bitree_List       /*树节点链表*/
{
  BLN *head;
  BLN *last;
}BL;

void error(BL *list,Bitree *Tree)
{
  free(list->head);
  free(Tree->head);
  printf("内存分配失败，程序结束!");
  getchar();
  exit(-1);
}

void initqueue(BL *list)
{
  list->head=(BLN *)malloc(sizeof(BLN));
  if(list->head==NULL)
  {
    printf("内存分配失败！程序结束！");
    getchar();
    exit(-1);
  }
  list->head->next=NULL;
  list->last=list->head;
}

void enqueue(BL *list,BN *latest,Bitree *Tree)
{
  BLN *temp;
  temp=(BLN *)malloc(sizeof(BLN));
  if(!temp)
    error(list,Tree);
  temp->next=NULL;
  temp->elem=latest;
  list->last->next=temp;
  list->last=temp;
}

BN* dequeue(BL *list)
{
  BLN *temp;
  BN *treenode;
  temp=list->head->next;
  if(temp==list->last)
    list->last=list->head;
  list->head->next=temp->next;
  treenode=temp->elem;
  free(temp);
  return treenode;
}

int build_other_node(Bitree *Tree,BL *list,int Vnum)
{
  int name;
  BN *latest,*old;
  while(list->head!=list->last)
  {
    old=dequeue(list);
    printf("输入%d的左孩子名称(输入负数则没有)：",old->adjvex);
    scanf("%d",&name);
    if(name<0)
        old->lchild=NULL;
    else
    {
        Vnum++;
        latest=(BN *)malloc(sizeof(BN));
        if(!latest)
          error(list,Tree);
        old->lchild=latest;
        latest->adjvex=name;
        enqueue(list,latest,Tree);
    }
    printf("输入%d的右孩子名称(输入负数则没有)：",old->adjvex);
    scanf("%d",&name);
    if(name<0)
        old->rchild=NULL;
    else
    {
        Vnum++;
        latest=(BN *)malloc(sizeof(BN));
        if(!latest)
          error(list,Tree);
        old->rchild=latest;
        latest->adjvex=name;
        enqueue(list,latest,Tree);
    }
  }
  return Vnum;
}

void build_tree(Bitree *Tree,BL *list)
{
  int name,Vnum;
  BN *temp;
  temp=(BN *)malloc(sizeof(BN));
  if(!temp)
    exit(-1);
  Tree->head=temp;
  Tree->head->lchild=NULL;
  printf("请输入第一个节点的名称(负数则没有节点):");
  scanf("%d",&name);
  if(name<0)
  {
    Tree->Vnum=0;
    return;
  }
  temp=(BN *)malloc(sizeof(BN));
  if(!temp)
    error(list,Tree);
  Vnum=1;
  Tree->head->lchild=temp;
  temp->adjvex=name;
  enqueue(list,temp,Tree);
  (Tree->Vnum)=build_other_node(Tree,list,Vnum);
}

void init_stack(BS *stack)         //创建栈底头节点
{
  stack->bottom=(BSN *)malloc(sizeof(BSN));
  if(stack->bottom==NULL)
    exit(-1);
  stack->top=stack->bottom;
  stack->bottom->next=NULL;
}

void enstack(BS *stack,BN *p)       //节点进栈
{
  BSN *temp;
  temp=(BSN *)malloc(sizeof(BSN));
  if(!temp)
    exit(-1);
  temp->next=stack->top;
  temp->elem=p;
  stack->top=temp;
}

BN *destack(BS *stack)             //节点出栈
{
  BN *p;
  BSN *temp;
  temp=stack->top;
  stack->top=temp->next;
  p=temp->elem;
  free(temp);
  return p;
}

RL *init_relation_list()
{
  RL *head;
  head=(RL *)malloc(sizeof(RL));
  if(!head)
    exit(-1);
  head->next=NULL;
  return head;
}

void save_relation(RL *head,BN *father,BN *rchild)//保存父亲和右孩子关系 
{
  RL *insert;
  insert=(RL *)malloc(sizeof(RL));
  if(!insert)
  {
    free(head);
    exit(-1);
  }
  insert->father=father;
  insert->rchild=rchild;
  insert->next=head->next;
  head->next=insert;
}

void restore_relation(RL *head)
{
  RL *p;
  p=head->next;
  while(p)
  {
    p->father->rchild=p->rchild;
    p=p->next;
  }
  free(head);
}

void No_recursion_preorder(BN *root,BS *stack)   //非递归前序遍历 
{
  BN *p;
  p=root;
  while(p || (stack->bottom!=stack->top))
  {
    if(p)
    {
        printf("       %2d",p->adjvex);
        enstack(stack,p);
        p=p->lchild;
    }
    else
    {
        p=destack(stack);
        p=p->rchild;
    }
  }
}

void No_recursion_inorder(BN *root,BS *stack)   //非递归中序遍历 
{
  BN *p;
  p=root;
  while(p || (stack->bottom!=stack->top))
  {
    if(p)
    {
        enstack(stack,p);
        p=p->lchild;
    }
    else
    {
        p=destack(stack);
        printf("       %2d",p->adjvex);
        p=p->rchild;
    }
  }
}

void No_recursion_postorder(BN *root,BS *stack)   //非递归后序遍历 
{
  BN *p;
  RL *head;       //保存关系的链表头指针 
  p=root;
  head=init_relation_list();
  while(p || (stack->bottom!=stack->top))   //p不为NULL或者栈非空则继续循环 
  {
    if(p)
    {
        enstack(stack,p);
        if(p->lchild)
          p=p->lchild;
        else
        {
          p=p->rchild;   //没有左子树的话，右子树进栈 
          if(p)       //若有右子树,把该节点和他的右子树 
          {           //的内存地址保存下来。 
            save_relation(head,stack->top->elem,p);
            stack->top->elem->rchild=NULL; //断开父子关系 
          }                       //从而避免重复进栈 
        }
    }               //若某节点的右孩子指针为NULL 
    else             //可能是没有右孩子或者右孩子已进栈，即已经断开了父子关系 
    {
        p=destack(stack);
        printf("        %d",p->adjvex);
        if(stack->bottom!=stack->top)   //栈非空的话，栈顶元素 
        {                       //的右孩子进栈 
          p=stack->top->elem;
          p=p->rchild;
          if(!p)
              continue;
          save_relation(head,stack->top->elem,p);
          stack->top->elem->rchild=NULL;
        }
        else
          break;                 //栈已空，遍历结束 
    }
  }
  restore_relation(head);     //由于遍历的时候破坏了节点的父子关系 
}                     //遍历完了要将关系恢复过来 

int main()
{
  BL list;
  Bitree Tree;
  BS stack;
  int i,j=1;
  init_stack(&stack);
  initqueue(&list);
  build_tree(&Tree,&list);
  printf("该树共有%d个节点.\n",Tree.Vnum);
  while(j)
  {
    printf("\n\n哪种遍历方法：\n\n");
    printf("      1.非递归前序遍历\n      2.非递归中序遍历\n");
	printf("      3.非递归后序遍历\n      4.退出\n");
    scanf("%d",&i);printf("\n");
    switch(i)
    {
        case 1:
          No_recursion_preorder(Tree.head->lchild,&stack);
          continue;
        case 2:
          No_recursion_inorder(Tree.head->lchild,&stack);
          continue;
        case 3:
          No_recursion_postorder(Tree.head->lchild,&stack);
          continue;
        default:
          j=0;
          break;
    }
  }
  return 0;
}