#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
using namespace std;
#define max_size 1010
//双亲表示法
typedef struct
{
int data;
int parent; //节点的父节点在数组中的下标
}PTNode;
typedef struct
{
PTNode nodes[max_size];
int len;
}PTTree;
//孩子表示法
struct CNode
{
int data;
struct CNode* ne;
};
typedef struct
{
int data;
CNode *firstchild;
}CTBox;
typedef struct
{
CTBox nodes[max_size];
int len, r;
}CTree;
//孩子兄弟表示法
typedef struct CSNode
{
int data;
struct CSNode* firstchild, *nextsibling;
}CSNode, *CSTree;
//线索二叉树
typedef struct TreeNode
{
int data;
struct TreeNode* lchild, *rchild;
int ltag, rtag;
}TreeNode, *Tree;
//前序遍历非递归
vector<int> preorder(Tree& tr)
{
stack<TreeNode*> s;
vector<int> res;
TreeNode* p = tr;
while (p || !s.empty())
{
while (p)
{
res.push_back(p->data);
s.push(p);
p = p->lchild;
}
p = s.top();
s.pop();
p = p->rchild;
}
}
//中序遍历非递归
vector<int> inorder(Tree& tr)
{
stack<TreeNode*> s;
vector<int> res;
TreeNode* p = tr;
while (p || !s.empty())
{
while (p)
{
s.push(p);
p = p->lchild;
}
p = s.top();
s.pop();
res.push_back(p->data);
p = p->rchild;
}
}
vector<int> postorder(Tree& tr)
{
stack<TreeNode*> s;
vector<int> res;
TreeNode* p = tr;
while (p || !s.empty())
{
while (p)
{
res.push_back(p->data);
s.push(p);
p = p->rchild;
}
p = s.top();
s.pop();
p = p->lchild;
}
reverse(res.begin(), res.end());
return res;
}
vector<int> postorder2(Tree &tr)
{
vector<int> res;
stack<TreeNode*> s;
TreeNode* p = tr, *visited = nullptr;
while (p || !s.empty())
{
while (p)
{
s.push(p);
p = p->lchild;
}
p = s.top();
if (p->rchild && p->rchild != visited)
p = p->rchild;
else
{
res.push_back(p->data);
visited = p;
s.pop();
p = nullptr;
}
}
return res;
}
//线索化二叉树
void inThread(Tree& p, TreeNode* pre)
{
if (p)
{
inThread(p->lchild, pre);
if (!p->lchild)
{
p->lchild = pre;
p->ltag = 1;
}
if (!pre && !pre->rchild)
{
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
inThread(p->rchild, pre);
}
}
//建立线索二叉树
void createrThread(Tree& root)
{
TreeNode* pre = NULL;
if (!root)
{
inThread(root, pre);
pre->rchild = NULL;
pre->rtag = 1;
}
}
void visit(TreeNode* p)
{
cout << p->data << endl;
}
//找到中序遍历第一个节点
TreeNode* firstNode(Tree& T)
{
TreeNode* p = T;
while (p->ltag == 0) p = p->lchild; //不一定是叶子节点
return p;
}
//找到中序遍历最后一个节点
TreeNode* lastNode(Tree& T)
{
TreeNode* p = T;
while (p->rtag == 0) p = p->rchild;
return p;
}
//找到当前节点下一个节点
TreeNode* nextNode(TreeNode* p)
{
if (!p->rtag) return firstNode(p->rchild);
else return p->rchild;
}
//找到当前节点前一个节点
TreeNode* preNode(TreeNode* p)
{
if (!p->ltag) return lastNode(p->lchild);
else return p->lchild;
}
//顺序遍历中序线索二叉树
void inorderThread(Tree& T)
{
for (TreeNode* p = firstNode(T); !p; p = nextNode(p))
visit(p);
}
//逆序遍历中序线索二叉树
void RinorderThread(Tree& T)
{
for (TreeNode* p = lastNode(T); !p; p = preNode(p))
visit(p);
}
/*
中序遍历后继:
1. p->rtag = 1 则右孩子就是后继
2. p->rtag = 0(肯定有右孩子) 后继是右子树中中序遍历第一个节点(左下方)
中序遍历前驱:
1.p->ltag = 1 则左孩子就是前驱
2.p->ltag = 0(肯定有左孩子) 前驱是左子树中中序遍历最后一个节点(右下方)
先序遍历后继:
1. p->rtag = 1 则右孩子就是后继
2. p->rtag = 0
1.有左孩子:找到先序遍历左子树第一个节点(就是左子树根节点)
2.没有左孩子:找到先序遍历右子树第一个节点(就是右孩子根节点)
先序遍历前驱(假设这是一个三叉链表, 为了找父节点)
1.p->ltag = 1 则左孩子就是前驱
2.p->ltag = 0: 按照根 左 右顺序p的前驱节点一定不在以p为根节点的子树中
1.p没有父节点 则p的前驱是NULL
2.p有父节点q且p正好为q的左孩子,则p的前驱为父节点q
3.p有父节点q且p为q的右孩子但是q的左孩子为空,则p的前驱为父节点q
4.p有父节点q且p为q的右孩子但是q的左孩子不为空, 则p的前驱为q的左子树中先序遍历最后一个元素
后序遍历后继:
1.p->rtag = 1 则右孩子就是后继
2.p->rtag = 0: 按照左, 右, 根,后继节点一定不在以p为根节点的子树中
1.p没有父节点,后继为NULL
2.p有父节点q且p是q的右孩子 则p的前驱为父节点q
3.p有父节点q且p是q的左孩子且右孩子为空 则p的前驱为父节点q
4.p有父节点q且p是q的左孩子且右孩子不为空 则p的前驱为q的右子树中后序遍历第一个元素
后序遍历前驱:
1.p->ltag = 1 则左孩子就是前驱
2.p->ltag = 0 (肯定有左孩子)
1.有右孩子:前驱就是右孩子
2.没有右孩子:前去就是左孩子
*/
//二叉查找树
typedef struct BNode
{
int data;
struct BNode *lchild, *rchild;
}BNode, *BTree;
//创建
void BST_insert(BTree& T, int x)
{
BNode* parent = NULL;
BNode *p = T;
while (p != NULL)
{
parent = p;
if (x < p->data) p = p->lchild;
else if (x > p->data) p = p->rchild;
}
BNode* ne = (BNode*)malloc(sizeof(BNode));
ne->data = x;
ne->lchild = NULL;
ne->rchild = NULL;
if (parent->data > x) parent->lchild = ne;
else parent->rchild = ne;
}
void BST_create(BTree T, int arr[], int n)
{
for (int i = 0; i < n; i++) BST_insert(T, arr[i]);
}
//查找
BNode* BST_find(BTree T, int x)
{
while (T != NULL && T->data != x)
{
if (x < T->data) T = T->lchild;
else T = T->rchild;
}
return T;
}
/*删除
1.叶子节点:直接删除
2.删除的节点只有右子树:右子树填补(删除该结点且使被删除节点的双亲结点指向被删除节点的右孩子结点)
3.删除的节点只有左子树:左子树填补(删除该结点且使被删除节点的双亲结点指向被删除结点的左孩子结点)
4.删除的节点有右子树和左子树:找到该节点的中序遍历前驱或后继填补
*/
BNode* find_next(BNode* p, BNode* parent)
{
while (p->lchild) parent = p, p = p->lchild;
return p;
}
void BST_del(BTree& T, int x)
{
BNode* cur = T;
BNode* parent = T;
BNode* del = NULL;
while (cur)
{
if (x < cur->data)
{
parent = cur;
cur = cur->lchild;
}
else if (x > cur->data)
{
parent = cur;
cur = cur->rchild;
}
else
{
//情况1
if (cur->lchild == NULL && cur->rchild == NULL)
{
if (parent->lchild == cur) parent->lchild = NULL;
else parent->rchild = NULL;
}
//情况2
else if (cur->lchild == NULL)
{
if (parent->lchild == cur) parent->lchild = cur->rchild;
else parent->rchild = cur->rchild;
}
//情况3
else if (cur->rchild == NULL)
{
if (parent->lchild == cur) parent->lchild = cur->lchild;
else parent->rchild = cur->lchild;
}
//情况4
else
{
BNode* parent = NULL;
BNode* p = find_next(cur->rchild, parent);
del = p;
cur->data = p->data;
//转化为情况2
if (parent->lchild == p) parent->lchild = p->rchild;
else parent->rchild = p->rchild;
}
}
}
}
//平衡二叉树AVL
typedef struct AVLNode
{
int data;
struct AVLNode* lchild, *rchild;
int h;
}AVLNode, *AVLTree;
/*旋转
1.LL平衡旋转:
2.RR平衡旋转:
3.LR平衡旋转:
4.RL平衡旋转:
*/
AVLNode* LL(AVLNode* p)
{
AVLNode* q = p->lchild;
p->lchild = q->rchild;
q->rchild = p;
//更新高度
p->h = max(p->lchild->h, p->rchild->h) + 1;
q->h = max(q->lchild->h, q->rchild->h) + 1;
return q;
}
AVLNode* RR(AVLNode* p)
{
AVLNode* q = p->rchild;
p->rchild = q->lchild;
q->lchild = p;
p->h = max(p->lchild->h, p->rchild->h) + 1;
p->h = max(p->lchild->h, p->rchild->h) + 1;
return q;
}
AVLNode* LR(AVLNode* p)
{
p->lchild = RR(p->lchild);
return LL(p);
}
AVLNode* RL(AVLNode* p)
{
p->rchild = LL(p->rchild);
return RR(p);
}
AVLTree insert(AVLTree T, int x)
{
if (T == NULL)
{
T = (AVLNode*)malloc(sizeof AVLNode);
T->data = x;
T->lchild = T->rchild = NULL;
T->h = 0;
}
else
{
if (x < T->data)
{
T->lchild = insert(T->lchild, x);
if (T->lchild->h - T->rchild->h == 2)
{
if (x < T->lchild->data) T = LL(T);
else T = LR(T);
}
}
else if (x > T->data)
{
T->rchild = insert(T->rchild, x);
if (T->rchild->h - T->lchild->h == 2)
{
if (x > T->rchild->data) T = RR(T);
else T = RL(T);
}
}
}
T->h = max(T->lchild->h, T->rchild->h) + 1;
return T;
}
int main()
{
return 0;
}