数据结构之 二叉树的构造与遍历(先序，中序，后序，层次)
// 二叉树.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;}