二叉树的定义及其相关算法
//header.h
#pragma once
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
template<typename T>
struct TreeNode
{
T Value;
TreeNode* leftChild;
TreeNode* rightChild;
TreeNode(const T& value)
: Value{
value }, leftChild{
nullptr }, rightChild{
nullptr }
{
//std::cout << "Creating TreeNode: " << Value << '\n';
}
~TreeNode()
{
//std::cout << "Destroying TreeNode: " << Value << '\n';
}
};
template<typename T>
class BinaryTree
{
private:
TreeNode<T>* root;
public:
BinaryTree() : root{
nullptr } {
}
BinaryTree& insert(const T& value);
//层序遍历
const BinaryTree& hierarchicalTraversal() const;
//先序遍历序列
const BinaryTree& preOrderTraversal(std::vector<T>& preOrder) const;
//中序遍历序列
const BinaryTree& inOrderTraversal(std::vector<T>& inOrder) const;
//后序遍历序列
const BinaryTree& postOrderTraversal(std::vector<T>& postOrder) const;
//从先序和中序遍历序列构建二叉树
BinaryTree& buildTreeFromPreAndInOrder(std::vector<T>& preOrder, std::vector<T>& inOrder);
//从中序和后续遍历序列构建二叉树
BinaryTree& buildTreeFromInAndPostOrder(std::vector<T>& inOrder, std::vector<T>& postOrder);
//从先序遍历序列序列化二叉树
std::string serializeFromPreOrder() const;
//从中序遍历序列序列化二叉树
std::string serializeFromInOrder() const;
//从后序遍历序列序列化二叉树
std::string serializeFromPostOrder() const;
//从先序遍历序列反序列化二叉树
BinaryTree& deserializeFromPreOrder(std::string data);
//从中序遍历序列反序列化二叉树
BinaryTree& deserializeFromInOrder(std::string data);
//从后序遍历序列反序列化二叉树
BinaryTree& deserializeFromPostOrder(std::string data);
~BinaryTree();
};
//二叉平凡树插入算法
template<typename T>
BinaryTree<T>& BinaryTree<T>::insert(const T& value)
{
TreeNode<T>* newNode = new TreeNode<T>{
value };
if (this->root == nullptr)
{
this->root = newNode;
return *this;
}
TreeNode<T>* temp = nullptr;
bool flag = true;
std::queue<TreeNode<T>*> que{
};
que.push(this->root);
while (flag)
{
int n = que.size();
for (int i = 0; i < n; ++i)
{
temp = que.front();
que.pop();
if (temp->leftChild == nullptr)
{
temp->leftChild = newNode;
flag = false;
break;
}
else
{
que.push(temp->leftChild);
}
if (temp->rightChild == nullptr)
{
temp->rightChild = newNode;
flag = false;
break;
}
else
{
que.push(temp->rightChild);
}
}
}
return *this;
}
template<typename T>
const BinaryTree<T>& BinaryTree<T>::hierarchicalTraversal() const
{
if (this->root == nullptr)
{
std::cout << "This binary tree is empty!!! Can not hierarchicalTraversal!!!\n";
return *this;
}
std::cout << "HierarchicalTraversal as belows:\n";
TreeNode<T>* temp = nullptr;
std::queue<TreeNode<T>*> helper;
helper.push(this->root);
while (!helper.empty())
{
int n = helper.size();
//for循环可以清晰地看出是层上的遍历
for (int i = 0; i < n; ++i)
{
temp = helper.front();
helper.pop();
std::cout << temp->Value << '\t';
if (temp->leftChild)
helper.push(temp->leftChild);
if (temp->rightChild)
helper.push(temp->rightChild);
}
}
std::cout << '\n';
return *this;
}
template<typename T>
const BinaryTree<T>& BinaryTree<T>::preOrderTraversal(std::vector<T>& preOrder) const
{
if (this->root == nullptr)
{
std::cout << "This binary tree is empty!!! Can not preOrderTraversal!!!\n";
return *this;
}
std::cout << "PreOrderTraversal as belows:\n";
TreeNode<T>* temp = this->root;
std::stack<TreeNode<T>*> stk{
};
while (temp != nullptr || !stk.empty())
{
//这个循环会持续找左孩子节点直到到达底部
while (temp)
{
//入栈的时候先入根节点，再入左孩子节点，所以打印二叉树的前序遍历
std::cout << temp->Value << '\t';
preOrder.emplace_back(temp->Value);
stk.push(temp);
temp = temp->leftChild;
}
//到底部时temp == nullptr，所以不会进行上面的内层循环
//持续外层循环并弹出栈顶节点直到该节点有右孩子节点为止(遍历完左子树弹出根节点后开始遍历右子树)
temp = stk.top();
stk.pop();
temp = temp->rightChild;
}
std::cout << '\n';
return *this;
}
template<typename T>
const BinaryTree<T>& BinaryTree<T>::inOrderTraversal(std::vector<T>& inOrder) const
{
if (this->root == nullptr)
{
std::cout << "This binary tree is empty!!! Can not inOrderTraversal!!!\n";
return *this;
}
std::cout << "InOrderTraversal as belows:\n";
TreeNode<T>* temp = this->root;
std::stack<TreeNode<T>*> stk{
};
while (temp != nullptr || !stk.empty())
{
while (temp)
{
stk.push(temp);
temp = temp->leftChild;
}
//先弹出左孩子节点，再弹出根节点，所以打印二叉树的中序遍历
temp = stk.top();
stk.pop();
std::cout << temp->Value << '\t';
inOrder.emplace_back(temp->Value);
temp = temp->rightChild;
}
std::cout << '\n';
return *this;
}
template<typename T>
const BinaryTree<T>& BinaryTree<T>::postOrderTraversal(std::vector<T>& postOrder) const
{
if (this->root == nullptr)
{
std::cout << "This binary tree is empty!!! Can not postOrderTraversal!!!\n";
return *this;
}
std::cout << "PostOrderTraversal as belows:\n";
std::stack<TreeNode<T>*> stk;
TreeNode<T>* temp = this->root;
TreeNode<T>* prev = nullptr;
while (temp != nullptr || !stk.empty())
{
while (temp != nullptr)
{
stk.push(temp);
temp = temp->leftChild;
}
temp = stk.top();
stk.pop();
if (temp->rightChild == nullptr || temp->rightChild == prev)
{
std::cout << temp->Value << '\t';
postOrder.emplace_back(temp->Value);
prev = temp;
temp = nullptr;
}
else
{
stk.push(temp);
temp = temp->rightChild;
}
}
std::cout << '\n';
return *this;
}
template<typename T>
BinaryTree<T>& BinaryTree<T>::buildTreeFromPreAndInOrder(std::vector<T>& preOrder, std::vector<T>& inOrder)
{
if (preOrder.size() == 0)
{
return *this;
}
this->root = new TreeNode<T>{
preOrder[0] };
std::stack<TreeNode<T>*> stk;
stk.push(this->root);
int inOrderIndex = 0;
int preOrderSize = preOrder.size();
for (int i = 1; i < preOrderSize; ++i)
{
int preOrderVal = preOrder[i];
TreeNode<T>* node = stk.top();
if (node->Value != inOrder[inOrderIndex])
{
node->leftChild = new TreeNode<T>(preOrderVal);
stk.push(node->leftChild);
}
else
{
while (!stk.empty() && stk.top()->Value == inOrder[inOrderIndex])
{
node = stk.top();
stk.pop();
++inOrderIndex;
}
node->rightChild = new TreeNode<T>{
preOrderVal };
stk.push(node->rightChild);
}
}
return *this;
}
template<typename T>
BinaryTree<T>& BinaryTree<T>::buildTreeFromInAndPostOrder(std::vector<T>& inOrder, std::vector<T>& postOrder)
{
if (postOrder.size() == 0)
{
return *this;
}
this->root = new TreeNode<T>{
postOrder[postOrder.size() - 1] };
std::stack<TreeNode<T>*> stk;
stk.push(this->root);
int inOrderIndex = inOrder.size() - 1;
int postOrderSize = postOrder.size();
for (int i = postOrderSize - 2; i >= 0; i--)
{
int postOrderVal = postOrder[i];
TreeNode<T>* node = stk.top();
if (node->Value != inOrder[inOrderIndex])
{
node->rightChild = new TreeNode<T>{
postOrderVal };
stk.push(node->rightChild);
}
else
{
while (!stk.empty() && stk.top()->Value == inOrder[inOrderIndex])
{
node = stk.top();
stk.pop();
inOrderIndex--;
}
node->leftChild = new TreeNode<T>{
postOrderVal };
stk.push(node->leftChild);
}
}
return *this;
}
template<typename T>
std::string serializationFromPreOrder(TreeNode<T>* node)
{
if (!node)
{
return "X";
}
std::string left = "(" + serializationFromPreOrder(node->leftChild) + ")";
std::string right = "(" + serializationFromPreOrder(node->rightChild) + ")";
return std::to_string(node->Value) + left + right;
}
template<typename T>
std::string serializationFromInOrder(TreeNode<T>* node)
{
if (!node)
{
return "X";
}
std::string left = "(" + serializationFromInOrder(node->leftChild) + ")";
std::string right = "(" + serializationFromInOrder(node->rightChild) + ")";
return left + std::to_string(node->Value) + right;
}
template<typename T>
std::string serializationFromPostOrder(TreeNode<T>* node)
{
if (!node)
{
return "X";
}
std::string left = "(" + serializationFromPostOrder(node->leftChild) + ")";
std::string right = "(" + serializationFromPostOrder(node->rightChild) + ")";
return left + right + std::to_string(node->Value);
}
template<typename T>
std::string BinaryTree<T>::serializeFromPreOrder() const
{
std::cout << "Serialize from pre order as belows:\n";
return serializationFromPreOrder(this->root);
}
template<typename T>
std::string BinaryTree<T>::serializeFromInOrder() const
{
std::cout << "Serialize from in order as belows:\n";
return serializationFromInOrder(this->root);
}
template<typename T>
std::string BinaryTree<T>::serializeFromPostOrder() const
{
std::cout << "Serialize from post order as belows:\n";
return serializationFromPostOrder(this->root);
}
template<typename T1, typename T2>
int parseInt(const T1& data, T2& ptr)
{
int x = 0;
int sign = 1;
if (!isdigit(data[ptr]))
{
sign = -1;
++ptr;
}
while (isdigit(data[ptr]))
{
x = x * 10 + data[ptr++] - '0';
}
return x * sign;
}
template<typename T1, typename T2>
TreeNode<T2>* parseSubTreeFromPreOrder(const T1& data, T2& ptr)
{
++ptr;
TreeNode<T2>* subTree = parseFromPreOrder(data, ptr);
++ptr;
return subTree;
}
template<typename T1, typename T2>
TreeNode<T2>* parseFromPreOrder(const T1& data, T2& ptr)
{
if (data[ptr] == 'X')
{
ptr++;
return nullptr;
}
TreeNode<T2>* cur = new TreeNode<T2>{
0 };
cur->Value = parseInt(data, ptr);
cur->leftChild = parseSubTreeFromPreOrder(data, ptr);
cur->rightChild = parseSubTreeFromPreOrder(data, ptr);
return cur;
}
template<typename T>
BinaryTree<T>& BinaryTree<T>::deserializeFromPreOrder(std::string data)
{
int ptr = 0;
this->root = parseFromPreOrder(data, ptr);
return *this;
}
template<typename T1, typename T2>
TreeNode<T2>* parseSubTreeFromInOrder(const T1& data, T2& ptr)
{
++ptr;
TreeNode<T2>* subTree = parseFromInOrder(data, ptr);
++ptr;
return subTree;
}
template<typename T1, typename T2>
TreeNode<T2>* parseFromInOrder(const T1& data, T2& ptr)
{
if (data[ptr] == 'X')
{
ptr++;
return nullptr;
}
TreeNode<T2>* cur = new TreeNode<T2>{
0 };
cur->leftChild = parseSubTreeFromInOrder(data, ptr);
cur->Value = parseInt(data, ptr);
cur->rightChild = parseSubTreeFromInOrder(data, ptr);
return cur;
}
template<typename T>
BinaryTree<T>& BinaryTree<T>::deserializeFromInOrder(std::string data)
{
int ptr = 0;
this->root = parseFromInOrder(data, ptr);
return *this;
}
template<typename T1, typename T2>
TreeNode<T2>* parseSubTreeFromPostOrder(const T1& data, T2& ptr)
{
++ptr;
TreeNode<T2>* subTree = parseFromPostOrder(data, ptr);
++ptr;
return subTree;
}
template<typename T1, typename T2>
TreeNode<T2>* parseFromPostOrder(const T1& data, T2& ptr)
{
if (data[ptr] == 'X')
{
ptr++;
return nullptr;
}
TreeNode<T2>* cur = new TreeNode<T2>{
0 };
cur->leftChild = parseSubTreeFromPostOrder(data, ptr);
cur->rightChild = parseSubTreeFromPostOrder(data, ptr);
cur->Value = parseInt(data, ptr);
return cur;
}
template<typename T>
BinaryTree<T>& BinaryTree<T>::deserializeFromPostOrder(std::string data)
{
int ptr = 0;
this->root = parseFromPostOrder(data, ptr);
return *this;
}
template<typename T>
BinaryTree<T>::~BinaryTree()
{
if (this->root == nullptr)
{
std::cout << "This binary tree is empty!!! No need to delete!!!\n";
return;
}
TreeNode<T>* temp = nullptr;
std::queue<TreeNode<T>*> helper;
helper.push(this->root);
while (!helper.empty())
{
temp = helper.front();
helper.pop();
if (temp->leftChild)
helper.push(temp->leftChild);
if (temp->rightChild)
helper.push(temp->rightChild);
delete temp;
temp = nullptr;
}
}
int BinaryTreeTest()
{
BinaryTree<int> tree;
std::vector<int> preOrder;
std::vector<int> inOrder;
std::vector<int> postOrder;
for (int i = 65; i < 91; i++)
{
tree.insert(i);
}
tree.preOrderTraversal(preOrder);
tree.inOrderTraversal(inOrder);
tree.postOrderTraversal(postOrder);
BinaryTree<int> TreeSerializeFromPreOrder;
std::string dataFromPreOrder;
TreeSerializeFromPreOrder.buildTreeFromPreAndInOrder(preOrder, inOrder);
std::cout << (dataFromPreOrder = TreeSerializeFromPreOrder.serializeFromPreOrder()) << '\n';
BinaryTree<int> TreeDeserializeFromPreOrder;
TreeDeserializeFromPreOrder.deserializeFromPreOrder(dataFromPreOrder);
TreeDeserializeFromPreOrder.hierarchicalTraversal();
BinaryTree<int> TreeSerializeFromInOrder;
std::string dataFromInOrder;
TreeSerializeFromInOrder.buildTreeFromPreAndInOrder(preOrder, inOrder);
std::cout << (dataFromInOrder = TreeSerializeFromInOrder.serializeFromInOrder()) << '\n';
BinaryTree<int> TreeDeserializeFromInOrder;
TreeDeserializeFromInOrder.deserializeFromInOrder(dataFromInOrder);
TreeDeserializeFromInOrder.hierarchicalTraversal();
BinaryTree<int> TreeSerializeFromPostOrder;
std::string dataFromPostOrder;
TreeSerializeFromPostOrder.buildTreeFromPreAndInOrder(preOrder, inOrder);
std::cout << (dataFromPostOrder = TreeSerializeFromPostOrder.serializeFromPostOrder()) << '\n';
BinaryTree<int> TreeDeserializeFromPostOrder;
TreeDeserializeFromPostOrder.deserializeFromPostOrder(dataFromPostOrder);
TreeDeserializeFromPostOrder.hierarchicalTraversal();
return 0;
}
#include "header.h"
int main()
{
BinaryTreeTest();
return 0;
}
测试结果：
参考：
The C++ Programming Language 3rd Edition, Bjarne.Stroustrup
C++ How to Program 9th Edition, Paul Deitel
Starting Out with C++ Early Objects Seventh Edition, Tony Gaddis, Judy Walters, Godfrey Muganda
C++ Templates The Complete Guide SECOND EDITION, David Vandevoorde, Nicolai M. Josuttis, Douglas Gregor
102. 二叉树的层序遍历
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
LCR 156. 序列化与反序列化二叉树
