// treecros.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

//二叉樹遍歷(遞歸)
#include<iostream.h>

struct node
{
   char data;
   node *left;
   node *right;
};
class tree
{
 public:
    tree(); 
    void Create(node*);
    void Delete(node*);
    void Q(node*);
    void Z(node*);
    void H(node*);
    ~tree();
 private:
    static node *root;
};

node* tree::root=0;
tree::tree()
{
    cout<<"輸入樹的根節點(如果為空輸入#):\t";
    root=new node;
    cin>>root->data;
    Create(root);
}
void tree::Create(node *p)
{
  if(p==NULL)
	  return;

    char x,y; 
	node *q;
    cout<<"輸入節點"<<p->data<<"的左孩子和右孩子:\t";
    cin>>x>>y;
    if(x=='#')
        p->left=0;
    else
	{
        q=new node;
        q->data=x;
        p->left=q;
	}
    if(y=='#')
        p->right=0;
    else
	{
        q=new node;
        q->data=y;
        p->right=q;
	}
    Create(p->left);
    Create(p->right);
}
void tree::Q(node *p=root)
{
 if(p)
 {
  cout<<p->data<<' ';
  Q(p->left);
  Q(p->right);
 }
}

void tree::Z(node *p=root)
{
 if(p)
 {
  Z(p->left);
  cout<<p->data<<' ';
  Z(p->right);
 }
}

void tree::H(node *p=root)
{
 if(p)
 {
  H(p->left); 
  H(p->right);
  cout<<p->data<<' ';
 }
}

tree::~tree()
{
 Delete(root);
}

void tree::Delete(node *p)
{
 if(p)
 {
  Delete(p->left);
  Delete(p->right);
  delete p;
 }
}

void main()
{
 tree h;
 cout<<"樹的前序遍歷:";
 h.Q();
 cout<<"\n樹的中序遍歷:";
 h.Z();
 cout<<"\n樹的后序遍歷:";
 h.H();
} 
/*
已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是
    A）acbed
    B）decab
    C）deabc
    D）cedba

前序遍歷序列:cedba
二叉樹圖形如下:

              c
             /
           e
          / \
        d   b
               \
                 a
*/