学步园

// 树6.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
using namespace std;
//-------------------二叉树的二叉链表存储表示---------------------------
typedef struct BiTNode{
 char data;
 struct BiTNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;

int InitBiTree(BiTree *T)
{    //构造空二叉树
 *T=NULL;
 return true;
}
void DestroyBiTree(BiTree *T)
{ //初始条件:二叉树T存在，操作结果:销毁二叉树
 if(*T)//非空树
 {
  if((*T)->lchild)
   DestroyBiTree(&(*T)->lchild);//销毁左孩子树
  if((*T)->rchild)
   DestroyBiTree(&(*T)->rchild);//销毁右孩子树
  free(*T);//释放根结点
  *T=NULL;//空指针
 }
}
void CreateBiTree(BiTree *T)
{
 //按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树
 //构造二叉链表表示的二叉树T
 char ch;
 cin>>ch;
 if(ch=='#') *T=NULL;
 else{
  *T=(BiTree)malloc(sizeof(BiTNode));
        (*T)->data=ch;
  CreateBiTree(&(*T)->lchild);//递归构造左子树;
  CreateBiTree(&(*T)->rchild);//递归构造右子树；
 }
}
int PreOrderTraverse(BiTree T)
{
 //初始条件:二叉树T存在,visit是对结点操作的应用函数
 //操作结果:先序遍历T,对每个结点调用函数VIsit
 if(T)//T非空
 {
  cout<<T->data<<" ";
  PreOrderTraverse(T->lchild);//递归调用,先序遍历左子树
  PreOrderTraverse(T->rchild);//递归调用,最后先序遍历右子树
 }
 return false;
}

void InOrder(BiTree &T) //中序遍历以T为根指针的二叉树
{
 if(T){   //二叉树不为空
  InOrder(T->lchild);//先遍历左孩子树
  cout<<T->data<<" ";//访问根结点
  InOrder(T->rchild);//最后遍历右孩子树
 }
}

void PostOrder(BiTree &T)//后序遍历以T为根结点的二叉树
{
 if(T)//二叉树不为空
 {
  PostOrder(T->lchild);//先遍历左孩子树
  PostOrder(T->rchild);//遍历右孩子树
  cout<<T->data<<" ";//访问根结点
 }
}
void DispBTree(BiTree &bt)
{
if (bt!=NULL)
{
cout<<bt->data;
if (bt->rchild!=NULL||bt->lchild!=NULL)
{
cout<<"(";
DispBTree(bt->lchild);
if (bt->rchild!=NULL)cout<<",";
DispBTree(bt->rchild);
cout<<")";
}
}
}

int main(int argc, char* argv[])
{
 cout << "请依次输入字符: ABD#G##E##C#FH###" << endl;
 BiTree T;
 InitBiTree(&T);
 CreateBiTree(&T);
 cout<<"先序遍历"<<endl;
 PreOrderTraverse(T);
 cout<<"/n中序遍历"<<endl;
 InOrder(T);
 cout<<"/n后序遍历"<<endl;
 PostOrder(T);
 cout<<"用括号表示输出二叉树"<<endl;
 DispBTree(T);
 return 0;
}