二叉树问题 - 数据结构与算法

问题点数：0 回复次数：11

二叉树问题

学数据结构不久，为何我先序建立二叉树后，不能输出的呢？
#include<iostream>
#include<iomanip>
using namespace std;
#define OVERFLOW 0
#define NULL 0
#define OK 1
typedef int Status;
typedef char ElemType;
typedef struct BiTree
{
ElemType data;
struct BiTree *Lchild;
struct BiTree *Rchild;
}BiTree,*Binary_Tree;
//创建一个二叉树
Status CreateBiTree(Binary_Tree &T)
{
char ch;
   T=(Binary_Tree)malloc(sizeof(BiTree));
   if(!T) exit(OVERFLOW);
   cin>>ch;
   if(ch=='@') T=NULL;
   else
   {
    T->data=ch;
    CreateBiTree(T->Lchild);
    CreateBiTree(T->Rchild);
   }
return OK;
}
//先遍历二叉树
Status PreShowBiTree(Binary_Tree T)
{
if(T!=NULL)
{
   cout<<T->data<<setw(3);
   PreShowBiTree(T->Lchild);
   PreShowBiTree(T->Rchild);
}
return OK;
}
//中遍历二叉树
Status MidShowBiTree(Binary_Tree T)
{
if(T!=NULL)
{
   MidShowBiTree(T->Lchild);
   cout<<T->data<<setw(3);
   MidShowBiTree(T->Rchild);
}
return OK;
}
//后遍历二叉树
Status BehShowBiTree(Binary_Tree T)
{
if(T!=NULL)
{
   BehShowBiTree(T->Lchild);
   BehShowBiTree(T->Rchild);
   cout<<T->data<<setw(3);
}
return OK;
}
int main()
{
BiTree *T;
cout<<"请创建一个二叉树: "<<endl;
CreateBiTree(T);
cout<<"先序遍历: ";
PreShowBiTree(T);
cout<<endl;
cout<<"中序遍历: ";
MidShowBiTree(T);
cout<<endl;
cout<<"后序遍历: ";
BehShowBiTree(T);
cout<<endl;
return 0;
}
比如先后输入ABC@@DE@G@@F@@@ 之后按回车，怎么没有反映的呢？        麻烦帮忙解决下，不胜感激！

搜索更多相关主题的帖子: 二叉树　

第 2 楼

得分:0

cin>>ch;？？？是什么意思啊？

第 3 楼

得分:0

我发现很多没见过的代码啊，我也是刚学数据结构的，你的目的是想做什么啊？是编写先序和后序遍历的吗？给你一个

#include"stdlib.h"
#include"stdio.h"

  typedef char DataType;

  typedef struct Node
  {DataType data;
  struct Node *leftchild;
  struct Node *rightchild;
   }BiTreeNode;

  void Visit(DataType item)
  {printf("%c",item);
  }

void  Destroy(BiTreeNode **root)
{ if((*root)!=NULL&&((*root)->leftchild!=NULL))
     Destroy(&(*root)->leftchild);
     if((*root)!=NULL&&((*root)->rightchild!=NULL))
     Destroy(&(*root)->rightchild);
     free(*root);
     }

  void Initiate(BiTreeNode **root)
  {*root=(BiTreeNode  *)malloc(sizeof(BiTreeNode));
  (*root)->leftchild=NULL;
  (*root)->rightchild=NULL;
  }

BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x)
  {BiTreeNode *s,*t;
  if(curr==NULL)  return NULL;
   t=curr->leftchild;
   s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
   s->data=x;
     s->leftchild=t;
   s->rightchild=NULL;

   curr->leftchild=s;
   return curr->leftchild;
   }

