Binary Tree Traversal

[jangdelong]

/*
 *  SCUN.Wuhan
 *  Edited By: JangDelong
 *  Student Number: 10066013
 *  Date: 2012.05.10
 *
 *  Program Name:
 *          Binary Tree Traversal
 *
 *
 *
 *
 *
 *
 */
#include <iostream>
#include <cstddef>
#include <queue>
using namespace std;

class BiNode
/* Structure BiNode */
{
public:
    char data;
    BiNode *lchild;
    // Left child
    BiNode *rchild;
    // Right child
};

class BiTree
/* Create class BiTree */
{
private:
    BiNode *root;
    void Free (BiNode *p);         // Delete BiNode
    BiNode* CreateByPreOrder ();   // Create by preorder
    void byPreOrder (BiNode *p);   // by preorder
    void byInOrder (BiNode *p);    // by inorder
    void byPostOrder (BiNode *p);  // by postoder
public:
    BiTree ();          // Intilize Bitree
    void Create ();     // Create BiTree
    ~BiTree ();         // Destroy BiTree.
    void PreOrder ();   // Traversal by preorder
    void InOrder ();    // Traversal by inorder
    void PostOrder ();  // Traversal by postorser
    void LevelPrint (); // Output the result by level

};



int main ()
{
    cout << "|---------------------------------------|\n";
    cout << "|----Edited By: JangDelong<10066013>----|\n";
    cout << "|---------------------------------------|\n";
    BiTree tree;

    //--------------Create the Bitree--------------
    cout << "Create a Binary Tree:\n";
    tree.Create ();
    cout << endl;

    //-----------The Tranversal of Bitree----------
    cout << "Traversal By Preorder:\n";
    tree.PreOrder ();
    cout << endl;
    cout << "Traversal By Inorder:\n";
    tree.InOrder ();
    cout << endl;
    cout << "Traversal By Postorder:\n";
    tree.PostOrder ();
    cout << endl;

    //----------Print the Bitree by level----------
    cout << "Output By Level:\n";
    tree.LevelPrint ();

    return 0;

}


void BiTree::Free (BiNode *p)
/* Implement the fouction Free */
{
    if (p == NULL)
        return;

    Free (p -> lchild);
    Free (p -> rchild);
    delete p;
}
BiNode* BiTree::CreateByPreOrder ()
/* Implement the fouction CreateByPreOrder */
{
    BiNode *p;
    char ch;
    cin >> ch;

    if ('#' == ch)
    {
        p = NULL;
    }
    else
    {
        p = new BiNode;
		p -> data = ch;
        p -> lchild = CreateByPreOrder ();
        p -> rchild = CreateByPreOrder ();
    }

    return p;
}

void BiTree::byPreOrder (BiNode *p)
/* Implement the fouction byPreOrder */
{
    if (p == NULL)
        return;
    cout << p -> data << " ";
    byPreOrder (p -> lchild);
    byPreOrder (p -> rchild);
}

void BiTree::byInOrder (BiNode *p)
/* Implement the fouction byInOrder */
{
    if (p == NULL)
        return;
    byInOrder (p -> lchild);
    cout << p -> data << " ";
    byInOrder (p -> rchild);
}

void BiTree::byPostOrder (BiNode *p)
/* Implement the fouction byPostOrder */
{
    if (p == NULL)
        return;
    byPostOrder (p -> lchild);
    byPostOrder (p -> rchild);
    cout << p -> data << " ";
}



BiTree::BiTree ()
/* Implement default constructor */
{
	root = NULL;
}



void BiTree::Create ()
/* Implement the fouction Create */
{
    cout << "Enter data<'#' Represents NULL>:\n";
    if (root != NULL)
        Free (root);
    root = CreateByPreOrder ();
}

BiTree::~BiTree ()
/* Implement the fouction ~BiTree */
{
    if (root)
        Free (root);
}

void BiTree::PreOrder ()
/* Implement the fouction PreOrder */
{
    byPreOrder (root);
}

void BiTree::InOrder ()
/* Implement the fouction InOrder */
{
    byInOrder (root);
}

void BiTree::PostOrder ()
/* Implement the fouction PostOrder */
{
    byPostOrder (root);
}

void BiTree::LevelPrint ()
/* Implement the fouction Print */
{
    queue<BiNode*> Q;
    if (root == NULL)
        return;
    Q.push (root);
    while (!Q.empty ())
    {
        BiNode *p;
        p = new BiNode;
        p = Q.front ();
        Q.pop ();
        // Out of queue

        cout << p -> data
             << " ";
        if (p -> lchild)
            Q.push (p -> lchild);
        if (p -> rchild)
            Q.push (p -> rchild);
    } // End of while
}