＜数据结构学习＞查找——平衡二叉树
查找——平衡二叉树的建立与遍历
·
目录
题目描述
程序输入一个字符串（只包含小写字母），请按照字符的输入顺序建立平衡二叉排序树，并分别输出二叉树的先序序列、中序序列和后序序列，最后输出该二叉树向左旋转 90 度后的结构。
例如：向左旋转 90 度后，以每层向里缩进 4 个空格的方式输出，输出结果为：
i
g
f
a
d
c
b
输入：agxnzyimk
输出：
Preorder: xigamknzy
Inorder: agikmnxyz
Postorder: agknmiyzx
Tree:
z
y
x
n
m
k
i
g
a
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
|
以文本方式显示
|
1秒 | 64M | 0 |
| 测试用例 2 | 以文本方式显示
|
以文本方式显示
|
1秒 | 64M | 0 |
题目分析
这道题的思路比较清晰。就是先建树，后以四种形式输出。
建树的时候，要注意每插入一个结点时树是否还平衡，若不平衡要调整到平衡，调整方法有LL型，RR型，LR型和RL型四种模式。
输出的时候前序、中序、后序输出不必多说。旋转90度输出实际是按先右后中再左的顺序。然后按层数空格即可。
问题解决
struct Node //结点结构体
{
char id;//数据域
Node* left; //左子树
Node* right;//右子树
};
Node *Tree=nullptr; //声明整棵树的根节点求树高的函数
int checkheight(Node* T) //求树高的函数
{
if(T==nullptr)
{
return 0;
}
else
{
if(checkheight(T->left)>checkheight(T->right)) //左右子树取最大高度加1
{
return checkheight(T->left)+1;
}
else
{
return checkheight(T->right)+1;
}
}
}下面来看调整平衡的四类函数。
首先是LL型调整，画图走一遍流程就清楚了。
Node* LL(Node* n1)
{
Node* n2=n1->left;
n1->left=n2->right;
n2->right=n1;
return n2;
}类似定义RR型
Node* RR(Node* n1)
{
Node* n2=n1->right;
n1->right=n2->left;
n2->left=n1;
return n2;
}LR型要先变成LL型，再做LL型调整
Node* LR(Node* n1)
{
Node* n2=n1->left;
Node* n3=n2->right;
n2->right=n3->left;
n3->left=n2;
n1->left=n3; //注意一定不要忘了这一步！！，要把调整到LL型的下面结点连接到当前根节点上
return LL(n1);
}注意一定不要忘了把调整到LL型的下面结点连接到当前根节点上，否则return回的LL调整树上会缺失结点。
类似定义RL型
Node* RL(Node* n1)
{
Node* n2=n1->right;
Node* n3=n2->left;
n2->left=n3->right;
n3->right=n2;
n1->right=n3;
return RR(n1);
}接下来定义结点插入函数，即构建树的函数
Node* insert(char c,Node* T)
{
if(T==nullptr) //若为根节点，就开始开辟结点存数据
{
T=new Node;
T->id=c;
T->left=nullptr;
T->right=nullptr;
}
else //不是一开始的根节点就直接连枝
{
if(c<T->id) //往左插
{
T->left=insert(c,T->left);
if(checkheight(T->left)-checkheight(T->right)>1) //不平衡要调整
{
if(c<T->left->id) //往左边的左边插了肯定是LL型
{
T=LL(T);
}
else{
T=LR(T); //否则LR型
}
}
}
else if(c>T->id) //往右插同理
{
T->right=insert(c,T->right);
if(checkheight(T->right)-checkheight(T->left)>1) //不平衡要调整
{
if(c>T->right->id) //往右边的右边插肯定是RR型
{
T=RR(T);
}
else{
T=RL(T); //否则RL型
}
}
}
}
return T; //返回建好树之后的树根结点
}接下来是输出函数
首先是前序、中序、后序输出函数
void Preorder(Node* T) //前序输出
{
if(T==nullptr)
{
return;
}
cout<<T->id;
Preorder(T->left);
Preorder(T->right);
}
void Inorder(Node* T) //中序输出
{
if(T==nullptr)
{
return;
}
Inorder(T->left);
cout<<T->id;
Inorder(T->right);
}
void Postorder(Node* T) //后序输出
{
if(T==nullptr)
{
return;
}
Postorder(T->left);
Postorder(T->right);
cout<<T->id;
}然后看一下旋转90度后的输出，即先右后中再左
void kongge(int l) //按层数输出空格的函数
{
for(int i=0;i<l;i++)
{
cout<<" ";
}
}
void Print(Node* T,int layer)
{
if(T==nullptr) return;
else
{
if(T->right) //先右
{
Print(T->right,layer+1);
}
kongge(layer); //后中
cout<<T->id<<endl;
if(T->left) //再左
{
Print(T->left,layer+1);
}
}
}最后是main函数
int main()
{
string s;
cin>>s;
for(int i=0;s[i];i++)
{
Tree=insert(s[i],Tree); //一定别忘了Tree=，要不拿不到根节点建树白建了
}
cout<<"Preorder: ";
Preorder(Tree);
cout<<endl;
cout<<"Inorder: ";
Inorder(Tree);
cout<<endl;
cout<<"Postorder: ";
Postorder(Tree);
cout<<endl;
cout<<"Tree:"<<endl;
Print(Tree,0);
return 0;
}注意一定别忘了Tree=，要不拿不到根节点建树白建了
完整代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct Node
{
char id;
Node* left;
Node* right;
};
Node *Tree=nullptr;
int checkheight(Node* T)
{
if(T==nullptr)
{
return 0;
}
else
{
if(checkheight(T->left)>checkheight(T->right))
{
return checkheight(T->left)+1;
}
else
{
return checkheight(T->right)+1;
}
}
}
Node* LL(Node* n1)
{
Node* n2=n1->left;
n1->left=n2->right;
n2->right=n1;
return n2;
}
Node* RR(Node* n1)
{
Node* n2=n1->right;
n1->right=n2->left;
n2->left=n1;
return n2;
}
Node* LR(Node* n1)
{
Node* n2=n1->left;
Node* n3=n2->right;
n2->right=n3->left;
n3->left=n2;
n1->left=n3;
return LL(n1);
}
Node* RL(Node* n1)
{
Node* n2=n1->right;
Node* n3=n2->left;
n2->left=n3->right;
n3->right=n2;
n1->right=n3;
return RR(n1);
}
Node* insert(char c,Node* T)
{
if(T==nullptr)
{
T=new Node;
T->id=c;
T->left=nullptr;
T->right=nullptr;
}
else
{
if(c<T->id)
{
T->left=insert(c,T->left);
if(checkheight(T->left)-checkheight(T->right)>1)
{
if(c<T->left->id)
{
T=LL(T);
}
else{
T=LR(T);
}
}
}
else if(c>T->id)
{
T->right=insert(c,T->right);
if(checkheight(T->right)-checkheight(T->left)>1)
{
if(c>T->right->id)
{
T=RR(T);
}
else{
T=RL(T);
}
}
}
}
return T;
}
void Preorder(Node* T)
{
if(T==nullptr)
{
return;
}
cout<<T->id;
Preorder(T->left);
Preorder(T->right);
}
void Inorder(Node* T)
{
if(T==nullptr)
{
return;
}
Inorder(T->left);
cout<<T->id;
Inorder(T->right);
}
void Postorder(Node* T)
{
if(T==nullptr)
{
return;
}
Postorder(T->left);
Postorder(T->right);
cout<<T->id;
}
void kongge(int l)
{
for(int i=0;i<l;i++)
{
cout<<" ";
}
}
void Print(Node* T,int layer)
{
if(T==nullptr) return;
else
{
if(T->right)
{
Print(T->right,layer+1);
}
kongge(layer);
cout<<T->id<<endl;
if(T->left)
{
Print(T->left,layer+1);
}
}
}
int main()
{
string s;
cin>>s;
for(int i=0;s[i];i++)
{
Tree=insert(s[i],Tree);
}
cout<<"Preorder: ";
Preorder(Tree);
cout<<endl;
cout<<"Inorder: ";
Inorder(Tree);
cout<<endl;
cout<<"Postorder: ";
Postorder(Tree);
cout<<endl;
cout<<"Tree:"<<endl;
Print(Tree,0);
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
20
0- 0
已为社区贡献5条内容
所有评论(0)