第九篇博客——数据结构二
二叉树
一般地，二叉树的定义：
struct TreeNode{
char data;
TreeNode *lc;
TreeNode *rc;
TreeNode(char c):data(c),lc(NULL),rc(NULL){}
};
//构造函数不可以少 深度优先遍历方法有前序、中序和后序之分。其中知道中序遍历次序和前/后序遍历次序是可以还原出二叉树的形状的。一般构建二叉树使用x序和#符号来建立。
例题1：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
先序序列 ABC##DE#G##F### 对应的二叉树如下：
#include <iostream>
#include<cstdio>
#include<string>
using namespace std;
struct TreeNode{
char data;
TreeNode* lc;
TreeNode* rc;
TreeNode(char c):data(c),lc(NULL),rc(NULL){}
};
/*
先序建立二叉🌲的思路和先序遍历的差不多，
先new TreeNode,然后build左子树和右子树，
返回的就是当下新建的root节点
*/
TreeNode* Build(int& position,string str){
char c=str[position++];
if(c=='#')
return NULL;
TreeNode* root=new TreeNode(c);
root->lc=Build(position, str);
root->rc=Build(position, str);
return root;
}
void InOrder(TreeNode* root){
if(root==NULL)
return;
InOrder(root->lc);
cout<<root->data<<' ';
InOrder(root->rc);
return;
}
int main(){
string str;
while(cin>>str){
int position=0;
TreeNode* root=Build(position,str);
InOrder(root);
cout<<endl;
}
return 0;
} 例题2：依据前序和中序序列推出后序序列。二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
输入描述：
两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
struct TreeNode{
char data;
TreeNode *lc;
TreeNode *rc;
TreeNode(char c):data(c),lc(NULL),rc(NULL){}
};
//build函数的第一个参数是前序，第二个参数是中序
TreeNode* Build(string str1,string str2){
//如果前序序列是0，那么就可以返回null
if(str1.size()==0)
return NULL;
//定义临时参数c=前序序列的第一个字符，也就是当前的root
char c=str1[0];
TreeNode *root=new TreeNode(c);
//寻找中序序列中的根root
int pos=str2.find(c);
//左子树的前序序列就是str1的1到pos；中序序列是str2的0到pos-1
//右子树就是从pos+1到末尾
root->lc=Build(str1.substr(1,pos), str2.substr(0,pos));
root->rc=Build(str1.substr(pos+1), str2.substr(pos+1));
//返回根root
return root;
}
int PostOrder(TreeNode* root){
if(root==NULL){
return 0;
}
PostOrder(root->lc);
PostOrder(root->rc);
cout<<root->data;
return 0;
}
int main(){
string str1,str2;
while(cin>>str1>>str2){
TreeNode* root=Build(str1,str2);
PostOrder(root);
cout<<endl;
}
return 0;
} 二叉排序树
二叉排序树的左子树和右子树都是二叉排序树，左子树一定小于根节点，右子树一定大于根节点。
练习：按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
#include<iostream>
#include<cstdio>
using namespace std;
struct TreeNode{
int data;
TreeNode *lc;
TreeNode* rc;
TreeNode(int x):data(x),lc(NULL),rc(NULL){}
};
TreeNode *Insert(TreeNode* root,int x,int father){
if(root==NULL){
root=new TreeNode(x);
cout<<father<<endl;
}
else if(x<root->data)
root->lc=Insert(root->lc, x, root->data);
else
root->rc=Insert(root->rc, x, root->data);
return root;
}
int main(){
int n;
while(cin>>n){
TreeNode* root=NULL;
for(int i=0;i<n;i++){
int x;
cin>>x;
root=Insert(root, x, -1);
}
}
return 0;
} 练习：输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。
#include <iostream>
#include <cstdio>
using namespace std;
struct node
{
int val;
node *left, *right;
node(int v):val(v),left(NULL),right(NULL){}
};
void insert(node *&root, int x)
{
if (root == NULL)
{
root = new node(x);
return;
}
if (root->val == x)
{
return;
}
if (x < root->val)
{
insert(root->left, x);
}
else
{
insert(root->right, x);
}
}
void preOrder(node *root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->val);//首先访问当前节点
preOrder(root->left);//然后访问左右节点
preOrder(root->right);
}
void inOrder(node *root)
{
if (root == NULL)
{
return;
}
inOrder(root->left);
printf("%d ", root->val);
inOrder(root->right);
}
void postOrder(node *root)
{
if (root == NULL)
{
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->val);
}
int main()
{
int n;
while (cin >> n)
{
node *root = NULL;
while (n--)
{
int x;
cin >> x;
insert(root, x);
}
preOrder(root);
printf("\n");
inOrder(root);
printf("\n");
postOrder(root);
printf("\n");
}
} 练习：二叉搜索树。判断两个序列是否是同一个二叉搜索树序列（浙大上机题）
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
struct node{
char val;
node *lc,*rc;
node(int c):val(c),lc(NULL),rc(NULL){}
};
bool flag;
node *insert(node *root,int x){
if(root==NULL){
root=new node(x);
return root;
}
if(root->val>x)
root->lc=insert(root->lc, x);
else
root->rc=insert(root->rc, x);
return root;
}
void check(node* root,node*judge){
if(root&&judge){
if(root->val!=judge->val)
flag=false;
check(root->lc, judge->lc);
check(root->rc, judge->rc);
}
else if(root||judge)
flag=false;
}
int main(){
int n;
while(cin>>n){
node *root=NULL;
string s;
cin>>s;
for(int i=0,len=s.length();i<len;i++)
root=insert(root, s[i]);
for(int i=0;i<n;i++){
flag=true;
node *judge=NULL;
cin>>s;
for(int i=0,len=s.length();i<len;i++)
judge=insert(judge, s[i]);
check(root,judge);
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
} 优先队列
在优先队列中每个元素都被赋予了优先级，每次访问元素的时候只能访问当前队列中优先级最高的元素。
定义一个优先队列的模版
priority_queue<Type, Container, Functional> name;
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式。
当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。
值得注意的地方，无论如何，每次访问元素的时候只能访问当前队列中优先级最高的元素，如果涉及到自定义的大小，比如用时最短的优先级最大，结构体自定义优先级等。这些情况下需要重载运算符。
//升序队列，小顶堆 priority_queue <int,vector<int>,greater<int> > q; //降序队列，大顶堆 priority_queue <int,vector<int>,less<int> >q; //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
优先队列的应用——哈夫曼树
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main(){
int n;
while(cin>>n){
priority_queue<int,vector<int>,greater<int>> myq;
while(n--){
int x;
cin>>x;
myq.push(x);
}
int ans=0;
while(1<myq.size()){
int a=myq.top();
myq.pop();
int b=myq.top();
myq.pop();
ans+=a+b;
myq.push(a+b);
}
cout<<ans<<endl;
}
return 0;
} 
京公网安备 11010502036488号