1 Star 0 Fork 0

郑玉强/dataStructure

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
binary_tree.hpp 17.77 KB
一键复制 编辑 原始数据 按行查看 历史
郑玉强 提交于 2024-10-06 16:23 +08:00 . 临时提交
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615
#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");
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/zheng-yuqiang_lyg_cn/data-structure.git
git@gitee.com:zheng-yuqiang_lyg_cn/data-structure.git
zheng-yuqiang_lyg_cn
data-structure
dataStructure
dev01

搜索帮助