Question

编程实现以上二叉树中序遍历操作，输出遍历序列，求写代码~~

Answer 1

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

#define OK  1
#define ERROR  0
#define OVERFLOW  0

typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
 TElemType data;
 struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef enum {Link,Thread} PointerTag;
typedef struct BiThrNode
{
 TElemType data;
 struct BiThrNode *lchild,*rchild;
 PointerTag LTag,RTag;
}BiThrNode;
typedef BiThrNode *BiThrTree;

BiTree CreateBiTree(BiTree T)    //先序遍历构造二叉树
{
 char ch;
 scanf("%c",&ch);
 if(ch=='#')    //#代表空指针
  T=NULL;
 else
 {
  T=(BiTNode *)malloc(sizeof(BiTNode));    //申请结点
  if(!T)
   exit(OVERFLOW);
  T->data=ch;    //生成根结点
  T->lchild=CreateBiTree(T->lchild);    //构造左子树
  T->rchild=CreateBiTree(T->rchild);    //构造右子树
 }
 return T;
}

Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{//中序遍历二叉树
 if(T)
 {
  if(InOrderTraverse(T->lchild,visit))
   if(visit(T->data))
    if(InOrderTraverse(T->rchild,visit))
     return OK;
  return ERROR;
 }
 else
  return OK;
}

Status PrintElement(TElemType e)
{
 printf("%-2c",e);
 return OK;
}

void main()
{
 BiTree T=NULL;
 printf("请输入构造二叉树的字符序列：");
 T=CreateBiTree(T);
 if(T)
  printf("二叉树建立成功！\n");
 else
  printf("二叉树构造失败！！！\n");
 printf("中序遍历二叉树：");
 InOrderTraverse(T,PrintElement);
 printf("\n");
}

Answer 2

#include <iostream>
#define MAXSIZE 100
using namespace std;
typedef char TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
bool InOrderTraverse1(BiTree T) {
if(T) {
cout<<T->data;
InOrderTraverse1(T->lchild);
InOrderTraverse1(T->rchild);
}
}
bool InOrderTraverse2(BiTree T) {
if(T) {
InOrderTraverse2(T->lchild);
cout<<T->data;
InOrderTraverse2(T->rchild);
}
}
bool InOrderTraverse3(BiTree T) {
if(T) {
InOrderTraverse3(T->lchild);
InOrderTraverse3(T->rchild);
cout<<T->data;
}
}
bool CreateBiTree(BiTree &T) {
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else {
T=new BiTNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
int Depth(BiTree T) {
int n,m;
if(T==NULL)
return 0;
else {
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n)
return(m+1);
else
return(n+1);
}
}
int NodeCount(BiTree T) {
if(T==NULL)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int main()
{
BiTree a;
int height,num;
cout<<"请输入二叉树的元素:\n";
CreateBiTree(a);
cout<<"先序遍历法输出：\n";
InOrderTraverse1(a);
cout<<"\n中序遍历法输出：\n";
InOrderTraverse2(a);
cout<<"\n后序遍历法输出：\n";
InOrderTraverse3(a);
height=Depth(a);
num=NodeCount(a);
cout<<"\n该二叉树深度为：";
cout<<height<<endl;
cout<<"该二叉树结点数为：";
cout<<num;
return 0;
}