BiTreeNode *InsertRightNode(BiTreeNode *curr,DataType x)
  {  BiTreeNode *s,*t;
    if(curr==NULL)  return NULL;
     t=curr->rightchild;
   s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
   s->data=x;
   s->rightchild=t;
      s->leftchild=NULL;
   curr->rightchild=s;
   return curr->rightchild;
   }

   BiTreeNode *DeleteLeftTree(BiTreeNode *curr)
   {if(curr==NULL||curr->leftchild==NULL)
     return NULL;
     Destroy(&curr->leftchild);
     curr->leftchild=NULL;
     return curr;
     }

     BiTreeNode *DeleteRightTree(BiTreeNode *curr)
   {if(curr==NULL||curr->rightchild==NULL)
     return NULL;
     Destroy(&curr->rightchild);
     curr->rightchild=NULL;
     return curr->rightchild;
     }


     void PreOrder(BiTreeNode *t,void Visit(DataType item))
     {if(t!=NULL)
     {Visit(t->data);
     PreOrder(t->leftchild,Visit);
     PreOrder(t->rightchild,Visit);
     }
     }

     void PostOrder(BiTreeNode *t,void Visit(DataType item))
     {if(t!=NULL)
     { PostOrder(t->leftchild,Visit);
     PostOrder(t->rightchild,Visit);
     Visit(t->data);
     }
     }

     void PrintBiTree(BiTreeNode *bt,int n)
     {int i;
     if(bt==NULL)return;
     PrintBiTree(bt->rightchild,n+1);
     for(i=0;i<n;i++)printf("  ");
     if(n>=0)
     {printf("------");
     printf("%c\n",bt->data);
     }

     PrintBiTree(bt->leftchild,n+1);

     }

     void  main(void)
     {BiTreeNode *root,*p,*pp;
     Initiate(&root);
     p=InsertLeftNode(root,'A');
      p=InsertLeftNode(p,'B');
      p=InsertLeftNode(p,'D');
      p=InsertRightNode(p,'G');
       p=InsertRightNode(root->leftchild,'C');
     pp=p;
     InsertLeftNode(p,'E');
     InsertRightNode(pp,'F');

     PrintBiTree(root,0);
     printf("前序遍历：");
     PreOrder(root->leftchild,Visit);
     printf("\n后序遍历：");
      PostOrder(root->leftchild,Visit);

     Destroy(&root);

     }
    是不是你想要的吗，至于中序你写好一个中序遍历的函数插入到前序遍历跟后序遍历之间就好了！1懂了吧，自己试试看

第 4 楼

得分:0

我也是刚刚学习那个

刚开始我想用我那个验证一下，不过哦我那个不支持C++，所以
我刚才看了看，好像你那个多写了@@，就是最后面的那两个，按照
二叉树的编号，好像与你那个不相符，再好好想想，一定会做出的

第 5 楼

得分:0

以下代码在我的电脑上完全正常。

问题呢，很简单，判断分配内存错误的代码写错了。

要我说，这是个个完全的四不像……C不像C，C++不像C++……虽然它的确可以运行……

程序代码：

#include<iostream>
#include<iomanip>
using namespace std;

#define OVERFLOW 0
#define OK 1

typedef int Status;
typedef char ElemType;

typedef struct BiTree
{
    ElemType data;
    struct BiTree *Lchild;
    struct BiTree *Rchild;
} BiTree, *Binary_Tree;

//创建一个二叉树
Status CreateBiTree(Binary_Tree& T)
{
    char ch;

    T = (Binary_Tree)malloc(sizeof(BiTree));
    if (T == NULL)
        exit(OVERFLOW);
    cin >> ch;
    if (ch == '@')
        T = NULL;
    else
    {
        T->data = ch;
        CreateBiTree(T->Lchild);
        CreateBiTree(T->Rchild);
    }

    return OK;
}

//先遍历二叉树
Status PreShowBiTree(Binary_Tree T)
{
    if (T != NULL)
    {
        cout << T->data << setw(3);
        PreShowBiTree(T->Lchild);
        PreShowBiTree(T->Rchild);
    }
    return OK;
}

//中遍历二叉树
Status MidShowBiTree(Binary_Tree T)
{
    if (T != NULL)
    {
        MidShowBiTree(T->Lchild);
        cout << T->data << setw(3);
        MidShowBiTree(T->Rchild);
    }
    return OK;
}

