代码拉取完成,页面将自动刷新
#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;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。