【23王道数据结构】根据先序中序(中序后序)建立二叉树，并遍历

思路

已知先序中序

TreeNode* ConstructTree(char pre[], int preStart, int preEnd, char in[], int inStart, int inEnd) {if (preStart > preEnd || inStart > inEnd) return NULL;TreeNode *root = (TreeNode *) malloc(sizeof (TreeNode));root->data = pre[preStart];//cout << "Constructor: root->data = " << root->data << endl;for (int i = inStart; i <= inEnd; i++) {//在中序序列中找到root的值if (in[i] == pre[preStart]) {//cout << "Constructor: i = " << i<< endl;root->lchild = ConstructTree(pre, preStart + 1, preStart + i - inStart,in, inStart, i - 1);root->rchild = ConstructTree(pre, preStart + i - inStart + 1, preEnd,in, i + 1, inEnd);}}return root;
}

已知后序中序

TreeNode* ConstructTree(char post[], int postStart, int postEnd, char in[], int inStart, int inEnd) {if (postStart > postEnd || inStart > inEnd) return NULL;TreeNode *root = (TreeNode*) malloc(sizeof (TreeNode));root->data = post[postEnd];for (int i = inStart; i <= inEnd; i++) {if (in[i] == post[postEnd]) {root->lchild = ConstructTree(post,postStart,postStart + i - inStart - 1,in, inStart, i - 1);root->rchild = ConstructTree(post, postStart + i - inStart,postEnd - 1,in, i + 1, inEnd);}}return root;
}

全部代码

//
// 根据前序中序构建二叉树
// Created by 48272 on 2022/4/25.
//
#include <iostream>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>using namespace std;typedef struct TreeNode{char data;struct TreeNode *lchild, *rchild;
}TreeNode, *BiTree;/*** pre ABCDEFGHI* in BCAEDGHIF* @param pre* @param preStart* @param preEnd* @param in* @param inStart* @param inEnd* @return*/
TreeNode* ConstructTree(char pre[], int preStart, int preEnd, char in[], int inStart, int inEnd);/*** 中序遍历* @param root* @return*/
vector<char> inOrder(BiTree root);/*** 层次遍历* @param root* @return*/
vector<char> levelOrder(BiTree root);/*** 先序遍历* @param root* @return*/
vector<char> preOrder(BiTree root);int main() {char pre[9] = {'A','B','C','D','E','F','G','H','I'};char in[9] = {'B','C','A','E','D','G','H','F','I'};BiTree root = ConstructTree(pre, 0, 8, in, 0, 8);cout << "中序遍历:\n";vector<char> inorder =  inOrder(root);for (auto &item: inorder) cout << item;cout <<endl;cout << "层次遍历:\n";vector<char> levelorder = levelOrder(root);for (auto &item: levelorder) cout << item;cout << endl;cout << "先序遍历:\n";vector<char> preorder = preOrder(root);for (auto &item: preorder) cout << item;cout << endl;return 0;
}TreeNode* ConstructTree(char pre[], int preStart, int preEnd, char in[], int inStart, int inEnd) {if (preStart > preEnd || inStart > inEnd) return NULL;TreeNode *root = (TreeNode *) malloc(sizeof (TreeNode));root->data = pre[preStart];//cout << "Constructor: root->data = " << root->data << endl;for (int i = inStart; i <= inEnd; i++) {//在中序序列中找到root的值if (in[i] == pre[preStart]) {//cout << "Constructor: i = " << i<< endl;root->lchild = ConstructTree(pre, preStart + 1, preStart + i - inStart,in, inStart, i - 1);root->rchild = ConstructTree(pre, preStart + i - inStart + 1, preEnd,in, i + 1, inEnd);}}return root;
}vector<char> preOrder(BiTree root) {if (!root) return {};vector<char> preorder;TreeNode *p = root;stack<TreeNode*> s;while (p || !s.empty()) {// 有左孩子 一直向左走if (p) {preorder.push_back(p->data);s.push(p);p = p->lchild;}else { //否则取出栈顶，找右孩子p = s.top();s.pop();p = p->rchild;}}return preorder;
}vector<char> inOrder(BiTree root) {if (!root) return {};vector<char> inorder;TreeNode *p = root;stack<TreeNode*> s;while (p || !s.empty()) {// 有左孩子 一直向左走if (p) {s.push(p);p = p->lchild;}else { //否则取出栈顶，找右孩子p = s.top();s.pop();inorder.push_back(p->data);p = p->rchild;}}return inorder;
}vector<char> levelOrder(BiTree root) {if (!root) return {};vector<char> levelOrder;queue<TreeNode*> level;level.push(root);while (!level.empty()) {TreeNode *t = level.front();level.pop();levelOrder.push_back(t->data);if (t->lchild) level.push(t->lchild);if (t->rchild) level.push(t->rchild);}return levelOrder;
}