Basic concepts:
A tree is a finite set of n (n > 0) nodes. When n =O, it is called an empty tree, which is a special case. In any non empty tree, it should meet the following requirements:
1) There is and only one specific node called root.
2) When n > 1, the other nodes can be divided into m (M > 0) disjoint finite sets T1, T2... Tm, in which each set itself is a tree and is called the subtree of the root node.
Properties:
Node level (depth) - count from top to bottom
Height of node - from bottom to top
Height (depth) of the tree - how many layers in total
Degree of node -- how many children (branches)
Degree of tree -- the maximum degree of each node
forest. Forest is a collection of M (m ≥ 0) disjoint trees
Binary tree
A binary tree is a finite set of n (n ≥ 0) nodes: 1 or an empty binary tree, that is, n = 0.
2 or consists of a root node and two disjoint left and right subtrees called roots. The left subtree and the right subtree are a binary tree respectively.
realization
Tree.h
#ifndef _TREE_H_
#define _TREE_H_
#define Maxszie 100
//Sequential storage
template<class T>
class STreeNode
{
public:
STreeNode()
{
isEmpty = 1;
}
~STreeNode()
{
isEmpty = 1;
}
T value;
bool isEmpty;
};
template<class T>
class STree : public STreeNode<T>
{
public:
void inTree(int n);
void PreOrder(const int now);
void InOrder(const int now);
void PosOrder(const int now);
void LevelOrder(const int now);
void Print();
private:
STreeNode<T> t[Maxszie];
int size;
};
// Chain type
template<class T>
class LTreeNode
{
public:
LTreeNode(const T &x, LTreeNode<T> *l = NULL, LTreeNode<T> *r = NULL) : value(x), lchild(l), rchild(r){};
public:
T &getValue() {return this->value};
LTreeNode<T> *getLeft() {return this->lchild};
LTreeNode<T> *getRight() {return this->rchild};
void setLeft(LTreeNode<T> *l) {this->lchild = l};
void setRight(LTreeNode<T> *r) {this->rchild = r};
void setValue(const T &x) {this->value = x};
private:
T value;
LTreeNode<T> *lchild, *rchild;
};
template<class T>
class LTree
{
public:
LTree(LTreeNode<T> *t) : root(t){};
~LTree() { del(root); };
public:
//Search the parent node of node p in the subtree with node t as the root node
LTreeNode<T> * getFather(LTreeNode<T> *t, LTreeNode<T> *p);
//Find the node whose data field is item in the subtree with node t as the root node
LTreeNode<T> * find(LTreeNode<T> *t, const T &item);
//Delete node t and its left and right subtrees from the tree (including some column update operations after deletion)
void delSubTree(LTreeNode<T> *t);
//Delete node t and its left and right subtrees
void del(LTreeNode<T> *t);
//First, traverse the root and output the subtree with node t as the root node
void preOrder(LTreeNode<T> *t);
//Traverse and output the subtree with node t as the root node
void InOrder(LTreeNode<T> *t);
//The latter root traverses and outputs the subtree with node t as the root node
void PostOrder(LTreeNode<T> *t);
//The hierarchy traverses and outputs the subtree with node t as the root node
void levelOrder(LTreeNode<T> *t);
//Create binary tree
void createBinTree(T stop);
//Create a binary tree and return the root node of the binary tree
LTreeNode<T> * create();
LTreeNode<T> * getRoot() { return root; }
void setRoot(LTreeNode<T> * t) { root = t; }
T getStop() { return stop; }
void setStop(const T& stop) { this->stop = stop; }
bool isEmpty() { return root == NULL ? true : false; }
private:
LTreeNode<T> *root;
T stop; // Enter stop to stop
};
#endif //_TREE_H_
Tree.cpp
#include "Tree.h"
#include <iostream>
#include <queue>
template<class T>
void STree<T>::inTree(int n)
{
if(n >= Maxszie)
{
std::cout << "can't in\n";
return ;
}
for(int i = 1; i <= n; ++ i)
{
std::cin >> t[i].value;
t[i].isEmpty = 0;
}
size = n;
}
template<class T>
void STree<T>::Print()
{
for(int i = 1; i <= size; ++ i)
{
std::cout << t[i].value << " ";
}
std::cout << std::endl;
}
template<class T>
void STree<T>::PreOrder(const int now)
{
if(t[now].isEmpty == 0)
{
std::cout << t[now].value << " ";
PreOrder(now*2);
PreOrder(now*2+1);
}
}
template<class T>
void STree<T>::InOrder(const int now)
{
if(t[now].isEmpty == 0)
{
InOrder(now*2);
std::cout << t[now].value << " ";
InOrder(now*2+1);
}
}
template<class T>
void STree<T>::PosOrder(const int now)
{
if(t[now].isEmpty == 0)
{
PosOrder(now*2);
PosOrder(now*2+1);
std::cout << t[now].value << " ";
}
}
template<class T>
void STree<T>::LevelOrder(const int now)
{
std::queue<int> q;
q.push(now);
while(!q.empty())
{
int i = q.front();
q.pop();
int l = i*2;
int r = i*2+1;
if(t[l].isEmpty == 0)
{
q.push(l);
}
if(t[r].isEmpty == 0)
{
q.push(r);
}
std::cout << t[i].value << " ";
}
std::cout << std::endl;
}
/*
.::::.
.::::::::.
::::::::::: FUCK YOU
..:::::::::::'
'::::::::::::'
.::::::::::
'::::::::::::::..
..::::::::::::.
``::::::::::::::::
::::``:::::::::' .:::.
::::' ':::::' .::::::::.
.::::' :::: .:::::::'::::.
.:::' ::::: .:::::::::' ':::::.
.::' :::::.:::::::::' ':::::.
.::' ::::::::::::::' ``::::.
...::: ::::::::::::' ``::.
````':. ':::::::::' ::::..
'.:::::' ':'````..
*/
template<class T>
LTreeNode<T> *LTree<T>::getFather(LTreeNode<T> *t, LTreeNode<T> *p)
{
LTreeNode<T> *father;
if(t == NULL || p == NULL)
{
return NULL;
}
if(t->getLeft() == p || t->getRight() == p)
return t;
if((father = getFather(t->getLeft(), p)) != NULL)
return father;
else
return getFather(t->getRight(), p);
}
template<class T>
LTreeNode<T> *LTree<T>::find(LTreeNode<T> *t, const T &item)
{
LTreeNode<T> *target;
if(t == NULL)
return NULL;
if(t->getValue() == T)
return t;
if((target = find(t->getLeft(), item)) != NULL)
return target;
else
return find(t->getRight(), item);
}
template<class T>
void LTree<T>::delSubTree(LTreeNode<T> *t)
{
if(t == NULL)
return ;
if(t == root)
{
del(t);
root = NULL;
return ;
}
LTreeNode<T> *p = t, *q;
q = getFather(root, t);
if(q)
{
if(q->getLeft() == t)
q->setLeft(NULL);
if(q->getRight() == t)
q->setRight(NULL);
}
del(p);
}
template<class T>
void LTree<T>::del(LTreeNode<T> *t)
{
if(t != NULL)
{
del(t->getLeft());
del(t->getRight());
delete t;
}
}
template<class T>
void LTree<T>::preOrder(LTreeNode<T> *t)
{
if(t != NULL)
{
std::cout << t->getValue() << " ";
preOrder(t->getLeft());
preOrder(t->getRight());
}
}
template<class T>
void LTree<T>::InOrder(LTreeNode<T> *t)
{
if(t != NULL)
{
InOrder(t->getLeft());
std::cout << t->getValue() << " ";
InOrder(t->getRight());
}
}
template<class T>
void LTree<T>::PostOrder(LTreeNode<T> *t)
{
if(t != NULL)
{
PostOrder(t->getLeft());
PostOrder(t->getRight());
std::cout << t->getValue() << " ";
}
}
template<class T>
void LTree<T>::levelOrder(LTreeNode<T> *t)
{
if(t == NULL)
return ;
LTreeNode<T> *cur;
std::queue<LTreeNode<T>* > q;
q.push(t);
while(!q.empty())
{
cur = q.front();
q.pop();
std::cout << cur->getValue() << " ";
if(cur->getLeft() != NULL)
q.push(cur->getLeft());
if(cur->getRight() != NULL)
q.push(cur->getRight());
}
std::cout << std::endl;
}
template<class T>
void LTree<T>::createBinTree(T stop)
{
setStop(stop);
root = create();
}
template<class T>
LTreeNode<T> *LTree<T>::create()
{
LTreeNode<T> *t, *t1, *t2;
T item;
std::cin >> item;
if (item == stop) {
t = NULL;
return t;
}
else {
if (!(t = new LTreeNode<T>(item, NULL, NULL)))
return NULL;
t1=create();
t->setLeft(t1);
t2 = create();
t->setRight(t2);
return t;
}
}
Binary search tree BST(Binary Search Tree)
definition
- If the left subtree of any node is not empty, the values of all nodes on the left subtree are less than those of its root node;
- If the right subtree of any node is not empty, the values of all nodes on the right subtree are greater than those of its root node;
- The left and right subtrees of any node are also binary search trees.
- There are no nodes with equal key values.
realization
statement
//Binary search tree
template<class T>
class BSTNode
{
public:
BSTNode(const T &x) : data(x), lchild(NULL), rchild(NULL), parent(NULL){};
~BSTNode(){};
public:
void setData(const T &x) { this->data = x; };
void setLchild(BSTNode<T> *l) { this->lchild = l; };
void setRchild(BSTNode<T> *r) { this->rchild = r; };
void setParent(BSTNode<T> *p) { this->parent = p; };
BSTNode<T> *getLchild() { return this->lchild; };
BSTNode<T> *getRchild() { return this->rchild; };
BSTNode<T> *getParent() { return this->parent; };
T getData() { return this->data; };
private:
T data;
BSTNode<T> *lchild, *rchild, *parent;
};
template<class T>
class BST
{
public:
BST(const int &s) : root(NULL), size(s){};
~BST(){ del(root); std::cout << "Deconstruction" << std::endl; };
public:
void create_BST();
BSTNode<T> *getroot();
void InOrder(BSTNode<T> *t);
void Insert(BSTNode<T> *t);
void PreOrder(BSTNode<T> *t);
void PosOrder(BSTNode<T> *t);
void LevelOrder(BSTNode<T> *t);
void del(BSTNode<T> *t);
BSTNode<T> *search(const T &x);
T max();
T min();
void visit(BSTNode<T> *t);
private:
BSTNode<T> *root;
int size = 0;
};
realization
// BST
template<class T>
BSTNode<T> *BST<T>::getroot()
{
return this->root;
}
template<class T>
void BST<T>::visit(BSTNode<T> *t)
{
std::cout << t->getData() << " ";
}
template<class T>
void BST<T>::Insert(BSTNode<T> *t)
{
BSTNode<T> *q = root, *p = NULL;
while(q != NULL)
{
p = q;
if(t->getData() < q->getData())
q = q->getLchild();
else
q = q->getRchild();
}
t->setParent(p);
if(p == NULL)
root = t;
else if(t->getData() < p->getData())
p->setLchild(t);
else
p->setRchild(t);
}
template<class T>
void BST<T>::create_BST()
{
std::cout << "Input your data: ";
for(int i = 0; i < size; ++ i)
{
T d;
std::cin >> d;
BSTNode<T> *node = new BSTNode<T>(d);
Insert(node);
}
}
template<class T>
void BST<T>::PreOrder(BSTNode<T> *t)
{
if(t != NULL)
{
visit(t);
PreOrder(t->getLchild());
PreOrder(t->getRchild());
}
}
template<class T>
void BST<T>::InOrder(BSTNode<T> *t)
{
if(t != NULL)
{
InOrder(t->getLchild());
visit(t);
InOrder(t->getRchild());
}
}
template<class T>
void BST<T>::PosOrder(BSTNode<T> *t)
{
if(t != NULL)
{
PosOrder(t->getLchild());
PosOrder(t->getRchild());
visit(t);
}
}
template<class T>
void BST<T>::LevelOrder(BSTNode<T> *t)
{
std::queue<BSTNode<T> *> q;
q.push(t);
while(!q.empty())
{
BSTNode<T> *p = q.front();
visit(p);
if(p->getLchild() != NULL)
q.push(p->getLchild());
if(p->getRchild() != NULL)
q.push(p->getRchild());
q.pop();
}
}
template<class T>
BSTNode<T> *BST<T>::search(const T &x)
{
if(root == NULL)
return NULL;
BSTNode<T> *t = root;
while(t != NULL && (t->getData() != x))
{
if(x < t->getData())
{
t = t->getLchild();
}
else t = t->getRchild();
}
return t;
}
template<class T>
T BST<T>::max()
{
BSTNode<T> *t = root;
while(t->getRchild() != NULL)
{
t = t->getRchild();
}
return t->getData();
}
template<class T>
T BST<T>::min()
{
BSTNode<T> *t = root;
while(t->getLchild() != NULL)
{
t = t->getLchild();
}
return t->getData();
}
template<class T>
void BST<T>::del(BSTNode<T> *t)
{
if(t != NULL)
{
del(t->getLchild());
del(t->getRchild());
delete t;
}
}
Balanced binary tree AVL
Balanced binary tree (AVL tree for short) - the height difference between the left and right subtrees of any node of the tree shall not exceed 1.
Node balance factor = left subtree height - right subtree height.
The absolute value of balance factor of balanced binary tree shall not be greater than 1
Adjust minimum unbalanced subtree
- Insert the left subtree of the left son of a once
- Insert LR into the right subtree of the left son of a once
- Insert the left subtree of the right son of a once
- Insert the right subtree of the right son of a once
LL
1)LL balanced rotation (right single rotation). Because A new node is inserted into the left subtree (L) of the left child (L) of node A, the balance factor of A increases from 1 to 2, resulting in the loss of balance of the subtree with A as the root, requiring A right rotation operation. Rotate the left child B of A to the right to replace A as the root node, rotate node A to the right and down to become the root node of the right subtree of B, and the original right subtree of B is the left subtree of node A.
RR
2) RR balanced rotation (left single rotation). Due to the right subtree of the right child (R) at node a ® A new node is inserted on the, and the balance factor of a is reduced from - 1 to - 2, resulting in the imbalance of the subtree with a as the root, which requires a left rotation operation. Rotate the right child B of a to the left to replace a as the root node, rotate node a to the left and down to become the root node of the left subtree of B, and the original left subtree of B is the right subtree of node a
LR
3)LR balanced rotation (double rotation from left to right). Since a new node is inserted into the right subtree (R) of a's left child (L), the balance factor of a increases from 1 to 2, resulting in the loss of balance of the subtree with a as the root. Two rotation operations are required, first left rotation and then right rotation. First, rotate the root node c of the left child of node A and the right subtree of node B to the left, and then rotate the c node to the right to the position of node a
RL
4) RL balanced rotation (double rotation from right to left). Since a new node is inserted into the left subtree (L) of the right child (R) of a, the balance factor of a is reduced from - 1 to - 2, resulting in the loss of balance of the subtree with a as the root. Two rotation operations are required, first right rotation and then left rotation. First, rotate the root node c of the right child of node A and the left subtree of node B upward to the right to the position of node B, and then rotate the c node upward to the left to the position of node a
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-dfv0TgfT-1630811348339)(./images/1.jpg)]
[the external chain picture transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-wdu427xb-1630811341) (. / images / 2. JPG)]
AVL.h
//Binary balanced tree
template<class T>
class AVLNode
{
public:
AVLNode(const T &x) : data(x), lchild(NULL), rchild(NULL) {};
~AVLNode(){};
public:
void setData(const T &x) { this->data = x; };
void setLchild(AVLNode<T> *l) { this->lchild = l; };
void setRchild(AVLNode<T> *r) { this->rchild = r; };
AVLNode<T> *getLchild() { return this->lchild; };
AVLNode<T> *getRchild() { return this->rchild; };
T getData() { return this->data; };
private:
T data;
AVLNode<T> *lchild, *rchild;
};
template<class T>
class AVL
{
typedef AVLNode<T> AVLnode;
public:
AVL(){ avlroot = NULL; };
~AVL() { __deleteTree(avlroot); };
AVL(const T *arr, int len);
AVL(const std::vector<T> &);
AVLnode *getAvlroot() { return this->avlroot; };
void setAvlroot(AVLnode *avl) { this->avlroot = avl; };
public:
void InorderTraversal(); //Traversing external interfaces in middle order
void InorderTraversal(std::vector<T> &); //Medium order traversal external interface overload 2
bool Delete(const T &x); //Delete external interface of node
bool Insert(const T &x); //Insert the external interface of the node
bool IsEmpty(){ return avlroot == NULL; } //Tree empty?
bool search(const T &x); //Query external interface
private:
int __height(AVLnode *root);//Find the height of the tree
int __diff(AVLnode *root);//Height difference (balance factor)
//Single rotation
AVLnode *__ll_Rotation(AVLnode *root);//left-left rotation
AVLnode *__rr_Rotation(AVLnode *root);//right-right rotation
//Double rotation
AVLnode *__lr_Rotation(AVLnode *root);//left-right rotation
AVLnode *__rl_Rotation(AVLnode *root);//right-left rotation
AVLnode *__Balance(AVLnode *root);//Balance operation
AVLnode *__Insert(AVLnode *root);//Internal implementation of insert
//Two overloads of middle order traversal
void __InorderTraversal(AVLnode *root);//output
void __InorderTraversal(AVLnode *root, std::vector<T> &vec);//Result saving
bool __isLeaf(AVLnode* const &);//Determine whether it is a leaf node
bool __isNodeWithTwoChild(AVLnode * const &);//Determine whether there are two children
AVLnode *__search(AVLnode *const root, const T &x);//Internal implementation of lookup
void __deleteTree(AVLnode *root);//Delete all nodes of the tree
AVLnode *__Delete(AVLnode *root, const T &x);//Delete node
AVLnode *__treeMin(AVLnode *root);//Find the minimum of the current root node (all the way to the left)
AVLnode *__treeMax(AVLnode *root);//Find the maximum of the current root node (all the way to the right)
private:
AVLnode *avlroot;
};
AVL.cpp
// AVL
template<class T>
AVL<T>::AVL(const T *arr, int len)
{
avlroot = NULL;
for(int i = 0; i < len; ++ i)
Insert(*(arr+i));
}
template<class T>
AVL<T>::AVL(const std::vector<T> &vec)
{
avlroot = NULL;
for(int i = 0; i < (int)vec.size(); ++ i)
Insert(vec[i]);
}
template<class T>
void AVL<T>::__deleteTree(AVLnode *root)
{
if(root == NULL)
return ;
__deleteTree(root->getLchild());
__deleteTree(root->getRchild());
delete root;
root = NULL;
return ;
}
template<class T>
AVLNode<T> *AVL<T>::__Insert(AVLnode *root)
{
// if(root == NULL)
// {
// if(root == avlroot)
// std::cout << "hello\n";
// // if(avlroot == NULL)
// // {
// // AVLNode<T> *newnode = new AVLNode<T>(x);
// // avlroot = newnode;
// // return avlroot;
// // }
// AVLNode<T> *newnode = new AVLNode<T>(x);
// root = newnode;
// if(root == avlroot)
// std::cout << "hello\n";
// return root;
// }
// else if(x < root->getData())
// {
// AVLnode *p = root->getLchild();
// root->setLchild( __Insert(p, x) );
// root = __Balance(root);
// }
// else if(x > root->getData())
// {
// AVLnode *p = root->getRchild();
// root->setRchild( __Insert(p, x) );
// root = __Balance(root);
// }
// return root;
AVLnode *q = avlroot, *p = NULL;
while(q != NULL)
{
p = q;
if(root->getData() < q->getData())
q = q->getLchild();
else if(root->getData() > q->getData())
q = q->getRchild();
else
return NULL;
}
if(p == NULL)
{
avlroot = root;
return root;
}
else if(root->getData() < p->getData())
p->setLchild(root);
else if(root->getData() > p->getData())
p->setRchild(root);
q = avlroot;
AVLnode *t;
while(q != NULL)
{
t = q;
if(q == p)
{
break;
}
if(root->getData() < q->getData())
{
q = q->getLchild();
if(q == p)
{
break;
}
}
else
{
q = q->getRchild();
if(q == p)
{
break;
}
}
}
__Balance(t);
return root;
}
template<class T>
bool AVL<T>::Insert(const T &x)
{
AVLnode *t = new AVLNode<T>(x);
return __Insert(t) == NULL? false : true;
}
template<class T>
int AVL<T>::__height(AVLnode *root)
{
if(root == NULL)
return 0;
return std::max(__height(root->getLchild()), __height(root->getRchild()))+1;
}
template<class T>
int AVL<T>::__diff(AVLnode *root)
{
int fctor = __height(root->getLchild()) - __height(root->getRchild());
return fctor;
}
template<class T>
AVLNode<T> *AVL<T>::__Balance(AVLnode *root)
{
int fctor = __diff(root);
if(fctor > 1) //left higer than right
{
if(__diff(root->getLchild()) > 0)
root = __ll_Rotation(root);
else
root = __lr_Rotation(root);
}
else if(fctor < -1) //right higer than left
{
if(__diff(root->getRchild()) > 0)
root = __rl_Rotation(root);
else
root = __rr_Rotation(root);
}
return root;
}
template<class T>
AVLNode<T> *AVL<T>::__ll_Rotation(AVLnode *root)
{
AVLnode *tmp;
tmp = root->getLchild();
root->setLchild(tmp->getRchild());
tmp->setRchild(root);
if(root == avlroot)
avlroot = tmp;
return tmp;
}
template<class T>
AVLNode<T> *AVL<T>::__rr_Rotation(AVLnode *root)
{
AVLnode *tmp;
tmp = root->getRchild();
root->setRchild(tmp->getLchild());
tmp->setLchild(root);
if(root == avlroot)
avlroot = tmp;
return tmp;
}
template<class T>
AVLNode<T> *AVL<T>::__lr_Rotation(AVLnode *root)
{
AVLnode *tmp;
tmp = root->getLchild();
root->setLchild(__rr_Rotation(tmp));
return __ll_Rotation(root);
}
template<class T>
AVLNode<T> *AVL<T>::__rl_Rotation(AVLnode *root)
{
AVLnode *tmp;
tmp = root->getRchild();
root->setRchild(__ll_Rotation(tmp));
return __rr_Rotation(root);
}
template<class T>
AVLNode<T> *AVL<T>::__Delete(AVLnode *root, const T &x)
{
if(root == NULL)
return NULL;
if(!search(x))
{
std::cerr << "Delete error, key not find" << std::endl;
return root;
}
if(x == root->getData())
{
if(__isNodeWithTwoChild(root)) //There are two children
{
if(__diff(root) > 0)
{
root->setData(__treeMax(root->getLchild())->getData());
root->setLchild(__Delete(root->getLchild(), root->getData()));
}
else
{
root->setData(__treeMin(root->getRchild())->getData());
root->setRchild(__Delete(root->getRchild(), root->getData()));
}
}
else //Have a child, merge with leaves
{
AVLnode *tmp = root;
root = (root->getLchild()) ? (root->getLchild()) : (root->getRchild());
delete tmp;
tmp = NULL;
}
}
else if(x < root->getData()) //Delete left
{
root->setLchild(__Delete(root->getLchild(), x));
if(__diff(root) < -1)
{
if(__diff(root->getLchild()) > 0)
root = __rl_Rotation(root);
else
root = __rr_Rotation(root);
}
}
else
{
root->setRchild(__Delete(root->getRchild(), x));
if(__diff(root) > 1)
{
if(__diff(root->getLchild()) > 0)
root = __lr_Rotation(root);
else
root = __ll_Rotation(root);
}
}
return root;
}
template<class T>
bool AVL<T>::Delete(const T &x)
{
return __Delete(avlroot, x) == NULL? false : true;
}
template<class T>
AVLNode<T> *AVL<T>::__search(AVLnode *root, const T &x)
{
if(root == NULL)
return NULL;
if(x == root->getData())
return root;
else if(x < root->getData())
return __search(root->getLchild(), x);
else
return __search(root->getRchild(), x);
}
template<class T>
bool AVL<T>::search(const T &x)
{
return __search(avlroot, x) == NULL? false:true;
}
template<class T>
void AVL<T>::__InorderTraversal(AVLnode *root)
{
if(root == NULL)
return ;
__InorderTraversal(root->getLchild());
std::cout << root->getData() << " ";
__InorderTraversal(root->getRchild());
}
template<class T>
void AVL<T>::__InorderTraversal(AVLnode *root, std::vector<T> &vec)
{
if(root == NULL)
return ;
__InorderTraversal(root->getLchild(), vec);
vec.push_back(root->getData());
__InorderTraversal(root->getRchild(), vec);
}
template<class T>
void AVL<T>::InorderTraversal()
{
__InorderTraversal(avlroot);
}
template<class T>
void AVL<T>::InorderTraversal(std::vector<T> &vec)
{
__InorderTraversal(avlroot, vec);
}
template<class T>
bool AVL<T>::__isLeaf(AVLnode *const &root)
{
if(root->getLchild() == NULL && root->getRchild() == NULL)
return true;
return false;
}
template<class T>
bool AVL<T>::__isNodeWithTwoChild(AVLnode *const &root)
{
if(root->getLchild() != NULL && root->getRchild() != NULL)
return true;
return false;
}
template<class T>
AVLNode<T> *AVL<T>::__treeMax(AVLnode *root)
{
while(root->getRchild() != NULL)
root = root->getRchild();
return root;
}
template<class T>
AVLNode<T> *AVL<T>::__treeMin(AVLnode *root)
{
while(root->getLchild() != NULL)
root = root->getLchild();
return root;
}
Huffman tree
Node weight: a value with some practical meaning (e.g. indicating the importance of nodes, etc.)
Weighted path length of a node: the product of the path length (number of sides) from the root of the tree to the node and the weight of the node
Weighted path length of tree: the sum of weighted path lengths of all leaf nodes in the tree (WPL, Weighted Path Length)
Among the binary trees with n weighted leaf nodes, the binary tree with the smallest weighted path length (WPL) is called Huffman tree, also known as optimal binary tree
HUFFMAN.h
//Huffman tree
template<class T>
class HfNode
{
public:
HfNode() : lchild(NULL), rchild(NULL){};
HfNode(const int &w) : weight(w), lchild(NULL), rchild(NULL){};
HfNode(const HfNode<T> &h);
bool operator<(const HfNode<T> &h) const;
public:
int weight, idx;
HfNode<T> *lchild, *rchild;
};
template<class T>
class Huffman
{
public:
Huffman(const T &sa);
~Huffman(){ __del(hfroot); }
public:
bool IsLeaf(HfNode<T>* t); //Judge whether the node is a leaf node
void GetFreq(std::vector<int> &des);//Gets the current weight array
void BuildTree();//Build a Huffman tree
void BuildCode();//The coding table is constructed according to Huffman tree
void GetCodeList();//Traverse the code table and the code corresponding to the code table
//Preorder traversal and inorder traversal are to determine whether the shape of Huffman tree is correct
void PreOrder();
void InOrder();
std::string Expend(const std::string &des);//decompression
std::string Compress(const std::string &des);//compress
private:
void __del(HfNode<T> *t);
void __build(HfNode<T> *t, T x);
void __PreOrder(HfNode<T> *t);
void __InOrder(HfNode<T> *t);
private:
HfNode<T> *hfroot;
std::vector<int> freq; //Weight array
std::vector<T> st; //Coding table
std::unordered_map<T, std::string> m; //key is the character of the code table
};
HUFFMAN.cpp
template<class T>
HfNode<T>::HfNode(const HfNode<T> &h)
{
this->idx = h.idx;
this->weight = h.weight;
if(h.lchild != NULL)
{
this->lchild = new HfNode<T>();
*this->lchild = *(h.lchild);
}
else
this->lchild = NULL;
if(h.rchild != NULL)
{
this->rchild = new HfNode<T>();
*this->rchild = *(h.rchild);
}
else
this->rchild = NULL;
}
template<class T>
bool HfNode<T>::operator<(const HfNode<T> &h) const
{
return this->weight < h.weight;
}
template<class T>
Huffman<T>::Huffman(const T &sa)
{
int len = sa.size();
if(len == 0)
{
std::cout << "please input again" << std::endl;
exit(-1);
}
std::unordered_map<T, int> mymap;
for(int i = 0; i < len; ++ i)
{
if(mymap.find(sa[i]) == mymap.end())
mymap[sa[i]] = 1;
else
mymap[sa[i]] += 1;
}
for(const auto& t : mymap)
{
st.push_back(t.first);
freq.push_back(t.second);
}
}
template<class T>
bool Huffman<T>::IsLeaf(HfNode<T>* t)
{
if(t == NULL)
return false;
if(t->lchild == NULL && t->rchild == NULL)
return true;
else
return false;
}
template<class T>
void Huffman<T>::GetFreq(std::vector<int> &des)
{
for(int i = 0; i < freq.size(); ++ i)
des.push_back(freq[i]);
}
template<class T>
void Huffman<T>::BuildTree()
{
std::priority_queue<HfNode<T> > myqueue;
for(int i = 0; i < freq.size(); ++ i)
{
HfNode<T> *tmp = new HfNode<T>(freq[i]);
tmp->idx = i;
myqueue.push(*tmp);
}
while(myqueue.size() > 1)
{
HfNode<T> left = myqueue.top();
myqueue.pop();
HfNode<T> right = myqueue.top();
myqueue.pop();
HfNode<T>* parent = new HfNode<T>(left.weight + right.weight);
parent->idx = -1;
parent->lchild = &left;
parent->rchild = &right;
myqueue.push(*parent);
}
hfroot = new HfNode<T>();
*hfroot = myqueue.top();
myqueue.pop();
}
template<class T>
void Huffman<T>::BuildCode()
{
if(hfroot == NULL)
return ;
T tmp;
tmp.clear();
__build(hfroot, tmp);
}
template<class T>
void Huffman<T>::GetCodeList()
{
for(const auto& t : m)
{
std::cout << t.first << " " << t.second << "\n";
}
}
template<class T>
void Huffman<T>::PreOrder()
{
if(hfroot == NULL)
return ;
__PreOrder(hfroot);
}
template<class T>
void Huffman<T>::InOrder()
{
if(hfroot == NULL)
return ;
__InOrder(hfroot);
}
template<class T>
std::string Huffman<T>::Expend(const std::string &des)
{
std::string res;
int i(0), n(des.size());
HfNode<T>* temp = new HfNode<T>();
temp = hfroot;
while (i < n) {
if (des[i]=='0')
{
temp = temp->lchild;
i++;
if (IsLeaf(temp)) {
res += st[temp->idx];
temp = hfroot;
continue;
}
}
if (des[i] == '1')
{
temp = temp->rchild;
i++;
if (IsLeaf(temp)) {
res += st[temp->idx];
temp = hfroot;
continue;
}
}
}
return res;
}
template<class T>
std::string Huffman<T>::Compress(const std::string& des)
{
std::string res;
for (int i = 0; i < des.length(); ++i) {
if (des[i] == '\n' || des[i]==' ')
continue;
res += m[des[i]];
}
return res;
}
template<class T>
void Huffman<T>::__PreOrder(HfNode<T>* t)
{
if (t == NULL) return;
std::cout << t->idx << " : " << t->weight << std::endl;
_PreOrder(t->lchild);
_PreOrder(t->rchild);
}
template<class T>
void Huffman<T>::__InOrder(HfNode<T>* t)
{
if (t == NULL) return;
_InOrder(t->lchild);
std::cout << t->idx << " : " << t->weight << std::endl;
_InOrder(t->rchild);
}
template<class T>
void Huffman<T>::__del(HfNode<T>* t)
{
if (t == nullptr)
return;
if (t->lchild)
__del(t->lchild);
if (t->rchild)
__del(t->rchild);
}
template<class T>
void Huffman<T>::__build(HfNode<T> *t, T x)
{
if (IsLeaf(t) && t->idx >= 0)
{
std::cout << x << " ";
m[st[t->idx]] = x;
return;
}
if(t->lchild) __build(t->lchild, x + '0');
if(t->rchild) __build(t->rchild, x + '1');
}