tree4.cpp

二叉树的遍历,数据结构问题 递归和非递归的都有

// tree4.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include "stdlib.h"
#include <stdio.h>


//二叉树结构体
struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
};
typedef struct BiTNode BiTNode;
typedef struct BiTNode *BiTree;

//递归
void PreOrderTraverse(BiTree T)  //先序
{
    if(T)
    {
        printf("%c ",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
void PostOrderTraverse(BiTree T)  //后序
{
    if(T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c ",T->data);
    }
}
void IntOrderTraverse(BiTree T)   //中序
{
    if(T)
    {
        PostOrderTraverse(T->lchild);
        printf("%c ",T->data);
        PostOrderTraverse(T->rchild);
        
    }
}


//非递归二叉树遍堆栈
struct ABTStack
{
 BiTree *ptree;
 ABTStack *link;
};

/*
 二叉树前序遍历函数pre_Order_Access()<非递归算法>
 参数描述：
  BTNode *head: 二叉树的根节点指针  
*/
void pre_Order_Access(BiTree *head)
{
  BiTree *pt;
  ABTStack *ps,*top;
  pt = head;
  top = NULL;
  printf("\n二叉树的前序遍历结果<非递归>：\n");
  while(pt!=NULL ||top!=NULL)  //二叉树未遍历完,或堆栈非空
  {
     while(pt!=NULL)
	 {
   
          printf("%c ",(*pt)->data);  //访问根节点*
   
          ps = (ABTStack *)malloc(sizeof(ABTStack));  //*根节点进栈
          ps->link = top;
          top = ps;
          (*pt)=(*pt)->lchild; //遍历节点右子树,经过的节点依次进栈
	 }
     if(top!=NULL)
	 {
           pt = top->ptree; //栈顶节点出栈
           ps = top;
           top = top->link;
           free(ps);    //释放栈顶节点空间
           (*pt) = (*pt)->rchild;     //遍历节点右子树
	 }
  }
}



void CreatBiTree(BiTree *T)
{
    char t;
    scanf("%c",&t);
    if(t == '0')
    {
        *T= NULL;
        return;
    }
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = t;//生成根结点
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        CreatBiTree(&(*T)->lchild);//构造左子树
        CreatBiTree(&(*T)->rchild); //构造右子树   
    }
}

int main()
{
    BiTree T;
	printf("创建二叉树（“0”表示空结点）:\n");
    CreatBiTree(&T);
    printf("\n二叉树的递归遍历结果：\n");
	printf("先序遍历:  ");
	PreOrderTraverse(T);
    printf("\n后序遍历:  ");
    PostOrderTraverse(T);
    printf("\n中序遍历:  ");
    IntOrderTraverse(T);
	printf("\n二叉树的前序遍历结果<非递归>：");
	PreOrderTraverse(T);
	//pre_Order_Access(&T);
	printf("\n");
    return 0;
}