二叉树的遍历
前序遍历中序遍历后序遍历 三种遍历的递归和非递归方法
/******************************************
* @brief 二叉树的前序、中序、后序遍历
*
*
******************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using std::endl;
using std::cout;
using std::vector;
using std::queue;
using std::stack;
/**
* @brief 树节点结构体
*
**/
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode* m_pLeft = nullptr;
BinaryTreeNode* m_pRight = nullptr;
};
/**
* @brief 声明函数
**/
BinaryTreeNode* Construct(int preOrder[], int inOrder[], int length);
BinaryTreeNode* ConstructCore(int *startPreOrder, int *endPreOrder, int *startInOrder, int *endInOrder);
/**
* @brief
void showVector(vector<int> vec) {
for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
cout << *iter << " ";
}
}
/**
* @brief 根据前序后中序遍历结果构造二叉树
*
**/
BinaryTreeNode* Construct(int preOrder[], int inOrder[], int length) {
if (preOrder == nullptr || inOrder == nullptr || length <= 0) {
return nullptr;
}
return ConstructCore(preOrder, preOrder + length - 1, inOrder, inOrder + length - 1);
}
/**
* @brief 递归构建二叉树
*
**/
BinaryTreeNode* ConstructCore(int *startPreOrder, int *endPreOrder, int *startInOrder, int *endInOrder) {
int rootValue = startPreOrder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->m_nValue = rootValue;
if (startPreOrder == nullptr) {
if (startInOrder == nullptr) {
return root;
}
throw "Invalid input";
}
int* inOrderRoot = startInOrder;
while (inOrderRoot < endInOrder && *inOrderRoot != rootValue) {
++inOrderRoot;
}
if (inOrderRoot == endInOrder && inOrderRoot == nullptr) {
throw "Invalid input";
}
int leftLen = inOrderRoot - startInOrder;
int rightLen = endInOrder - inOrderRoot;
int *endStartPreOrder = startPreOrder + leftLen;
if (leftLen > 0) {
root->m_pLeft=ConstructCore(startPreOrder + 1, endStartPreOrder, startInOrder, inOrderRoot - 1);
}
if (rightLen > 0) {
root->m_pRight = ConstructCore(endStartPreOrder + 1, endPreOrder, inOrderRoot + 1, endInOrder);
}
return root;
}
/**
* @brief 前序遍历
*
**/
void preorderTraversal(BinaryTreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->m_nValue << " ";
preorderTraversal(root->m_pLeft);
preorderTraversal(root->m_pRight);
}
/**
* @brief 中序遍历
*
**/
void inorderTraversal(BinaryTreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->m_pLeft);
cout << root->m_nValue << " ";
inorderTraversal(root->m_pRight);
}
/**
* @brief 后序遍历
*
**/
void postorderTraversal(BinaryTreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->m_pLeft);
postorderTraversal(root->m_pRight);
cout << root->m_nValue << " ";
}
/**
* @brief 前序非递归
*
**/
void preorderTraversal2(BinaryTreeNode* root) {
stack<BinaryTreeNode *> s;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
cout << root->m_nValue << " ";
s.push(root);
root = root->m_pLeft;
}
BinaryTreeNode* node = s.top();
s.pop();
root = node->m_pRight;
}
}
/**
* @brief 中序非递归
*
**/
void inorderTraversal2(BinaryTreeNode *root) {
stack<BinaryTreeNode *> s;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->m_pLeft;
}
BinaryTreeNode *node = s.top();
cout << node->m_nValue << " ";
s.pop();
root = root->m_pRight;
}
}
/**
* @brief 后序非递归
* 巧妙方法: 后序遍历（左->右->根），
* 前序遍历（根->左->右),
* 后序遍历反转: 根->右->左，
*
**/
void postorderTraversal2(BinaryTreeNode *root) {
if (root == nullptr) {
return;
}
vector<int> result;
stack<BinaryTreeNode *> s;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
result.push_back(root->m_nValue);
root = root->m_pRight;
}
BinaryTreeNode* node = s.top();
s.pop();
root = node->m_pLeft;
}
std::reverse(result.begin(), result.end());
showVector(result);
}
/**
* @brief 后序非递归
* 记录节点的访问次数
*
*
**/
void postorderTraversal3(BinaryTreeNode *root) {
if (root == nullptr) {
return;
}
stack<BinaryTreeNode *> s;
BinaryTreeNode* lastVisit = root;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->m_pLeft;
}
BinaryTreeNode* node = s.top();
if (node->m_pRight == nullptr || node->m_pRight == lastVisit) {
s.pop();
cout << node->m_nValue << " ";
lastVisit = node;
} else {
root = node->m_pRight;
}
}
}
int main() {
// 二叉树
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// / \
// 8 9
//
int preOrder[] = {1, 2, 4, 8, 9, 5, 3, 6, 7}; // 前序遍历
int inOrder[] = {8, 4, 9, 2, 5, 1, 6, 3, 7}; // 中序遍历
// 构建二叉树
BinaryTreeNode* tree = Construct(preOrder, inOrder, 9);
// 前序遍历
cout << "前序遍历" << endl;
preorderTraversal(tree);
cout << endl;
// 前序遍历(非递归)
cout << "前序遍历(非递归)" << endl;
preorderTraversal2(tree);
cout << endl;
// 中序遍历
cout << "中序遍历" << endl;
inorderTraversal(tree);
cout << endl;
// 中序遍历(非递归)
cout << "中序遍历(非递归)" << endl;
inorderTraversal(tree);
cout << endl;
// 后序遍历
cout << "后序遍历" << endl;
postorderTraversal(tree);
cout << endl;
// 后序遍历(非递归,方法1)
cout << "后序遍历(非递归,巧妙方法)" << endl;
postorderTraversal2(tree);
cout << endl;
// 后序遍历(非递归,方法2)
cout << "后序遍历(非递归,标记法)" << endl;
postorderTraversal3(tree);
cout << endl;
return 0;
}
Processed:
0.018, SQL:
9
