[꼭대기] 데이터 구조의 이 진 트 리 의 구조 와 옮 겨 다 니 기 (선서, 중 서, 후 서, 차원)

//    .cpp :              。

//



#include "stdafx.h"

#include <iostream>

#define maxSize 10

using namespace std;



typedef struct BinaryTreeNode

{

    char data;

    BinaryTreeNode * leftChild;

    BinaryTreeNode * rightChild;

}Node;

//                    

void MakeBinaryTree(Node** root, char* preOrder, char* midOrder, int length)

{

    if (length == 0)

    {

        (*root) = NULL;

        return;

    }

    (*root) = new Node;

    (*root)->data = *preOrder;



    char * rootplace = strchr(midOrder, (*root)->data);

    if (rootplace == NULL)

    {

        cout <<"input wrong order sample!"<<endl;

    }

    int leftTreeLength = strlen(midOrder) - strlen(rootplace);

    int rightTreeLength = length - leftTreeLength - 1;



    MakeBinaryTree(&(*root)->leftChild, preOrder+1, midOrder, leftTreeLength);

    MakeBinaryTree(&(*root)->rightChild, preOrder+leftTreeLength+1, rootplace+1, rightTreeLength);

}



void PostTraverse(Node* root)

{

    if (root == NULL)

        return;

    PostTraverse(root->leftChild);

    PostTraverse(root->rightChild);

    cout << root->data;

}

void visit(Node *p)

{

	printf("%c ",p->data);

}

//    

void preOrder(Node *p)

{

	if(p==NULL)

		return;

	visit(p);

	preOrder(p->leftChild);

	preOrder(p->rightChild);

}

//    

void inOrder(Node *p)

{

	if(p==NULL)

		return;

	inOrder(p->leftChild);

	visit(p);

	inOrder(p->rightChild);

}

//    

void postOrder(Node *p)

{

	if(p==NULL)

		return;

	postOrder(p->leftChild);

	postOrder(p->rightChild);

	visit(p);

}



//    

typedef struct

{

	Node *data[maxSize];

	int front;

	int rear;

}SqQueue;

void level(Node *&p)

{

	Node *q;

	SqQueue qu;

	qu.front=qu.rear=0;



	qu.rear=(qu.rear+1)%maxSize;

	qu.data[qu.rear]=p;//  



	while(qu.front!=qu.rear)

	{

		qu.front=(qu.front+1)%maxSize;

		q=qu.data[qu.front]; //  



		visit(q);



		if(q->leftChild!=NULL)

		{

			qu.rear=(qu.rear+1)%maxSize;

			qu.data[qu.rear]=q->leftChild;//     

		}

		if(q->rightChild!=NULL)

		{

			qu.rear=(qu.rear+1)%maxSize;

			qu.data[qu.rear]=q->rightChild;//     

		}

	}

}



int _tmain(int argc, _TCHAR* argv[])

{

	char pre[] = "abdeijcfg";

    char mid[] = "dbiejafcg";	//"bdeijafcg"  "dijebfgca"

    Node* r;

    MakeBinaryTree(&r, pre, mid, strlen(pre));//        

	printf("    :");

    preOrder(r);

	printf("
    :");

    inOrder(r);

	printf("
    :");

    postOrder(r);

	printf("
    :");

    level(r);

    return 0;

}