数据结构之 二叉树的构造与遍历(先序，中序，后序，层次)

// 二叉树.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#define maxSize 10using 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("\n中序遍历:");    inOrder(r);printf("\n后序遍历:");    postOrder(r);printf("\n层次遍历:");    level(r);    return 0;}