二叉树.txt

程序设计比赛较为实用的一些代码,希望对别人能有帮助

#include <stdio.h>
#include <iostream>
#include <queue>
#include <stack>
#include <malloc.h>
#define SIZE 100

using namespace std;

typedef struct     BiTNode         //定义二叉树节点结构
{
char     data;                        //数据域
struct BiTNode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;

int visit(BiTree t);
void CreateBiTree(BiTree &T);       //生成一个二叉树
void PreOrder(BiTree);             //递归先序遍历二叉树
void InOrder(BiTree);              //递归中序遍历二叉树
void PostOrder(BiTree);            //递归后序遍历二叉树
void InOrderTraverse(BiTree T); //非递归中序遍历二叉树
void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树
void LeverTraverse(BiTree T);//非递归层序遍历二叉树


//主函数
void main()
{
BiTree T;       
char j;
int flag=1;
//---------------------程序解说-----------------------
printf("本程序实现二叉树的操作。\n");
printf("叶子结点以空格表示。\n");
printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n");
//----------------------------------------------------
printf("\n");
printf("请建立二叉树。\n");
printf("建树将以三个空格后回车结束。\n");
printf("例如:1 2 3 4 5 6      (回车)\n"); CreateBiTree(T);          //初始化队列
getchar();
while(flag)
       {
     printf("\n");
     printf("请选择: \n");
     printf("1.递归先序遍历\n");
     printf("2.递归中序遍历\n");
     printf("3.递归后序遍历\n");
     printf("4.非递归中序遍历\n");
     printf("5.非递归先序遍历\n");
     printf("6.非递归层序遍历\n");
     printf("0.退出程序\n");
     scanf(" %c",&j);
     switch(j)
     {
      case '1':if(T)
               {
       printf("递归先序遍历二叉树:");
       PreOrder(T);
       printf("\n");
                }
      else printf("二叉树为空!\n");
      break;
      case '2':if(T)
               {
       printf("递归中序遍历二叉树:");
       InOrder(T);
       printf("\n");
               }
      else printf("二叉树为空!\n");
      break;
      case '3':if(T)
               {
       printf("递归后序遍历二叉树:");
       PostOrder(T);
       printf("\n");
               }
      else printf("二叉树为空!\n");
      break;
      case '4':if(T)
               {
       printf("非递归中序遍历二叉树:");
       InOrderTraverse(T);
       printf("\n");
               }
      else printf("二叉树为空!\n");
      break;
      case '5':if(T)
               {
       printf("非递归先序遍历二叉树:");
       PreOrder_Nonrecursive(T);
       printf("\n");
               }
      else printf("二叉树为空!\n");
      break; 
      case '6':if(T)
               {
       printf("非递归层序遍历二叉树:");
       LeverTraverse(T);
       printf("\n");
               }
      else printf("二叉树为空!\n");
      break; 
      default:flag=0;printf("程序运行结束，按任意键退出!\n");
     }
       }

}

//建立二叉树
void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);       //读入一个字符   
if(ch==' ') T=NULL;
else 
{
     T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点
     T->data=ch;
     CreateBiTree(T->lchild);     //生成左子树
     CreateBiTree(T->rchild);     //生成右子树
        }
}

//先序遍历的递归
void PreOrder(BiTree T)
{
if(T)
{
     printf("%c ",T->data);     //访问结点
     PreOrder(T->lchild);      //遍历左子树
     PreOrder(T->rchild);      //遍历右子树
}
}

//中序遍历的递归
void InOrder(BiTree T)
{
if(T)
{
     InOrder(T->lchild);      //遍历左子树 
     printf("%c ",T->data); //访问结点
     InOrder(T->rchild);      //遍历右子树
}
}

//后序遍历的递归
void PostOrder(BiTree T)
{
if(T)
{
     PostOrder(T->lchild); //遍历左子树
     PostOrder(T->rchild); //访问结点
     printf("%c ",T->data); //遍历右子树
}
}

//非递归中序遍历   
void InOrderTraverse(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);//跟指针进栈
while(!S.empty())
{
     p=new BiTNode;
     while((p=S.top())&&p)
      S.push(p->lchild);//向左走到尽头
     S.pop(); //空指针退栈
     if(!S.empty())
     {
      p=S.top();
      S.pop();
      cout<<p->data<<"     ";
      S.push(p->rchild);
     }
}

}

//先序遍历的非递归
void PreOrder_Nonrecursive(BiTree T)
{
stack<BiTree> S;
BiTree p;

S.push(T);//根指针进栈
while(!S.empty())//栈空时结束
{
     while((p=S.top())&&p)
     {
      cout<<p->data<<"     ";
      S.push(p->lchild);
     }//向左走到尽头
     S.pop();//弹出堆栈
     if(!S.empty())
     {
      p=S.top();
      S.pop();
      S.push(p->rchild);//向右走一步
     }
}
}


void LeverTraverse(BiTree T)
{//非递归层次遍历
queue <BiTree> Q;
BiTree p;
p = T;
if(visit(p)==1)
     Q.push(p);
while(!Q.empty())
{
     p = Q.front();
     Q.pop();
     if(visit(p->lchild) == 1) 
      Q.push(p->lchild);
     if(visit(p->rchild) == 1)
      Q.push(p->rchild);
}
}

int visit(BiTree T)
{
if(T)
{
     printf("%c ",T->data);
     return 1;
}
else
     return 0;

}