【数据结构】树
二叉树
二叉树的存储结构
struct node{
typename data;
node * lchild;
node * rchild;
};
//函数：生成一个新的结点
node * newNode(int v){ //v为权值
node* Node=new node;
Node->data=v;
Node->lchild=Node->rchild=NULL;
return Node;
}
//函数：查找二叉树结点
node* search(node* root,int x){ //查找权值为x的结点，如果没找到，返回空
if(root==NULL){
return;
}
if(root->data==x){
return root;
}
search(root->lchild,x);
search(root->rchild,x);
}
//函数：插入二叉树结点
void insert(node* &root,int x){
if(root==NULL){
root=newNode(x);
return; //加&，此操作修改原变量；
}
if(root-data<x)
insert(root->rchild,x);
else
insert(root->lchild,x);
}
//创建二叉树
node* Creat(int data[],int n){
node* root=NULL;
for(int i=0;i<n;++i){
insert(root,data[i]);
}
return root;
}
二叉树的四种遍历方式
//先序遍历
void preOrder(node * root){
if(root==NULL){
return;
}
visit(root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
//中序遍历
void inorder(node * root){
if(root==NULL)
return;
inorder(root->lchild);
visit(root->data);
inorder(root->rchild);
}
//后序遍历
void postOrder(node * root){
if(root==NULL){
return;
}
postOrder(root->lchild);
postOrder(root->rchild);
visit(root->data);
}
//层序遍历
void levelOrder(node *root){
queue<node*>q; //存放地址，可修改
q.push(root);
while(!q.empty()){
node* now=q.front();
q.pop();
visit(now->data);
if(now->lchild!=NULL) q.push(now->lchild);
if(now->rchild!=NULL) q.push(now->rchild);
}
}
树的遍历
树的存储结构
//静态写法：用数组下标代替孩子结点地址
struct node{
typename data; //存放数据
vector<int> child; //存放所有孩子结点的下标
}Node[maxn]; //结点数组
树的遍历方式
//先根遍历
void preOrder(int root){
visit(Node[root].data);
for(int i=0;i<Node[root].child.size();++i){
preOrder(Node[root].child[i]);
}
}
//树的层序遍历
void levelOrder(int root){
queue<int>q;
q.push(root);
while(!q.empty()){
int front=q.front();
visit(front);
q.pop();
for(int i=0;i<Node[front].child.size();++i){
int child=Node[front].child[i];
q.push(child);
}
}
}
二叉查找树BST(binary search tree)
BST的基本操作
//函数：查找
void search(node* root,int x){
if(root===NULL){
cout<<"null";
return;
}
if(x==root->data){
cout<<root->data;
}else if(x<root->data){
search(root->lchild,x);
}else{
search(root->rchild,x);
}
}
//函数：插入
void insert(node* &root,int x){
if(root==NULL){
root=newNode(x);
return;
}
if(x==root->data){
return;
}else if(x<root->data){
insert(root->lchild,x);
}else{
insert(root->rchild,x);
}
}
//函数：建立BST
node* creat(int data[],int n){
node* root=NULL;
for(int i=0;i<n;++i){
insert(root,data[i]);
}
return root;
}
//函数：删除权值为x的结点
node* findMax(node* root){ //寻找以root为根结点的树中的最大权值结点
while(root->rchild!=NULL){
root=root->rchild;
}
return root;
}
node* findMin(node* root){ //寻找以root为根结点的树中的最小权值结点
while(root->lchild!=NULL){
root=root->lchild;
}
return root;
}
void deleteNode(node* &root,int x){
if(root==NULL) return;
if(root->data==x){
if(root->lchild==NULL&&root->rchild==NULL){
root=NULL;
}else if(root->lchild!=NULL){
node* pre=findMax(root->lchild);
root->data=pre->data;
deleteNode(root->lchild,pre->data);
}else{
node* next=findMin(root->rchild);
root->data=next->data;
deleteNode(root->rchild,next->data);
}
}else if(root->data<x){
deleteNode(root->lchild,x);
}else{
deleteNode(root->rchild,x);
}
}
//BST性质：中序遍历，得到有序数列。
二叉平衡树(AVL)
二叉平衡树的定义
struct node{
int v,height; //权值，结点高度
node * lchild;
node * rchild;
};
生成一个新结点
node* newNode(int v){
node* Node=new node;
Node->v=v;
Node->height=1;
Node->lchild=Node->rchild=NULL;
return Node;
}
函数：获取root子树的当前高度
int getHeight(node* root){
if(root==NULL)
return 0;
else
return root->height;
}
函数：计算结点root的平衡因子
int getBalanceFactor(node* root){
return getHeight(root->lchild)-getHeight(root->rchild);
}
函数：更新结点root的高度
void updataHeight(node* root){
root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}
二叉平衡树的基本操作
//查找
void search(node* root,int x){
if(root==NULL){
cout<<"not find";
return;
}
if(root->data==x){
cout<<root->data;
}else if(x<root->data){
search(root->rchild,x);
}else{
search(root->lchild,x);
}
}
//左旋(Left Rotation)(向左旋转)
void L(node* &root){
node* temp=root->rchild;
root->right=temp->lchld;
temp->lchild=root;
updataHeight(root);
updataHeight(temp);
root=temp;
}
//右旋(Right Rotation)(向右旋转)
void R(node* &root){
node* temp=root->lchild;
root->lchild=temp->rchild;
temp->rchild=root;
updataHeight(root);
updataHeight(temp);
root=temp;
}
二叉平衡树插入权值为v的结点,并做调整
void insert(node* &root,int v){
if(root==NULL){
root=newNode(v);
return;
}
if(v<root->v){
insert(root->lchild,v); //插入到左子树
updataHeight(root); //更新树高
if(getBalanceFactor(root)==2){
if(getBalanceFactor(root->lchild)==1) //LL型，左高右低
R(root);
else if(getBalanceFactor(root->lchild)==-1){ //LR型
L(root->lchild);
R(root);
}
}
}else{
insert(root->rchild,v);
updataHeight(root);
if(getBalanceFactor(root)==-2){
if(getBalanceFactor(root->rchild)==-1) //RR型
L(root);
else if(getBalanceFactor(root->rchild)==1){ //RL型
R(root->rchild);
L(root);
}
}
}
}
建立AVL树
node* creat(int data[],int n){
node* root=NULL;
for(int i=0;i<n;++i){
insert(,root,data[i]);
}
return root;
}
并查集
并查集的实现，其实就是用一个数组。对同一个集合来说只存在一个跟结点，且将其作为所属集合的标识。
并查集的基本操作：初始化，查找，合并
//初始化
for(int i=0;i<N;i++){
father[i]=i;
}
//查找：返回元素x所在集合的根结点
int findFather(int x){
while(x!=father[x]){
x=father[x];
}
return x;
}
//合并
void union(int a,int b){
int fa=findFather(a);
int fb=findFather(b);
if(fa!=fb){
father[fa]=fb;
}
}
路径压缩
int findFather(int x){
int a=x;
while(x!=father[x]){
x=father[x];
}
//此时，x存放的是根结点
//路径压缩
while(a!=father[a]){
int tmp=a;
a=father[a];
father[tmp]=x;
}
//返回查找结果：根结点
return x;
}