二叉树的遍历
#include <iostream>
#include <cstring>
#define maxLength 32
using namespace std;
typedef struct binaryNode
{
char data;
struct binaryNode *lchild, *rchild;
} binaryNode;
void createByPreAndIn(char preArray[], char inArray[], binaryNode *&parent, int preStart, int preEnd, int inStart, int inEnd);
void createByLastAndIn(char lastArray[], char inArray[], binaryNode *&parent, int lastEnd, int lastStart, int inStart, int inEnd);
void preOrderVisit(binaryNode *root);
void inOrderVisit(binaryNode *root);
void lastOrderVisit(binaryNode *root);
void rugged(binaryNode *root,int);
void brackets(binaryNode *root);
void level(binaryNode *root);
void display(binaryNode *root);
int main(void)
{
char preArray[maxLength], inArray[maxLength], lastArray[maxLength];
binaryNode *root;
cout<<"构造二叉树，输入构造方式。(1代表前中序，其它数字代表后中序): ";
int way;
cin>>way;
if(way==1)
{
cout << "输入前序遍历序列: ";
cin >> preArray;
cout << "输入中序遍历序列: ";
cin >> inArray;
createByPreAndIn(preArray, inArray, root, 0, strlen(preArray) - 1, 0, strlen(inArray) - 1);
}
else if(way==2)
{
cout << "输入后序遍历序列: ";
cin >> lastArray;
cout << "输入中序遍历序列: ";
cin >> inArray;
createByLastAndIn(lastArray, inArray, root, 0, strlen(lastArray) - 1, 0, strlen(inArray) - 1);
}//initialization
cout<<"构造完成,下列是该二叉树的表示方式"<<endl;
display(root);
cout<<"按enter键继续...";
cin.get(); cin.get();
return 0;
}
void createByPreAndIn(char preArray[], char inArray[],binaryNode *&parent, int preStart, int preEnd, int inStart, int inEnd)
{
if (preStart <= preEnd)
{
parent = new binaryNode;
parent->data = preArray[preStart], parent->lchild = parent->rchild = NULL;
int middle = inStart;
while (inArray[middle] != preArray[preStart] && middle <= inEnd)
middle++;
createByPreAndIn(preArray, inArray, parent->lchild, preStart + 1, preStart+middle-inStart, inStart, middle - 1);
createByPreAndIn(preArray, inArray, parent->rchild, preStart + middle - inStart + 1, preEnd, middle + 1, inEnd);
}
}
void createByLastAndIn(char lastArray[], char inArray[], binaryNode *&parent, int lastStart, int lastEnd, int inStart, int inEnd)
{
if (lastStart <= lastEnd)
{
parent = new binaryNode;
parent->data = lastArray[lastEnd], parent->lchild = parent->rchild = NULL;
int middle = inStart;
while (inArray[middle] != lastArray[lastEnd] && middle <= inEnd)
middle++;
createByLastAndIn(lastArray, inArray, parent->lchild, lastEnd - inEnd + inStart, lastEnd - inEnd + middle - 1, inStart, middle - 1);
createByLastAndIn(lastArray, inArray, parent->rchild, lastEnd - inEnd + middle, lastEnd - 1, middle + 1, inEnd);
}
}
void preOrderVisit(binaryNode *root)
{
if (root)
{
std::cout << root->data;
preOrderVisit(root->lchild);
preOrderVisit(root->rchild);
}
}
void inOrderVisit(binaryNode *root)
{
if (root)
{
inOrderVisit(root->lchild);
std::cout << root->data;
inOrderVisit(root->rchild);
}
}
void lastOrderVisit(binaryNode *root)
{
if (root)
{
lastOrderVisit(root->lchild);
lastOrderVisit(root->rchild);
cout << root->data;
}
}
void rugged(binaryNode *root, int indent)
{
if (root)
{
for (int j = 0; j < indent; j++)
std::cout << "-";
indent++;
std::cout << root->data;
std::cout << std::endl;
rugged(root->lchild, indent + 1);
rugged(root->rchild, indent + 1);
}
}
void level(binaryNode *root)
{
int front = -1, rear = 0;
binaryNode *buff[maxLength],*visit;
buff[rear] = root;
while (front != rear)
{
front = (front + 1) % maxLength;
visit = buff[front];
if (visit->lchild)
{
rear = (rear + 1) % maxLength;
buff[rear] = visit->lchild;
}
if (visit->rchild)
{
rear = (rear + 1) % maxLength;
buff[rear] = visit->rchild;
}
cout << visit->data;
}
}
void brackets(binaryNode *root)
{
if (root)
{
std::cout << root->data;
if (root->lchild || root->rchild)
std::cout << '(';
brackets(root->lchild);
if(root->lchild && root->rchild)
std::cout << ',';
brackets(root->rchild);
if (root->lchild || root->rchild)
std::cout << ')';
}
}
void display(binaryNode *root)
{
cout << "前序遍历: ";
preOrderVisit(root);
cout << endl;
cout << "中序遍历: ";
inOrderVisit(root);
cout << endl;
cout << "后序遍历: ";
lastOrderVisit(root);
cout << endl;
cout << "层次遍历: " << endl;
level(root);
cout << endl;
cout << "凹入表示法: " << endl;
rugged(root, 0);
cout << endl;
cout << "括号表示法: " << endl;
brackets(root);
cout << endl;
}
本回答被网友采纳