413 lines
13 KiB
C++
413 lines
13 KiB
C++
#ifndef BINARYTREE_H
|
|
#define BINARYTREE_H
|
|
|
|
#include "DynamicArray.h"
|
|
#include "LinkedQueue.h"
|
|
#include "SharedPointer.h"
|
|
#include "Tree.h"
|
|
|
|
namespace Kylin {
|
|
|
|
template <typename T>
|
|
class BinaryTreeNode : public TreeNode<T> {
|
|
public:
|
|
BinaryTreeNode(const T &value, BinaryTreeNode *parent = nullptr) : TreeNode<T>(value, parent) {}
|
|
|
|
BinaryTreeNode *left = nullptr;
|
|
BinaryTreeNode *right = nullptr;
|
|
};
|
|
|
|
template <typename T>
|
|
class BinaryTree : public Tree<T> {
|
|
public:
|
|
enum Pos { //子树节点位置
|
|
Any,
|
|
Left,
|
|
Right
|
|
};
|
|
|
|
enum Traversal { //遍历顺序
|
|
Preorder, //先序遍历
|
|
Inorder, //中序遍历
|
|
Postorder, //后续遍历
|
|
Levelorder //层次遍历
|
|
};
|
|
|
|
class Iterator {
|
|
public:
|
|
Iterator(BinaryTreeNode<T> *pos) : m_pos(pos) {}
|
|
bool operator!=(const Iterator &other) { return (m_pos != other.m_pos); }
|
|
T &operator*() { return m_pos->value; }
|
|
Iterator &operator++() {
|
|
if (m_pos->left != nullptr) m_queue.enqueue(m_pos->left);
|
|
if (m_pos->right != nullptr) m_queue.enqueue(m_pos->right);
|
|
m_pos = m_queue.empty() ? nullptr : m_queue.dequeue();
|
|
return *this;
|
|
}
|
|
|
|
private:
|
|
BinaryTreeNode<T> *m_pos = nullptr;
|
|
LinkedQueue<BinaryTreeNode<T> *> m_queue;
|
|
};
|
|
|
|
BinaryTree() = default;
|
|
|
|
BinaryTree(const BinaryTree &other) { this->m_root = clone(dynamic_cast<BinaryTreeNode<T> *>(other.m_root)); }
|
|
|
|
BinaryTree(BinaryTree &&other) {
|
|
this->m_root = other.m_root;
|
|
other.m_root = nullptr;
|
|
}
|
|
|
|
~BinaryTree() { clear(); }
|
|
|
|
virtual BinaryTreeNode<T> *root() const { return dynamic_cast<BinaryTreeNode<T> *>(this->m_root); }
|
|
|
|
int degree() const { return degree(dynamic_cast<BinaryTreeNode<T> *>(this->m_root)); }
|
|
|
|
int height() const { return height(dynamic_cast<BinaryTreeNode<T> *>(this->m_root)); }
|
|
|
|
int count() const { return count(dynamic_cast<BinaryTreeNode<T> *>(this->m_root)); }
|
|
|
|
void clear() {
|
|
free(dynamic_cast<BinaryTreeNode<T> *>(this->m_root));
|
|
this->m_root = nullptr;
|
|
}
|
|
|
|
BinaryTree operator+(const BinaryTree &other) {
|
|
BinaryTree result;
|
|
result.m_root =
|
|
add(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), dynamic_cast<BinaryTreeNode<T> *>(other.m_root));
|
|
return result;
|
|
}
|
|
|
|
BinaryTree<T> &operator=(const BinaryTree &other) {
|
|
if (&other != this) {
|
|
clear();
|
|
this->m_root = clone(other.m_root);
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
bool operator==(const BinaryTree<T> &other) const {
|
|
return equal(dynamic_cast<const BinaryTreeNode<T> *>(this->m_root),
|
|
dynamic_cast<const BinaryTreeNode<T> *>(other.m_root));
|
|
}
|
|
|
|
bool operator!=(const BinaryTree<T> &other) const { return !(*this == other); }
|
|
|
|
DynamicArray<T> traversal(Traversal order) {
|
|
LinkedQueue<BinaryTreeNode<T> *> queue;
|
|
traversal(order, queue);
|
|
auto size = queue.size();
|
|
DynamicArray<T> result(size);
|
|
for (size_t i = 0; i < size; i++) {
|
|
result[i] = queue.dequeue()->value;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
bool insert(TreeNode<T> *node) override { return insert(node, Any); }
|
|
|
|
virtual bool insert(TreeNode<T> *node, Pos pos) {
|
|
if (node == nullptr) return false;
|
|
if (this->m_root == nullptr) {
|
|
this->m_root = node;
|
|
node->parent = nullptr;
|
|
return true;
|
|
}
|
|
auto status = find(node->parent);
|
|
if (!status) return false; //没有找到父节点
|
|
return insert(dynamic_cast<BinaryTreeNode<T> *>(node), dynamic_cast<BinaryTreeNode<T> *>(node->parent), pos);
|
|
}
|
|
|
|
bool insert(const T &value, TreeNode<T> *parent, Pos pos) {
|
|
bool ret = false;
|
|
auto n = new BinaryTreeNode<T>(value);
|
|
if (n == nullptr) THROW_EXCEPTION(NoEnoughMemoryException, "There is no enough memory to insert an element.");
|
|
n->parent = parent;
|
|
ret = insert(n, pos);
|
|
if (!ret) {
|
|
delete n;
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
virtual BinaryTreeNode<T> *find(const T &value) const {
|
|
return find(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), value);
|
|
}
|
|
|
|
bool find(TreeNode<T> *node) const {
|
|
return find(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), dynamic_cast<BinaryTreeNode<T> *>(node));
|
|
}
|
|
|
|
BinaryTree<T> remove(const T &value) {
|
|
auto node = find(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), value);
|
|
if (node == nullptr) return BinaryTree<T>();
|
|
auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
|
|
if (parent->left == node) {
|
|
parent->left = nullptr;
|
|
} else if (parent->right == node) {
|
|
parent->right = nullptr;
|
|
}
|
|
node->parent = nullptr;
|
|
BinaryTree<T> result;
|
|
result.m_root = node;
|
|
return result;
|
|
}
|
|
|
|
BinaryTree<T> remove(TreeNode<T> *node) {
|
|
auto status = find(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), dynamic_cast<BinaryTreeNode<T> *>(node));
|
|
if (!status) return BinaryTree();
|
|
auto parent = dynamic_cast<BinaryTreeNode<T> *>(node->parent);
|
|
if (parent->left == node) {
|
|
parent->left = nullptr;
|
|
} else if (parent->right == node) {
|
|
parent->right = nullptr;
|
|
}
|
|
node->parent = nullptr;
|
|
BinaryTree result;
|
|
result.m_root = node;
|
|
return result;
|
|
}
|
|
|
|
/**
|
|
* @brief 二叉树线索化，不可逆。
|
|
*/
|
|
BinaryTreeNode<T> *threaded(Traversal order) {
|
|
BinaryTreeNode<T> *ret = nullptr;
|
|
LinkedQueue<BinaryTreeNode<T> *> queue;
|
|
traversal(order, queue);
|
|
ret = connect(queue);
|
|
this->m_root = nullptr;
|
|
return ret;
|
|
}
|
|
|
|
Iterator begin() { return Iterator(dynamic_cast<BinaryTreeNode<T> *>(this->m_root)); }
|
|
Iterator end() { return Iterator(nullptr); }
|
|
|
|
protected:
|
|
BinaryTreeNode<T> *find(BinaryTreeNode<T> *node, const T &value) const {
|
|
BinaryTreeNode<T> *ret = nullptr;
|
|
if (node != nullptr) {
|
|
if (node->value == value) {
|
|
ret = node;
|
|
} else {
|
|
if (ret == nullptr) {
|
|
ret = find(node->left, value);
|
|
}
|
|
if (ret == nullptr) {
|
|
ret = find(node->right, value);
|
|
}
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
/**
|
|
* @brief 在以node为根结点的树中查找obj结点
|
|
*/
|
|
bool find(BinaryTreeNode<T> *node, BinaryTreeNode<T> *obj) const {
|
|
if ((node == nullptr) || (obj == nullptr)) return false;
|
|
if (node == obj) return true;
|
|
bool ret = find(node->left, obj);
|
|
if (!ret) ret = find(node->right, obj);
|
|
return ret;
|
|
}
|
|
|
|
/**
|
|
* @brief 将node插入到parent的pos节点
|
|
*/
|
|
bool insert(BinaryTreeNode<T> *node, BinaryTreeNode<T> *parent, Pos pos) {
|
|
bool ret = false;
|
|
if (pos == Any) {
|
|
if (parent->left == nullptr) {
|
|
parent->left = node;
|
|
ret = true;
|
|
} else if (parent->right == nullptr) {
|
|
parent->right = node;
|
|
ret = true;
|
|
}
|
|
} else if (pos == Left) {
|
|
if (parent->left == nullptr) {
|
|
parent->left = node;
|
|
ret = true;
|
|
}
|
|
} else if (pos == Right) {
|
|
if (parent->right == nullptr) {
|
|
parent->right = node;
|
|
ret = true;
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
void free(BinaryTreeNode<T> *node) {
|
|
if (node == nullptr) return;
|
|
if (node->left != nullptr) {
|
|
free(node->left);
|
|
}
|
|
if (node->right != nullptr) {
|
|
free(node->right);
|
|
}
|
|
delete node;
|
|
}
|
|
|
|
int count(BinaryTreeNode<T> *node) const {
|
|
if (node == nullptr) return 0;
|
|
int ret = 1;
|
|
ret += count(node->left);
|
|
ret += count(node->right);
|
|
return ret;
|
|
}
|
|
|
|
size_t height(BinaryTreeNode<T> *node) const {
|
|
if (node == nullptr) return 0;
|
|
size_t ret = 0;
|
|
ret = height(node->left);
|
|
auto rightHeight = height(node->right);
|
|
if (rightHeight > ret) ret = rightHeight;
|
|
return ret + 1;
|
|
}
|
|
|
|
int degree(BinaryTreeNode<T> *node) const {
|
|
if (node == nullptr) return 0;
|
|
int ret = 0;
|
|
|
|
ret = (!!node->left) + (!!node->right);
|
|
BinaryTreeNode<T> *nodes[] = {node->left, node->right};
|
|
for (int i = 0; (i < 2) && (ret < 2); i++) {
|
|
int d = degree(nodes[i]);
|
|
if (d > ret) {
|
|
d = ret;
|
|
}
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
BinaryTreeNode<T> *clone(BinaryTreeNode<T> *node) const {
|
|
if (node == nullptr) return nullptr;
|
|
auto ret = new BinaryTreeNode<T>(node->value);
|
|
ret->left = clone(node->left);
|
|
if (ret->left != nullptr) {
|
|
ret->left->parent = ret;
|
|
}
|
|
ret->right = clone(node->right);
|
|
if (ret->right != nullptr) {
|
|
ret->right->parent = ret;
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
bool equal(const BinaryTreeNode<T> *lh, const BinaryTreeNode<T> *rh) const {
|
|
|
|
bool ret = false;
|
|
if (lh == rh) {
|
|
ret = true;
|
|
} else if (lh != nullptr && rh != nullptr) {
|
|
ret = (lh->value == rh->value) && equal(lh->left, rh->left) && equal(lh->right, rh->right);
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
BinaryTreeNode<T> *add(BinaryTreeNode<T> *lh, BinaryTreeNode<T> *rh) const {
|
|
BinaryTreeNode<T> *ret = nullptr;
|
|
if ((lh != nullptr) && (rh == nullptr)) {
|
|
ret = clone(lh);
|
|
} else if ((lh == nullptr) && (rh != nullptr)) {
|
|
ret = clone(rh);
|
|
} else if ((lh != nullptr) && (rh != nullptr)) {
|
|
ret = new BinaryTreeNode<T>(lh->value + rh->value);
|
|
ret->left = add(lh->left, rh->left);
|
|
ret->right = add(lh->right, rh->right);
|
|
if (ret->left != nullptr) ret->left->parent = ret;
|
|
if (ret->right != nullptr) ret->right->parent = ret;
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
void traversal(Traversal order, LinkedQueue<BinaryTreeNode<T> *> &queue) {
|
|
switch (order) {
|
|
case Preorder:
|
|
preOrderTraversal(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), queue);
|
|
break;
|
|
case Inorder:
|
|
inOrderTraversal(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), queue);
|
|
break;
|
|
case Postorder:
|
|
postOrderTraversal(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), queue);
|
|
break;
|
|
case Levelorder:
|
|
levelOrderTraversal(dynamic_cast<BinaryTreeNode<T> *>(this->m_root), queue);
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief 先序遍历
|
|
*/
|
|
void preOrderTraversal(BinaryTreeNode<T> *node, LinkedQueue<BinaryTreeNode<T> *> &queue) {
|
|
if (node == nullptr) return;
|
|
queue.enqueue(node);
|
|
preOrderTraversal(node->left, queue);
|
|
preOrderTraversal(node->right, queue);
|
|
}
|
|
|
|
/**
|
|
* @brief 中序遍历
|
|
*/
|
|
void inOrderTraversal(BinaryTreeNode<T> *node, LinkedQueue<BinaryTreeNode<T> *> &queue) {
|
|
if (node == nullptr) return;
|
|
inOrderTraversal(node->left, queue);
|
|
queue.enqueue(node);
|
|
inOrderTraversal(node->right, queue);
|
|
}
|
|
|
|
void postOrderTraversal(BinaryTreeNode<T> *node, LinkedQueue<BinaryTreeNode<T> *> &queue) {
|
|
if (node == nullptr) return;
|
|
postOrderTraversal(node->left, queue);
|
|
postOrderTraversal(node->right, queue);
|
|
queue.enqueue(node);
|
|
}
|
|
|
|
/**
|
|
* @brief 层次遍历
|
|
*/
|
|
void levelOrderTraversal(BinaryTreeNode<T> *node, LinkedQueue<BinaryTreeNode<T> *> &queue) {
|
|
if (node == nullptr) return;
|
|
LinkedQueue<BinaryTreeNode<T> *> temp;
|
|
temp.enqueue(node);
|
|
while (temp.length() > 0) {
|
|
auto n = temp.dequeue();
|
|
if (n->left != nullptr) temp.enqueue(n->left);
|
|
if (n->right != nullptr) temp.enqueue(n->right);
|
|
queue.enqueue(n);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief 将queue的BinaryTreeNode连接成双向链表
|
|
*/
|
|
BinaryTreeNode<T> *connect(LinkedQueue<BinaryTreeNode<T> *> &queue) {
|
|
if (queue.empty()) return nullptr;
|
|
auto slider = queue.dequeue();
|
|
auto ret = slider;
|
|
slider->left = nullptr;
|
|
while (!queue.empty()) {
|
|
slider->right = queue.head();
|
|
queue.head()->left = slider;
|
|
slider = queue.dequeue();
|
|
}
|
|
slider->right = nullptr;
|
|
return ret;
|
|
}
|
|
};
|
|
|
|
} // namespace Kylin
|
|
#endif // BINARYTREE_H
|