数据结构二叉树有关问题

2012-06-01

数据结构二叉树问题求建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（线序，中序和后序），打印输出便利

数据结构二叉树问题
求建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（线序，中序和后序），打印输出便利结果的可运行通过的程序。
测试数据ABC##DE#G##F###
求高手指教

[解决办法]
主要采用的数据结构如下：

Java code

// 二叉树节点类class BNode {    Object element;// 存放的数据    BNode left;// 左孩子    BNode right;// 右孩子}
[解决办法]
递归调用
nest（note*）
{
next（note*）
visit（）
next（note*）
}
[解决办法]
C/C++ code#include <stdio.h>#include <stdlib.h>typedef struct BiTNode{    char data;    struct BiTNode *lchild;    struct BiTNode *rchild;} BiTNode;BiTNode *CreatBiTree();void PreOrderTraverse(BiTNode *);void InOrderTraverse(BiTNode *);void PostOrderTraverse(BiTNode *);void DestroyBiTree(BiTNode **);int main(){    BiTNode *pT = CreatBiTree();    PreOrderTraverse(pT);    printf("\n");    InOrderTraverse(pT);    printf("\n");    PostOrderTraverse(pT);    printf("\n");    DestroyBiTree(&pT);    return 0;}BiTNode *CreatBiTree(){    char ch;    BiTNode *p;    ch = getchar();    if (ch == EOF)        return NULL;    getchar();    p = (BiTNode *)malloc(sizeof(BiTNode));    p->data = ch;    p->lchild = CreatBiTree();    p->rchild = CreatBiTree();    return p;}void PreOrderTraverse(BiTNode *pT){    if (pT != NULL)    {        printf("%c ", pT->data);        PreOrderTraverse(pT->lchild);        PreOrderTraverse(pT->rchild);    }}void InOrderTraverse(BiTNode *pT){    if (pT != NULL)    {        InOrderTraverse(pT->lchild);        printf("%c ", pT->data);        InOrderTraverse(pT->rchild);    }}void PostOrderTraverse(BiTNode *pT){    if (pT != NULL)    {        PostOrderTraverse(pT->lchild);        PostOrderTraverse(pT->rchild);        printf("%c ", pT->data);    }}void DestroyBiTree(BiTNode **pT){    if (*pT != NULL)    {         DestroyBiTree(&(*pT)->lchild);         DestroyBiTree(&(*pT)->rchild);         free(*pT);    }}
[解决办法]
#include<stdio.h>
#include<stdlib.h>
typedef struct binode
{
char data;
struct binode *lchild,*rchild;
}binode,*bitree;
///////////////////////////////////////////////////
bitree createbitree()
{
bitree t;
char x;
     x=getchar();
if(x=='#')
t=NULL;
else
{
t=(binode*)malloc(sizeof(binode));
t->data=x;
t->lchild=createbitree();
t->rchild=createbitree();
}
return t;
}
////////////////////////////////////////////////////
void preordertraverse(bitree t)
{
if(t)
{

printf("%4c",t->data);
      preordertraverse(t->lchild);
   preordertraverse(t->rchild);
   }
}
////////////////////////////////////////////////////
void preordertraverse2(bitree t)
{
if(t)
{
preordertraverse2(t->lchild);
preordertraverse2(t->rchild);
printf("%4c",t->data);
   }
}
//////////////////////////////////////
void preordertraverse3(bitree t)
{
if(t)
{

       preordertraverse3(t->lchild);
      printf("%4c",t->data);
   preordertraverse3(t->rchild);
   }
}
/////////////////////////////////////////////
int main()
{
bitree t;
t=createbitree();
printf("前序遍历：\n");
   preordertraverse(t);
printf("\n");
printf("中序遍历：\n");
   preordertraverse2(t);
printf("\n");
printf("后序遍历：\n"); 
 
   preordertraverse3(t);
printf("\n");
return 0;
}

热点排行

软件架构设计

数据结构二叉树有关问题