//后遍历二叉树
Status BehShowBiTree(Binary_Tree T)
{
    if (T != NULL)
    {
        BehShowBiTree(T->Lchild);
        BehShowBiTree(T->Rchild);
        cout << T->data << setw(3);
    }
    return OK;
}

int main()
{
    BiTree *T;
    cout << "请创建一个二叉树: " << endl;
    CreateBiTree(T);
    cout << "先序遍历: ";
    PreShowBiTree(T);
    cout << endl;
    cout << "中序遍历: ";
    MidShowBiTree(T);
    cout << endl;
    cout << "后序遍历: ";
    BehShowBiTree(T);
    cout << endl;
    return 0;
}

专心编程………
飞燕算法初级群：3996098
我的Blog

第 6 楼

得分:0

你输入时有误，就是最后多输入了一个@，你要明白建立二叉树的原理，比如说我输入一段代码：A@B@@就是指A的左子树为空，右子树为B，然后B的左右子树都为空，而且如果你是前序建立一个二叉树就得按前序顺序输入。明白？

第 7 楼

得分:0

这是一个纯正的C++版本：

程序代码：

//http://bbs.bccn.net/viewthread.php?tid=245466&pid=1447570&page=1&extra=page%3D1#pid1447570
#include<iostream>
#include<iomanip>
using namespace std;

template<typename T>
class binary_tree
{
    struct node
    {
        T data;
        node *lchild, *rchild;
    } *m_root;

public:

    enum show_type { ST_PREFIX, ST_MIDDLEFIX, ST_POSTFIX };

    binary_tree() : m_root(NULL)
    {
    }

    ~binary_tree()
    {
        destroy(m_root);
    }

    void create(istream& is, const T& null_data)
    {
        if (m_root != NULL)
            destroy(m_root);

        create(is, null_data, m_root);
    }

    void show(ostream& os, show_type st)
    {
        show(os, m_root, st);
    }

private:

    static void create(istream& is, const T& null_data, node*& root)
    {
        T data;
        is >> data;

        if (data != null_data)
        {
            root = new node;
            root->data = data;
            create(is, null_data, root->lchild);
            create(is, null_data, root->rchild);
        }
        else
            root = NULL;
    }

    static void destroy(node*& root)
    {
        if (root != NULL)
        {
            destroy(root->lchild);
            destroy(root->rchild);
            delete root;
            root = NULL;
        }
    }

    static void show(ostream& os, node* root, show_type st)
    {
        if (root != NULL)
        {
            if (st == ST_PREFIX)
                os << root->data;

            show(os, root->lchild, st);
            if (st == ST_MIDDLEFIX)
                os << root->data;

            show(os, root->rchild, st);
            if (st == ST_POSTFIX)
                os << root->data;
        }
    }
};


int main()
{
    typedef binary_tree<char> bi_tree;
    bi_tree tree;

    cout << "请创建一个二叉树: " << endl;
    tree.create(cin, '@');

    cout << "先序遍历: ";
    tree.show(cout, bi_tree::ST_PREFIX);
    cout << endl;
    cout << "中序遍历: ";
    tree.show(cout, bi_tree::ST_MIDDLEFIX);
    cout << endl;
    cout << "后序遍历: ";
    tree.show(cout, bi_tree::ST_POSTFIX);
    cout << endl;
    return 0;
}

专心编程………
飞燕算法初级群：3996098
我的Blog

第 8 楼

得分:0

[bo][un]jianlian080[/un] 在 2008-11-22 16:45 的发言：[/bo]

你输入时有误，就是最后多输入了一个@，你要明白建立二叉树的原理，比如说我输入一段代码：A@B@@就是指A的左子树为空，右子树为B，然后B的左右子树都为空，而且如果你是前序建立一个二叉树就得按前序顺序输入。明白？ ...

LZ的输入是正确的。ABC@@DE@G@@F@@@产生的树如下

      A
     /
    B
   / \
  C   D
     / \
    E   F
     \
      G

最后一个@表示的是A没有右子树……

专心编程………
飞燕算法初级群：3996098
我的Blog

第 9 楼

得分:0

好厉害

第 10 楼

得分:0

好。。。

在通往牛X的路上我一路狂奔。。。