西安优秀的集团门户网站建设,李家沱网站建设,postgre wordpress,可以做网站的域名后缀目录
1.有关二叉树必须知道的几个基本概念
2.有关二叉树的基本操作
2.0有关元素的定义以及要进行的操作
2.1初始化和销毁操作
2.2插入操作以及上调操作
2.2.1插入操作以及上调操作的图解
2.2.2插入操作以及上调操作的代码
2.3删除根元素及其下调操作
2.3.2删除根元素及…目录
1.有关二叉树必须知道的几个基本概念
2.有关二叉树的基本操作
2.0有关元素的定义以及要进行的操作
2.1初始化和销毁操作
2.2插入操作以及上调操作
2.2.1插入操作以及上调操作的图解
2.2.2插入操作以及上调操作的代码
2.3删除根元素及其下调操作
2.3.2删除根元素及其下调操作的代码 1.有关二叉树必须知道的几个基本概念
完全二叉树前n-1层满最后一层未必满但自左向右是连续的
满二叉树相较于完全二叉树最后一层叶子是完全的
经实验可知数组是实现叉树这种数据结构的最好方式 由图可知
算孩子公式 leftchild 2parent 1 rightchild2parent2
算父亲公式 parentchild-1/2
2.有关二叉树的基本操作
2.0有关元素的定义以及要进行的操作
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP; void HPInit(HP* php);
void HPDestroy(HP*php);void HPPush(HP* php, HPDataType x);//插入操作
void Swap(HPDataType* px, HPDataType* py);
void AdjustUp(HPDataType* a, int child);//上调操作void HPPop(HP* php);//删除根操作
void AdjustDown(HPDataType* a, int n, int parent);//下调操作bool HPEmpty(HP* php);2.1初始化和销毁操作
void HPInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}void HPDestroy(HP* php)
{assert(php);free(php);php-a NULL;php-capacity 0;php-size 0;
} 2.2插入操作以及上调操作
2.2.1插入操作以及上调操作的图解 2.2.2插入操作以及上调操作的代码
void HPPush(HP* php, HPDataType x)//入
{assert(php);if (php-size php-capacity){size_t newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;//开辟空间并且插入到最后一个树叶AdjustUp(php-a, php-size-1);//将此被插入元素向上调整至合适位置
}void AdjustUp(HPDataType* a, int child)//将size-1传递给child,让child的初始指向被插入的新元素
{int parent (child - 1) / 2;while (child0)//一旦这个被插入元素到了根部(child0),停止!{if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;//将child移动到parent的位置parent (parent - 1) / 2;}else{break;}}
}void Swap(HPDataType* px, HPDataType* py)
{HPDataType temp;temp *px;*px *py;*py temp;
} 2.3删除根元素及其下调操作
2.3.1删除根元素及其下调操作的图解 2.3.2删除根元素及其下调操作的代码
void HPPop(HP* php)//删除根元素
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}//向下调整,就是将新的根元素下移至它的合适的位置
void AdjustDown(HPDataType* a, int n, int parent)
{int child (2 * parent) 1;while (childn)//nsize{if (a[child] a[child 1])//找小孩子,和小孩子交换,{//让最小的孩子成为新根才能保持小堆形态child;//如果左孩子不是小,那么右才是小}if(a[child]a[parent])//如果小孩子比父小,那么不符合小堆,需要交换{Swap(a[parent], a[child]);parent child;//更新父下标指向child (2 * parent) 1;//更新孩子下标指向}else{break;}}
} 3.研究笔记
