[数据结构与算法]树，图，堆的基本操作代码

树

二叉树顺序存储结构

#define MAX_TREE_SIZE 100  //二叉树最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE];   //0号单元存储根节点
SqBiTree bt;

二叉树的二叉链表存储表示

typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

二叉树的二叉线索存储表示

typedef enum PointerTag{Link,Thtead};//Link==0:指针.Thread==1:线索
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;//左右孩子指针
PointerTag LTag,RTag;//左右标志
}BiThrNode,*BiThrTree;

建立二叉链表

int CreateBiTree(BiTree &T){
cin<<ch;
if(ch=='');
T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))    exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}

树的孩子链表存储表示

typedef struct CTNode{//孩子结点
int child;
struct CTNode *next;
}ChildPtr;
typedef struct{
TElemType data;
ChildPtr firstchild;//孩子链表头指针
}CTBox;
typedef struct{
CTBox nodes[MAX_TREE_SIZE];
int n,r;//结点数和根的位置
)CTree;

图

图的数组（邻接矩阵）存储表示

#include <iostream>
using namespace std;
#define INFINITY INT_MAX//最大值 
#define MAX_VERTEX_NUM 20//最大顶点个数 
typedef enum{
	DG,DN,UDG,UDN//{有向图，又向网，无向图，无向网} 
}GraphKind;
typedef struct ArcCell{
	VRType adj;//VRType是顶点关系模型，对无权图，用0或1
	               //表示相邻否，对带权图，则为权值类型 
	InfoType *info;//该弧相关信息的指针 
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	VertexType vexs[MAX_VERTEX_NUM];//顶点向量 
	AdjMatrix arcs;//邻接矩阵 
	int vexnum,arcnum;//图的当前顶点数和弧数 
	GraphKind kind;//图的种类标志 
}MGraph;

图的邻接表存储表示

#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;//该弧所指向的顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
InfoType *info;//该弧相关信息的指针
}ArcNode; 
typedef struct VNode{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;//图的当前顶点数和弧数
int kind;//图的种类标志
}ALGraph;

邻接矩阵构造图G

int CreateGraph(MGraph &G){//采用数组表示法，构造图G
cin>>G.kind;
swich(G.kind){
case DG;return GreateDG(G);//构造有向图G
case DN;return CreateDN(G);//构造有向网G
case UDG;return CreateUDG(G);//构造无向图G
case UDN;return CreateUDN(G);//构造五向网G
default:return ERROR;
}

}

堆

基本数组定义

int n; //数组元素的个数
int heap[100005];  //堆数组

向下调整

//对输入的heap数组在[low, high]范围内向下调整，调整为最小堆，即小的数在最上面 
void downHeap(int low, int high){ //i初始化为欲调整节点，j为其左孩子 
    int i = low, j = i * 2;  //如果还存在孩子节点则一直比较并调整 
    while(j <= high){  //如果右孩子存在且值比左孩子还小，那么就应该将右孩子向上调整 
        if(j + 1 <= high && heap[j+1] < heap[j])
            j = j + 1; //当孩子的值比欲调整节点大时，则进行交换，保证小的数在上面 
        if(heap[j] < heap[i]){
            swap(heap[j], heap[i]);    //继续向下调整 
            i = j;
            j = j * 2;
        }  //如果欲调整节点的值已经比孩子都小则结束调整 
        else
            break;
    }
}

建堆操作

//建堆操作 
void createHeap(){
    //建堆从最后一个还具有孩子的节点开始，依次往前遍历到根结点，到最后便建立了最小堆 
    for(int i = n / 2; i >= 1; i--){
        downHeap(i, n);
    }
}

删除堆顶元素

//删除堆顶元素 
void deleteHeap(){  //将堆最后一个元素覆盖堆顶元素，再将元素个数n简易 
    heap[1] = heap[n--];  //从堆顶到堆最后进行一次向下调整，保证删除后仍是最小堆 
    downHeap(1, n);
} 

插入一个元素在堆里

//对heap中[low，high]范围内进行向上调整 
void upHeap(int low, int high)    //i初始化为欲调整节点，j为其父亲节点 
    int i = high, j = i / 2; //当未到达根结点时则继续操作 
    while(j >= low){    //如果父亲节点仍然比欲调整节点的值大则继续向上，因为需要调整为最小堆 
        if(heap[j] > heap[i]){
            swap(heap[i], heap[j]);
            i = j;
            j = i / 2;
        }   //比父亲节点值大，则达到退出条件 
        else
            break;
    }
}
//插入一个元素，利用向上调整方法 
void insert(int x){   //将新插入的元素放到堆数组的最后，并将元素个数加1 
    heap[++n] = x;  //放入后进行一次向上调整 
    upHeap(1, n);
}

堆排序

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>


using namespace std;
int n;
int heap[100005]; 


//对输入的heap数组在[low, high]范围内向下调整，调整为最小堆，即小的数在最上面 
void downHeap(int low, int high){
    //i初始化为欲调整节点，j为其左孩子 
    int i = low, j = i * 2;
    //如果还存在孩子节点则一直比较并调整 
    while(j <= high){
        //如果右孩子存在且值比左孩子还小，那么就应该将右孩子向上调整 
        if(j + 1 <= high && heap[j+1] < heap[j])
            j = j + 1;
        //当孩子的值比欲调整节点大时，则进行交换，保证小的数在上面 
        if(heap[j] < heap[i]){
            swap(heap[j], heap[i]);
            //继续向下调整 
            i = j;
            j = j * 2;
        }
        //如果欲调整节点的值已经比孩子都小则结束调整 
        else
            break;
    }
}
//建堆操作 
void createHeap(){
    //建堆从最后一个还具有孩子的节点开始，依次往前遍历到根结点，到最后便建立了最小堆 
    for(int i = n / 2; i >= 1; i--){
        downHeap(i, n);
    }
}
//堆排序操作 
void heapSort(){
    //首先建立初始最小堆 
    createHeap();
    //从后遍历每一个元素，每次将最小元素放入到i位置，这样第一次最小放到n
    //第二次的最小则放入到n-1，第三次则会放入到n-2...... 
    for(int i = n; i > 1; i--){
        swap(heap[i], heap[1]);
        downHeap(1, i-1);
    }
}

//10
//2 8 4 6 1 10 7 3 5 9
int main() {
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &heap[i]);
        heapSort();
        for(int i = n; i >= 1; i--)
            printf("%d ", heap[i]);
    }
    return 0;
}