代码拉取完成,页面将自动刷新
#pragma once
#include <iostream>
#include <cstdlib>
#include <stack>
#include <queue>
using namespace std;
namespace binary_tree
{
// 二叉树结点模板结构体
template <class TData>
struct BinaryTreeNode
{
TData data;
BinaryTreeNode<TData>* left_child;
BinaryTreeNode<TData>* right_child;
BinaryTreeNode()
:left_child(NULL),right_child(NULL){}
explicit BinaryTreeNode(TData data, BinaryTreeNode<TData>* left_child = NULL, BinaryTreeNode<TData>* right = NULL)
:data(data), left_child(left_child), right_child(right_child) {}
};
// (后序遍历)回溯栈结点模板结构体
template <class TData>
struct PostOrderBacktrackStackNode
{
BinaryTreeNode<TData>* node;
// 0:左孩子回溯,1:右孩子回溯
enum {LEFT_BACK_TRACKING = 0, RIGHT_BACK_TRACKING} tag;
explicit PostOrderBacktrackStackNode(BinaryTreeNode<TData>* node = NULL)
:node(node), tag(LEFT_BACK_TRACKING) {}
};
}
template <class TData>
class BinaryTree
{
// 重载==,判断两棵树是否相同
friend bool operator== <>(const BinaryTree<TData>& binary_tree_1, const BinaryTree<TData>& binary_tree_2);
// 重载<<,输出二叉树
friend ostream& operator<< <>(ostream& out, BinaryTree<TData>& binary_tree);
public:
// 判断两棵二叉树是否相同(递归)------ static修饰的变量或者方法受权限修饰符约束吗?会受权限修饰符限制
static bool equal(binary_tree::BinaryTreeNode<TData>* root1, binary_tree::BinaryTreeNode<TData>* root2);
protected:
binary_tree::BinaryTreeNode<TData>* root_; // 树根结点
// 子树插入结点(递归)
bool insertInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root, const TData& data);
// 子树删除(递归)
void deleteSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root);
// 子树是否存在数据(递归)
bool existInSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, TData data) const;
// 复制(递归)
bool duplicateSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* src_subtree_root, binary_tree::BinaryTreeNode<TData>*& target_subtree_root);
// 求子树的高度(递归)
int heightOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_node) const;
// 求子树的节点个数(递归)
int sizeOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root) const;
// 子树获取节点的父节点
binary_tree::BinaryTreeNode<TData>* getParentInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, binary_tree::BinaryTreeNode<TData>* node) const;
// 子树前序遍历(递归)
void preOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
// 子树前序遍历
void preOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
// 子树中序遍历(递归)
void inOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
// 子树中序遍历
void inOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
// 子树后序遍历(递归)
void postOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
// 子树后序遍历
void postOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
// 子树层序遍历
void levelOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void (*visit)(binary_tree::BinaryTreeNode<TData>*));
// 子树打印
void printSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root);
// 使用前序遍历和中序遍历结果,创建子树(递归)
bool createSubTreeByPreOrderAndInOrderList_(const TData* preorder_sub_list,
const TData* inorder_sub_list,
int length,
binary_tree::BinaryTreeNode<TData>*& subtree_root);
public:
BinaryTree() :root_(NULL) {}
explicit BinaryTree(const TData& data) { this->insertInSubTreeRecursive_(this->root_, data); }
// 拷贝构造函数
BinaryTree(const BinaryTree<TData>& src_binary_tree);
~BinaryTree() { this->deleteSubTreeRecursive_(this->root_); }
// 获取根节点
binary_tree::BinaryTreeNode<TData>* root() const { return this->root_; }
// 判断是否为空树
bool isEmpty() { return this->root_ == NULL; }
// 获取父节点
binary_tree::BinaryTreeNode<TData>* parent(binary_tree::BinaryTreeNode<TData>* node) const
{
// == NULL 代表空树, == node代表是根节点,无父节点
return (this->root_ == NULL || this->root_ == node) ? NULL : this->getParentInSubTreeRecursive_(this->root_, node);
}
// 获取高度
int height() { return this->heightOfSubTreeRecursive_(this->root_); }
// 获取节点数
int size() { return this->sizeOfSubTreeRecursive_(this->root_); }
// 插入节点(递归)
bool insertRecursive(const TData& data) { return this->insertInSubTreeRecursive_(this->root_, data); }
// 是否存在数据
bool exist(TData data) { return this->existInSubTree_(this->root_, data); }
// 前序遍历(递归)
void preOrderTraversalRecursive(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
{
this->preOrderTraversalOfSubTreeRecursive_(this->root_, visit);
}
// 前序遍历
void preOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
{
this->preOrderTraversalOfSubTree_(this->root_, visit);
}
// 中序遍历(递归)
void inOrderTraversalRecursive(void (*visit)(binary_tree::BinaryTreeNode<TData>* node))
{
this->inOrderTraversalOfSubTreeRecursive_(this->root_, visit);
}
// 中序遍历
void inOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>* node))
{
this->inOrderTraversalOfSubTree_(this->root_, visit);
}
// 后序遍历(递归)
void postOrderTraversalRecursive(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
{
this->postOrderTraversalOfSubTreeRecursive_(this->root_,visit);
}
// 后序遍历
void postOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
{
this->postOrderTraversalOfSubTree_(this->root_,visit);
}
// 层序遍历
void levelOrderTraversal(void (*visit)(binary_tree::BinaryTreeNode<TData>*))
{
this->levelOrderTraversalOfSubTree_(this->root_, visit);
}
bool createByPreOrderAndInOrderList(const TData* preorder_list, const TData* inorder_list, int length)
{
bool res = this->createSubTreeByPreOrderAndInOrderList_(preorder_list,inorder_list,length,this->root_);
return res;
}
void print() { this->printSubTreeRecursive_(this->root_); }
};
template <typename TData>
bool operator==(const BinaryTree<TData>& binary_tree_1, const BinaryTree<TData>& binary_tree_2)
{
return BinaryTree<TData>::equal(binary_tree_1.root_,binary_tree_2.root_);
}
template <typename TData>
inline ostream& operator<< <>(ostream& out, BinaryTree<TData>& binary_tree)
{
binary_tree.print();
return out;
}
template<class TData>
inline bool BinaryTree<TData>::equal(binary_tree::BinaryTreeNode<TData>* root1, binary_tree::BinaryTreeNode<TData>* root2)
{
// 两个空树进行比较
if (root1 == NULL && root2 == NULL)
return true;
// 递归处理左右子树
if (root1 != NULL && root2 != NULL && root1->data == root2->data
&& BinaryTree<TData>::equal(root1->left_child, root2->left_child) // 处理左子树
&& BinaryTree<TData>::equal(root1->right_child, root2->right_child)) // 处理右子树
return true;
return false;
}
template<class TData>
inline bool BinaryTree<TData>::insertInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root, const TData& data)
{
// 空子树处理,生成树根即可
if (!subtree_root)
{
subtree_root = new binary_tree::BinaryTreeNode<TData>(data);
if (!subtree_root)
throw bad_alloc();
return true;
}
// 分治递归
int left_subtree_height = this->heightOfSubTreeRecursive_(subtree_root->left_child);
int right_subtree_height = this->heightOfSubTreeRecursive_(subtree_root->right_child);
// 为了平衡左右子树高度
if (left_subtree_height > right_subtree_height)
{
bool res = this->insertInSubTreeRecursive_(subtree_root->right_child,data);
if (!res)
return false;
}
else
{
bool res = this->insertInSubTreeRecursive_(subtree_root->left_child,data);
if (!res)
return false;
}
// 退出
return true;
}
template<class TData>
inline void BinaryTree<TData>::deleteSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>*& subtree_root)
{
// 空子树就什么都不用处理
if (!subtree_root)
return;
// 分治递归
this->deleteSubTreeRecursive_(subtree_root->left_child);
this->deleteSubTreeRecursive_(subtree_root->right_child);
delete subtree_root;
// 防止出现悬空指针
subtree_root = NULL;
}
template<class TData>
inline bool BinaryTree<TData>::existInSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, TData data) const
{
// 空树返回false
if (!subtree_root)
return false;
// 存在条件处理
if (subtree_root->data == data)
return true;
// 分治递归
// 左子树递归
bool existed = this->existInSubTree_(subtree_root->left_child,data);
if (existed)
return true;
// 右子树递归
existed = this->existInSubTree_(subtree_root->right_child,data);
if (existed)
return true;
// 退出函数
return false;
}
template<class TData>
inline bool BinaryTree<TData>::duplicateSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* src_subtree_root, binary_tree::BinaryTreeNode<TData>*& target_subtree_root)
{
// 源树为空
if (!src_subtree_root)
{
target_subtree_root = NULL;
return true;
}
// 目标子树根节点处理
target_subtree_root = new binary_tree::BinaryTreeNode<TData>(src_subtree_root->data);
if (!target_subtree_root)
throw bad_alloc();
// 分治递归
// 左子树递归
bool res = this->duplicateSubTreeRecursive_(src_subtree_root->left_child,
target_subtree_root->left_child);
if (!res)
return false;
// 右子树递归
res = this->duplicateSubTreeRecursive_(src_subtree_root->right_child,
target_subtree_root->right_child);
if (!res)
return false;
return true;
}
template<class TData>
inline int BinaryTree<TData>::heightOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_node) const
{
// 空子树高度为0
if (!subtree_node)
return 0;
// 分治递归
// 左子树递归
int left_subtree_height = this->heightOfSubTreeRecursive_(subtree_node->left_child);
// 右子树递归
int right_subtree_height = this->heightOfSubTreeRecursive_(subtree_node->right_child);
// 计算subtree_height,等于1 + 最高子树的高度
int subtree_height = (left_subtree_height > right_subtree_height ? left_subtree_height : right_subtree_height) + 1;
// 返回结果
return subtree_height;
}
template<class TData>
inline int BinaryTree<TData>::sizeOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root) const
{
// 空子树节点个数为0
if (!subtree_root)
return 0;
// 分治递归
// 左子树递归
int left_subtree_size = this->sizeOfSubTreeRecursive_(subtree_root->left_child);
// 右子树递归
int right_subtree_size = this->sizeOfSubTreeRecursive_(subtree_root->right_child);
int subtree_size = left_subtree_size + right_subtree_size + 1;
// 返回结果
return subtree_size;
}
template<class TData>
inline binary_tree::BinaryTreeNode<TData>* BinaryTree<TData>::getParentInSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, binary_tree::BinaryTreeNode<TData>* node) const
{
// 空子树父节点也为NULL
if (!subtree_root)
return NULL;
// 找到父节点情况处理
if (subtree_root->left_child == node || subtree_root->right_child == node)
return subtree_root;
// 分治递归
binary_tree::BinaryTreeNode<TData>* parent = this->getParentInSubTreeRecursive_(subtree_root->left_child,node);
if (!parent) // 左子树没找到对应节点的父节点
parent = this->getParentInSubTreeRecursive_(subtree_root->right_child, node);
return parent;
}
template<class TData>
inline void BinaryTree<TData>::preOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
// 空子树(节点)不需要遍历
if (!subtree_root)
return;
// 分治递归
visit(subtree_root);
this->preOrderTraversalOfSubTreeRecursive_(subtree_root->left_child,visit);
this->preOrderTraversalOfSubTreeRecursive_(subtree_root->right_child,visit);
}
template<class TData>
inline void BinaryTree<TData>::preOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
// 回溯栈
stack<binary_tree::BinaryTreeNode<TData>*> backtrack_stack;
backtrack_stack.push(subtree_root);
while (!backtrack_stack.empty())
{
binary_tree::BinaryTreeNode<TData>* cur = backtrack_stack.top();
backtrack_stack.pop();
visit(cur);
if (cur->right_child)
backtrack_stack.push(cur->right_child);
if (cur->left_child)
backtrack_stack.push(cur->left_child);
}
}
template<class TData>
inline void BinaryTree<TData>::inOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
// 空子树(节点)不需要递归
if (!subtree_root)
return;
this->inOrderTraversalOfSubTreeRecursive_(subtree_root->left_child,visit);
visit(subtree_root);
this->inOrderTraversalOfSubTreeRecursive_(subtree_root->right_child,visit);
}
template<class TData>
inline void BinaryTree<TData>::inOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
stack<binary_tree::BinaryTreeNode<TData>*> backtrack_stack;
binary_tree::BinaryTreeNode<TData>* cur = subtree_root;
while (cur || !backtrack_stack.empty())
{
// 一直向左子树方向搜索,等于在做深度优先搜索DFS
// 每次visit完一个节点,都要去找其左子树的各节点
while (cur)
{
backtrack_stack.push(cur);
cur = cur->left_child;
}
if (!backtrack_stack.empty())
{
cur = backtrack_stack.top();
backtrack_stack.pop();
visit(cur);
cur = cur->right_child;
}
}
}
template<class TData>
inline void BinaryTree<TData>::postOrderTraversalOfSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
// 空子树不需要后序遍历
if (!subtree_root)
return;
// 分治递归
this->postOrderTraversalOfSubTreeRecursive_(subtree_root->left_child,visit);
this->postOrderTraversalOfSubTreeRecursive_(subtree_root->right_child,visit);
visit(subtree_root);
}
template<class TData>
inline void BinaryTree<TData>::postOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
stack<binary_tree::PostOrderBacktrackStackNode<TData>> backtarck_stack;
binary_tree::BinaryTreeNode<TData>* cur_tree_node = subtree_root;
do
{
// 一直向左子树方向搜索,等于在做深度优先搜索dfs
while (cur_tree_node != NULL)
{
binary_tree::PostOrderBacktrackStackNode<TData> stack_node(cur_tree_node);
backtarck_stack.push(stack_node);
cur_tree_node = cur_tree_node->left_child;
}
bool cur_tree_node_left_backtrack_unfinished = true;
while (cur_tree_node_left_backtrack_unfinished && !backtarck_stack.empty())
{
binary_tree::PostOrderBacktrackStackNode<TData> cur_backtrack_node = backtarck_stack.top();
backtarck_stack.pop();
cur_tree_node = cur_backtrack_node.node;
if (cur_backtrack_node.tag == binary_tree::PostOrderBacktrackStackNode<TData>::LEFT_BACK_TRACKING)
{
cur_backtrack_node.tag = binary_tree::PostOrderBacktrackStackNode<TData>::RIGHT_BACK_TRACKING;
backtarck_stack.push(cur_backtrack_node);
cur_tree_node = cur_tree_node->right_child;
cur_tree_node_left_backtrack_unfinished = false;
}
else
{
visit(cur_tree_node);
}
}
} while (!backtarck_stack.empty());
}
template<class TData>
inline void BinaryTree<TData>::levelOrderTraversalOfSubTree_(binary_tree::BinaryTreeNode<TData>* subtree_root, void(*visit)(binary_tree::BinaryTreeNode<TData>*))
{
// 初始化遍历队列
queue<binary_tree::BinaryTreeNode<TData>*> traversal_queue;
traversal_queue.push(subtree_root);
// 遍历
while (!traversal_queue.empty())
{
binary_tree::BinaryTreeNode<TData>* cur = traversal_queue.front();
traversal_queue.pop();
visit(cur);
if (cur->left_child)
traversal_queue.push(cur->left_child);
if (cur->right_child)
traversal_queue.push(cur->right_child);
}
}
template<class TData>
inline void BinaryTree<TData>::printSubTreeRecursive_(binary_tree::BinaryTreeNode<TData>* subtree_root)
{
// 空子树处理
if (!subtree_root)
return;
// 打印子树根节点
cout << subtree_root->data;
// 递归处理左右子树
if (subtree_root->left_child != NULL || subtree_root->right_child != NULL)
{
cout << '(';
this->printSubTreeRecursive_(subtree_root->left_child);
cout << ',';
this->printSubTreeRecursive_(subtree_root->right_child);
cout << ')';
}
}
template<class TData>
inline bool BinaryTree<TData>::createSubTreeByPreOrderAndInOrderList_(const TData* preorder_sub_list,const TData* inorder_sub_list, int length, binary_tree::BinaryTreeNode<TData>*& subtree_root)
{
// 空子序列处理,就是一棵空树
if (length == 0)
return true;
// 中序序列找到轴(根节点),并生成子树根节点
int inorder_sub_list_pivot = 0;
// 取出前序遍历序列首元素,即根结点
TData cur_subtree_root_data = *preorder_sub_list;
while (cur_subtree_root_data != inorder_sub_list[inorder_sub_list_pivot])
{
inorder_sub_list_pivot++;
}
// 找到根结点后生成子根节点
subtree_root = new binary_tree::BinaryTreeNode<TData>(cur_subtree_root_data);
if (!subtree_root)
throw bad_alloc();
// 递归构造左子树和右子树
// 构造sub_tree的左子树
bool res = this->createSubTreeByPreOrderAndInOrderList_(preorder_sub_list + 1,
inorder_sub_list,
inorder_sub_list_pivot,
subtree_root->left_child);
if (!res) // 构造失败
return false;
// 构造sub_tree的右子树
res = this->createSubTreeByPreOrderAndInOrderList_(preorder_sub_list + inorder_sub_list_pivot + 1,
inorder_sub_list + inorder_sub_list_pivot + 1,
length - inorder_sub_list_pivot - 1,
subtree_root->right_child);
return res;
}
template<class TData>
inline BinaryTree<TData>::BinaryTree(const BinaryTree<TData>& src_binary_tree)
{
bool res = this->duplicateSubTreeRecursive_(src_binary_tree.root(),this->root_);
if (!res)
throw logic_error("DuplicateSubTreeRecursive_ error");
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。