1 Star 0 Fork 0

郑玉强/dataStructure

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
preorder_threaded_binary_tree.hpp 4.11 KB
一键复制 编辑 原始数据 按行查看 历史
#pragma once
#include <iostream>
#include "threaded_node.hpp"
using namespace std;
template <class TData>
class PreOrderThreadedBinaryTree
{
private:
ThreadedNode<TData>* root_;
/// <summary>
/// 子树创建前序线索
/// </summary>
/// <param name="node">当前结点</param>
/// <param name="pre_node">前序遍历下该节点的前一个结点</param>
void createThreadInSubTreeRecursive_(ThreadedNode<TData>*& node,ThreadedNode<TData>*& pre_node);
public:
PreOrderThreadedBinaryTree() :root_(NULL) {}
// 创建前序线索
void createThreadRecursive();
/// <summary>
/// 查找某个节点的父节点
/// </summary>
/// <param name="node">查找这个结点的父节点</param>
/// <returns></returns>
ThreadedNode<TData>* parent(ThreadedNode<TData>* node);
// 前序线索二叉树的下一个节点
ThreadedNode<TData>* next(ThreadedNode<TData>* node);
//前序线索二叉树的前一个结点
ThreadedNode<TData>* pre(ThreadedNode<TData>* node);
//前序线索二叉树的最后一个结点
ThreadedNode<TData>* last(ThreadedNode<TData>* subtree_root);
};
template<class TData>
inline void PreOrderThreadedBinaryTree<TData>::createThreadInSubTreeRecursive_(ThreadedNode<TData>*& node, ThreadedNode<TData>*& pre_node)
{
// 结点为空,返回
if (!node)
return;
if (!node->left_child)
{
node->left_child = pre_node;
node->left_tag = THREADED_NODE_POINTER;
}
if (pre_node != NULL && pre_node->right_child == NULL)
{
pre_node->right_child = node;
pre_node->right_tag = THREADED_NODE_POINTER;
}
pre_node = node;
// 左子树分治
if (node->left_tag == CHILD_POINTER)
this->createThreadInSubTreeRecursive_(node->left_child,pre_node);
// 右子树分治
this->createThreadInSubTreeRecursive_(node->right_child,pre_node);
}
template<class TData>
inline void PreOrderThreadedBinaryTree<TData>::createThreadRecursive()
{
ThreadedNode<TData>* pre_node = NULL;
// 不为空树时
if (this->root_)
{
this->createThreadInSubTreeRecursive_(this->root_,pre_node);
pre_node->right_child = NULL;
pre_node->right_tag = THREADED_NODE_POINTER;
}
}
template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<TData>::parent(ThreadedNode<TData>* node)
{
// 如果树为空或者要查找的节点是根节点,则返回 NULL
if (root == NULL || node == root) {
return NULL;
}
ThreadedNode<TData>* current = root; // 从根节点开始
ThreadedNode<TData>* parent_node = NULL; // 用来记录父节点
// 遍历树,寻找目标节点 node
while (current != NULL)
{
if (current == node) {
// 找到了目标节点,返回其父节点
return parent_node;
}
// 如果左子节点存在并且不是线索
if (current->left_tag == CHILD_POINTER && current->left_child != NULL)
{
// 如果左子节点是目标节点,当前节点就是父节点
if (current->left_child == node) {
return current;
}
// 向左子树移动
parent_node = current;
current = current->left_child;
}
// 如果右子节点存在并且不是线索
else if (current->right_tag == CHILD_POINTER && current->right_child != NULL)
{
// 如果右子节点是目标节点,当前节点就是父节点
if (current->right_child == node) {
return current;
}
// 向右子树移动
parent_node = current;
current = current->right_child;
}
else {
// 如果没有孩子节点或孩子节点是线索,遍历结束
break;
}
}
// 如果遍历结束还没找到,返回 NULL
return NULL;
}
template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<TData>::next(ThreadedNode<TData>* node)
{
if (node->left_tag != THREADED_NODE_POINTER)
return node->left_child;
return node->right_child;
}
template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<TData>::pre(ThreadedNode<TData>* node)
{
if (node->left_tag == THREADED_NODE_POINTER)
return node->left_child;
ThreadedNode<TData>* parent = this->parent(node);
if (!parent)
return NULL;
if (parent->left_tag == 1 || parent->left_child == node)
return parent;
return this->last(parent->left_child);
}
template<class TData>
inline ThreadedNode<TData>* PreOrderThreadedBinaryTree<TData>::last(ThreadedNode<TData>* subtree_root)
{
if (!subtree_root)
throw invalid_argument("NULL pointer");
ThreadedNode<TData>* cur = subtree_root;
while (cur->right_child != NULL && cur->right_tag == CHILD_POINTER)
{
cur = cur->right_child;
}
return cur;
}
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

搜索帮助