热门标签
热门文章
- 1Win10(Windows)系统中窗口切换 最大最小化窗口等快捷键_窗口化快捷键是什么
- 2微信小程序授权登录 获取用户信息与手机号_查看有多少小程序获取了手机号
- 3LlamaIndex ：面向QA 系统的全新文档摘要索引
- 4MySQL知识点总结_mysql 知识总结
- 5【图灵】iOS技能书单——入门+进阶+精通_ios 学习javascript书籍
- 6Phi-2: 一个易于在您的GPU上进行微调的小型模型 在消费硬件上进行微调和量化的指导_单卡 微调 phi
- 7UI自动化之图片验证码处理_ui自动化截取验证码部分
- 8在linux上部署Java项目_linux部署java项目
- 9如何用spss做灰色关联度分析？手把手教学快速掌握_spss灰色关联度分析
- 10AI 智能写作与智能写诗_ai写作框架图片
当前位置: article > 正文
BST树 非递归中序遍历 | 中序线索化 | AVL树
作者：我家自动化 | 2024-03-20 16:28:40
赞
踩
bst树 非递归
带父指针的BST树。
typedef int Type;
typedef struct BSTreeNode{
Type key; // 关键字(键值)
struct BSTreeNode *left; // 左孩子
struct BSTreeNode *right; // 右孩子
struct BSTreeNode *parent; // 父结点
}BstNode, *BSTree;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
BstNode * First(BstNode * ptr); // 找左孩子，即最小元素节点
BstNode * Last(BstNode * ptr); // 找右孩子，即最大元素节点
void NiceInOrder(BstNode * ptr)
{
for( BstNode * p = First(ptr); p != nullptr; p = Next(p) )
{
cour << p->key;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
// 需要设计实现Next函数
BstNode * Next(BstNode * ptr)
{
if(ptr == nullptr) return nullptr;
if(ptr->right != nullptr) // 情况1，有右子树，需要遍历右子树
{
return First(ptr->right);
}
else
{
BstNode * pa = ptr->parent; // 情况2/3 先得到父结点
while(pa != nullptr && pa->right == ptr)// 情况3，证明刚才是从右孩子回退的。则当前结点不取。
{ // pa->left != ptr 也是可以的，如果是父结点的左孩子（从左边回退），我们取当前结点。否则不取
ptr = pa;
pa = pa->next; // 反复操作，因为存在多次的回退操作
}
return pa;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
上述的几部操作，类似使用树形结构的容器的迭代器操作。其中：
- begin（）可对应 First（root）
- it++ 可对应 Next（p）操作。it 为迭代器，p 为当前结点指针
- it-- 可对应 Prev（p操作）。…
- end（）可对应 Last（root）操作
根据上述操作经验，Prev和 逆向的迭代中序即可实现。
void ResNiceInOrder(BstNode * ptr)
{
for(BstNode * p = Last(ptr); p != nullptr; p = Prev(p) )
{
cout << p->key;
}
}
// 与Next的操作为镜像的操作
BstNode * Prev(BstNode * ptr)
{
if(ptr == nullptr) return nullptr;
if(ptr->left != nullptr)
{
return Last(ptr->left);
}
else
{
BstNode * pa = ptr->parent;
while(pa != nullptr && pa->left == ptr) // or pa->right != ptr
{
ptr = pa;
pa = pa->parent;
}
return pa;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
全部代码：
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
typedef int KeyType;
typedef struct BstNode
{
KeyType key;
BstNode* leftchild;
BstNode* parent;
BstNode* rightchild;
}BstNode, * BSTree;
BstNode* Buynode(KeyType kx)
{
BstNode* s = (BstNode*)malloc(sizeof(BstNode));
if (nullptr == s) exit(1);
memset(s, 0, sizeof(BstNode));
s->key = kx;
return s;
}
void Freenode(BstNode* p)
{
free(p);
}
bool Insert(BstNode*& ptr, KeyType kx)
{
if (ptr == nullptr)
{
ptr = Buynode(kx);
return true;
}
BstNode* pa = nullptr;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
pa = p;
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p != nullptr && p->key == kx) return false;
p = Buynode(kx);
p->parent = pa;
if (p->key < pa->key)
{
pa->leftchild = p;
}
else
{
pa->rightchild = p;
}
return true;
}
void InOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
InOrder(ptr->leftchild);
cout << ptr->key << " ";
InOrder(ptr->rightchild);
}
}
BstNode* First(BstNode* ptr) // Min
{
while (ptr != nullptr && ptr->leftchild != nullptr)
{
ptr = ptr->leftchild;
}
return ptr;
}
BstNode* Last(BstNode* ptr) // Max
{
while (ptr != nullptr && ptr->rightchild != nullptr)
{
ptr = ptr->rightchild;
}
return ptr;
}
BstNode* Next(BstNode* ptr)
{
if (ptr == nullptr) return nullptr;
if (ptr->rightchild != nullptr)
{
return First(ptr->rightchild);
}
else
{
BstNode* pa = ptr->parent;
while (pa != nullptr && pa->leftchild != ptr)
{
ptr = pa;
pa = ptr->parent;
}
return pa;
}
}
BstNode* Prev(BstNode* ptr)
{
if (ptr == nullptr) return nullptr;
if (ptr->leftchild != nullptr)
{
return Last(ptr->leftchild);
}
else
{
BstNode* pa = ptr->parent;
while (pa != nullptr && pa->rightchild != ptr)
{
ptr = pa;
pa = ptr->parent;
}
return pa;
}
}
void NiceInOrder(BstNode* ptr)
{
for (BstNode* p = First(ptr); p != nullptr; p = Next(p))
{
cout << p->key << " ";
}
cout << endl;
}
void ResNiceInOrder(BstNode* ptr)
{
for (BstNode* p = Last(ptr); p != nullptr; p = Prev(p))
{
cout << p->key << " ";
}
cout << endl;
}
int main()
{
BSTree root = nullptr;
vector<int> ar = { 53,17,78,9,45,65,87,23,81,94,88,92 };
for (auto& x : ar)
{
Insert(root, x);
}
InOrder(root);
cout << endl;
NiceInOrder(root);
ResNiceInOrder(root);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
不带双亲结点（不含父指针）的BST树，按照中序遍历的方式改造成链表（线索化）。
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
typedef int KeyType;
typedef struct BstNode
{
KeyType key;
BstNode* leftchild;
BstNode* rightchild;
}BstNode, * BSTree;
BstNode* Buynode(KeyType kx)
{
BstNode* s = (BstNode*)malloc(sizeof(BstNode));
if (nullptr == s) exit(1);
memset(s, 0, sizeof(BstNode));
s->key = kx;
return s;
}
void Freenode(BstNode* p)
{
free(p);
}
bool Insert(BstNode*& ptr, KeyType kx)
{
if (ptr == nullptr)
{
ptr = Buynode(kx);
return true;
}
BstNode* pa = nullptr;
BstNode* p = ptr;
while (p != nullptr && p->key != kx)
{
pa = p;
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p != nullptr && p->key == kx) return false;
p = Buynode(kx);
if (p->key < pa->key)
{
pa->leftchild = p;
}
else
{
pa->rightchild = p;
}
return true;
}
void InOrder(BstNode* ptr)
{
if (ptr != nullptr)
{
InOrder(ptr->leftchild);
cout << ptr->key << " ";
InOrder(ptr->rightchild);
}
}
// 借助栈，非递归的中序遍历
void NiceInOrder(BstNode* ptr)
{
stack<BstNode*> st;
while (ptr != nullptr || !st.empty())
{
while (ptr != nullptr)
{
st.push(ptr);
ptr = ptr->leftchild;
}
ptr = st.top(); st.pop();
cout << ptr->key << " ";
ptr = ptr->rightchild;
}
}
// 将BST树按照中序遍历的方式，线索化
BstNode* InOrderList(BstNode* ptr)
{
if (ptr == nullptr) return nullptr;
stack<BstNode*> st;
BstNode* newroot = nullptr;
BstNode* pre = nullptr;
while (ptr != nullptr || !st.empty())
{
while (ptr != nullptr)
{
st.push(ptr);
ptr = ptr->leftchild;
}
ptr = st.top(); st.pop();
if (pre == nullptr)
{
newroot = ptr;
pre = ptr;
}
else
{
pre->rightchild = ptr;
ptr->leftchild = pre;
pre = ptr;
}
ptr = ptr->rightchild;
}
return newroot;
}
int main()
{
BSTree root = nullptr;
vector<int> ar = { 53,17,78,9,45,65,87,23,81,94,88,92 };
for (auto& x : ar)
{
Insert(root, x);
}
InOrder(root);
cout << endl;
NiceInOrder(root);
cout << endl;
root = InOrderList(root);
BstNode* p = root;
// 正向打印
for ( ; p->rightchild != nullptr; p = p->rightchild)
{
cout << p->key << "->";
}
cout << p->key << endl;
// 逆向打印
for ( ; p != nullptr; p = p->leftchild)
{
cout << p->key << "->";
}
cout << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
typedef int KeyType;
typedef struct AVLNode
{
AVLNode* leftchild;
AVLNode* parent;
AVLNode* rightchild;
int balance; // -1 ,0 ,1
KeyType key;
}AVLNode, * AVLTree;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
左单旋转：
第一步：先将左右孩子结点完成旋转。
void RotateLeft(AVLTree& root, AVLNode* ptr)
{
AVLNode* newroot = ptr->rightchild;
ptr->rightchild = newroot->leftchild;
newroot->leftchild = ptr;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
第二步：将父指针部分补充完整
void RotateLeft(AVLTree& root, AVLNode* ptr)
{
AVLNode* newroot = ptr->rightchild;
newroot->parent = ptr->parent;// 1 新的头结点指向原先的根节点的父节点
if (ptr->parent == nullptr)// 如果ptr是整棵树的根节点，则将root更新为 新的根节点newroot
{
root = newroot;
}
else// 如果ptr原先不是根节点，则查看ptr是其父节点的左孩子还是右孩子，然后更新父节点的孩子指向
{
if (ptr->parent->leftchild == ptr)
{
ptr->parent->leftchild = newroot;
}
else
{
ptr->parent->rightchild = newroot;
}
}
ptr->rightchild = newroot->leftchild;
if (newroot->leftchild != nullptr)//60结点的父节点指向50结点，注意60结点可能不存在
{
newroot->leftchild->parent = ptr;// 2
}
newroot->leftchild = ptr;
ptr->parent = newroot; // 3
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
右单旋转同理。
双旋：
总结：如果结点是一条斜线，则我们需要进行单旋。如果是成“折线”状，则我们需要进行两次旋转。
- 斜线：单旋转
- 折线，双旋转
实现左平衡
参考代码：
// 左边平衡的调整。 ptr 指向balance为-2的结点
void LeftBalance(AVLTree& tree, AVLNode* ptr)
{ // 指向其左孩子，balance为-1或1 // 指向其左孩子的右孩子
AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;
switch (leftsub->balance)
{
case 0: // 当前平衡，无需旋转
cout << "Left balance \n"; break;
case -1: // 需要（右）单旋转
ptr->balance = 0; // 进行左旋后，ptr的balance当为0
leftsub->balance = 0; // 。。。。
RotateRight(tree, ptr);
break;
case 1: // 需要双旋转
rightsub = leftsub->rightchild;
switch (rightsub->balance)
{
case 1:
ptr->balance = 0;
leftsub->balance = -1;
break;
case 0:
ptr->balance = 0;
leftsub->balance = 0;
break;
case -1:
ptr->balance = 1;
leftsub->balance = 0;
break;
}
rightsub->balance = 0;// 该结点最终成为根节点，且平衡因子为0
RotateLeft(tree, leftsub);
RotateRight(tree, ptr);
break;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
对于以上switch（）中给出的几种情况，分别如下：
- 只需要进行单旋转，旋转后所有结点的平衡因子皆是 0
- 需要进行双旋转（折线）
同样到，右子树平衡是左子树平衡的镜像操作。
void RightBalance(AVLTree& tree, AVLNode* ptr)
{
AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;
switch (rightsub->balance)
{
case 0: cout << "right balance \n"; break;
case 1:
ptr->balance = 0;
rightsub->balance = 0;
RotateLeft(tree, ptr);
break;
case -1:
leftsub = rightsub->leftchild;
switch (leftsub->balance)
{
case 1:
ptr->balance = -1;
rightsub->balance = 0;
break;
case 0:
ptr->balance = 0;
rightsub->balance = 0;
break;
case -1:
ptr->balance = 0;
rightsub->balance = 1;
break;
}
leftsub->balance = 0;
RotateRight(tree, rightsub);
RotateLeft(tree, ptr);
break;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
接下来就是调整树上结点的时机了。需要调整的时机是，我们插入结点之后，进行调整。
bool Insert(AVLTree& tree, KeyType kx)
{
Adjust_AVL(tree, p); // 调整结点
return true;
}
- 1
- 2
- 3
- 4
- 5
同时，我们需要先补完调整结点的函数过程。通过不断的向父节点回溯，直至到达根节点。将沿途的结点的平衡因子修改。
void Adjust_AVL(AVLTree& tree, AVLNode* ptr)
{
AVLNode* pa = ptr->parent; // ptr为刚插入的结点
bool high = true; // ptr改变，对树的高度是否产生影响
while (high && pa != nullptr) // 向上遍历，设置平衡因子
{
if (pa->rightchild == ptr) // 在pa的右边插入ptr
{
switch (pa->balance) // 原pa的平衡因子
{
case 0: pa->balance = 1; break;
case -1:
pa->balance = 0;
high = false;
break;
case 1: // 如果ptr插入，则pa将变为2，这里可以先进行一次调整
RightBalance(tree, pa);
high = false;
break;
}
}
else // left
{
switch (pa->balance)
{
case 0: pa->balance = -1; break;
case 1:
pa->balance = 0;
high = false;
break;
case -1:
LeftBalance(tree, pa);
high = false;
break;
}
}
ptr = pa; // 向树根回溯
pa = ptr->parent;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
完整代码如下：
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
typedef int KeyType;
typedef struct AVLNode
{
AVLNode* leftchild;
AVLNode* parent;
AVLNode* rightchild;
int balance; // -1 ,0 ,1
KeyType key;
}AVLNode, * AVLTree;
AVLNode* Buynode(KeyType kx)
{
AVLNode* s = (AVLNode*)malloc(sizeof(AVLNode));
if (nullptr == s) exit(1);
memset(s, 0, sizeof(AVLNode));
s->key = kx;
return s;
}
void Freenode(AVLNode* p)
{
free(p);
}
void RotateLeft(AVLTree& root, AVLNode* ptr)
{
AVLNode* newroot = ptr->rightchild;
newroot->parent = ptr->parent;// 1 新的头结点指向原先的根节点的父节点
if (ptr->parent == nullptr)// 如果ptr是整棵树的根节点，则将root更新为 新的根节点newroot
{
root = newroot;
}
else// 如果ptr原先不是根节点，则查看ptr是其父节点的左孩子还是右孩子，然后更新父节点的孩子指向
{
if (ptr->parent->leftchild == ptr)
{
ptr->parent->leftchild = newroot;
}
else
{
ptr->parent->rightchild = newroot;
}
}
ptr->rightchild = newroot->leftchild;
if (newroot->leftchild != nullptr)//60结点的父节点指向50结点，注意60结点可能不存在
{
newroot->leftchild->parent = ptr;// 2
}
newroot->leftchild = ptr;
ptr->parent = newroot; // 3
}
void RotateRight(AVLTree& root, AVLNode* ptr)
{
AVLNode* newroot = ptr->leftchild;
newroot->parent = ptr->parent;//1
if (ptr->parent == nullptr)
{
root = newroot;
}
else
{
if (ptr->parent->leftchild == ptr)
{
ptr->parent->leftchild = newroot;
}
else
{
ptr->parent->rightchild = newroot;
}
}
ptr->leftchild = newroot->rightchild;
if (newroot->rightchild != nullptr)
{
newroot->rightchild->parent = ptr;
}
newroot->rightchild = ptr;
ptr->parent = newroot;
}
// 左边平衡的调整。 ptr 指向balance为-2的结点
void LeftBalance(AVLTree& tree, AVLNode* ptr)
{ // 指向其左孩子，balance为-1或1 // 指向其左孩子的右孩子
AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;
switch (leftsub->balance)
{
case 0: // 当前平衡，无需旋转
cout << "Left balance \n"; break;
case -1: // 需要（右）单旋转
ptr->balance = 0; // 进行左旋后，ptr的balance当为0
leftsub->balance = 0; // 。。。。
RotateRight(tree, ptr);
break;
case 1: // 需要双旋转
rightsub = leftsub->rightchild;
switch (rightsub->balance)
{
case 1:
ptr->balance = 0;
leftsub->balance = -1;
break;
case 0:
ptr->balance = 0;
leftsub->balance = 0;
break;
case -1:
ptr->balance = 1;
leftsub->balance = 0;
break;
}
rightsub->balance = 0; // 该结点最终成为根节点，且平衡因子为0
RotateLeft(tree, leftsub);
RotateRight(tree, ptr);
break;
}
}
void RightBalance(AVLTree& tree, AVLNode* ptr)
{
AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;
switch (rightsub->balance)
{
case 0: cout << "right balance \n"; break;
case 1:
ptr->balance = 0;
rightsub->balance = 0;
RotateLeft(tree, ptr);
break;
case -1:
leftsub = rightsub->leftchild;
switch (leftsub->balance)
{
case 1:
ptr->balance = -1;
rightsub->balance = 0;
break;
case 0:
ptr->balance = 0;
rightsub->balance = 0;
break;
case -1:
ptr->balance = 0;
rightsub->balance = 1;
break;
}
leftsub->balance = 0;
RotateRight(tree, rightsub);
RotateLeft(tree, ptr);
break;
}
}
void Adjust_AVL(AVLTree& tree, AVLNode* ptr)
{
AVLNode* pa = ptr->parent; // ptr为刚插入的结点
bool high = true; // ptr改变，对树的高度是否产生影响
while (high && pa != nullptr) // 向上遍历，设置平衡因子
{
if (pa->rightchild == ptr) // 在pa的右边插入ptr
{
switch (pa->balance) // 原pa的平衡因子
{
case 0: pa->balance = 1; break;
case -1:
pa->balance = 0;
high = false;
break;
case 1: // 如果ptr插入，则pa将变为2，这里可以先进行一次调整
RightBalance(tree, pa);
high = false;
break;
}
}
else // left
{
switch (pa->balance)
{
case 0: pa->balance = -1; break;
case 1:
pa->balance = 0;
high = false;
break;
case -1:
LeftBalance(tree, pa);
high = false;
break;
}
}
ptr = pa; // 向树根回溯
pa = ptr->parent;
}
}
bool Insert(AVLTree& ptr, KeyType kx)
{
if (ptr == nullptr)
{
ptr = Buynode(kx);
return true;
}
AVLNode* pa = nullptr;
AVLNode* p = ptr;
while (p != nullptr && p->key != kx)
{
pa = p;
p = kx < p->key ? p->leftchild : p->rightchild;
}
if (p != nullptr && p->key == kx) return false;
p = Buynode(kx);
p->parent = pa;
if (p->key < pa->key)
{
pa->leftchild = p;
}
else
{
pa->rightchild = p;
}
Adjust_AVL(ptr, p); // 调整结点
return true;
}
void InOrder(AVLTree ptr)
{
if (ptr != nullptr)
{
InOrder(ptr->leftchild);
cout << ptr->key << " ";
InOrder(ptr->rightchild);
}
}
/* ---------------- 打印二叉树结构 ----------------------*/
// https://blog.csdn.net/weixin_41990671/article/details/108885298
#include <unordered_map>
#include <queue>
#include <string>
/**
* 中序遍历返回节点数组
* @param root 根节点
* @return 中序遍历节点数组
*/
std::vector<AVLNode*> inorderTraversal(AVLNode* root) {
std::vector<AVLNode*> res;
std::stack<AVLNode*> stk;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.push(root);
root = root->leftchild;
}
root = stk.top();
stk.pop();
res.push_back(root);
root = root->rightchild;
}
return res;
}
/**
* 利用下划线和正反斜杠打印出美观的二叉树，没有破坏二叉树结构，但传入的root会有变化
* @param root 二叉树根节点
*/
void printTree(AVLNode* root) {
if (!root)return;
auto tmp = root;
std::vector<AVLNode*> intv = inorderTraversal(tmp);//中序遍历节点数组
std::string template_str;//模板string，表示每行打印string的长度
int location = 0;
std::unordered_map<AVLNode*, int> first_locations;//存储节点对应在本行string中的首位置
for (auto& i : intv) {
location = template_str.size();
template_str += std::to_string(i->key) + " ";
first_locations[i] = location;
}
for (auto& i : template_str)i = ' ';//把模板全部置为空格方便后续使用
//层序遍历
std::queue<AVLNode*> q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
int cur_loc = 0;
std::string tmp_str1 = template_str, tmp_str2 = template_str;//1为节点所在行，2为其下一行
for (int i = 1; i <= currentLevelSize; ++i) {
auto node = q.front();
q.pop();
cur_loc = first_locations[node];
std::string num_str = std::to_string(node->key);
//左边，如果存在左孩子，那么在第二行对应位置打印'/'，在第一行补上'_'
if (node->leftchild) {
q.push(node->leftchild);
int first_loc = first_locations[node->leftchild] + 1;
tmp_str2[first_loc++] = '/';
while (first_loc < cur_loc)tmp_str1[first_loc++] = '_';
}
//中间,对应位置打印节点值（有可能为多位数）
for (int j = 0; j < num_str.length(); ++j, ++cur_loc) {
tmp_str1[cur_loc] = num_str[j];
}
//右边，如果存在右孩子，那么在第二行对应位置打印'\'，在第一行补上'_'
if (node->rightchild) {
q.push(node->rightchild);
int last_loc = first_locations[node->rightchild] - 1;
tmp_str2[last_loc] = '\\';
while (cur_loc < last_loc) {
tmp_str1[cur_loc++] = '_';
}
}
}
//打印两行
std::cout << tmp_str1 << std::endl;
std::cout << tmp_str2 << std::endl;
}
}
/*----------------------------------------------------*/
int main()
{
AVLTree root = nullptr;
vector<int> ar = { 53,17,78,9,45,65,87,23,81,94,88,92 };
for (auto& x : ar)
{
Insert(root, x);
}
cout << "中序遍历: { ";
InOrder(root);
cout << " }\n树型结构为：\n";
printTree(root);
cout << endl;
}
/* 输出：
中序遍历: { 9 17 23 45 53 65 78 81 87 88 92 94 }
树型结构为：
_______53_________
/ \
17___ ____87___
/ \ / \
9 _45 _78 _92
/ / \ / \
23 65 81 88 94
*/
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/275017
推荐阅读
- 先引入
赞
踩
相关标签
