treecros.cpp

快速遍历二叉树的几种算法

// 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
*/