数据结构-二叉树（1）_代码007(未授权)

树是一种非线性的数据结构，它是由n（n&g t;=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6.
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点.
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G…等节点为分支节点.
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点.
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点.
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点.
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6.
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4.
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点.
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先.
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙.
森林：由m（m>0）棵互不相交的树的集合称为森林；

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法.

typedef int DataType;
struct Node
{
   struct Node* _firstChild1; // 第一个孩子结点
   struct Node* _pNextBrother; // 指向其下一个兄弟结点
   DataType _data; // 结点中的数据域
};

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* php)
{
	assert(php);

	php-&gt;a = NULL;
	php-&gt;size = 0;
	php-&gt;capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	// 扩容
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&amp;a[child], &amp;a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPrint(HP* php)
{
	assert(php);

	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("n");
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child<n)
	{
		//找小的孩子
		if (child + 1 < n &amp;&amp; a[child] > a[child + 1])
		{
			child = child + 1;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//继续往下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(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);
}


HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

树是结点节点

1.树概念及结构

1.1树的概念

1.2 树的相关 概念

1.3 树的表示

2.二叉树 概念及结构

2.1概念

2.2 特殊的二叉树：

2.3二叉树的性质

2.4 二叉树的存储 结构

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

3.2 堆的概念及结构

3.3 堆的实现

3.3.1堆的定义

3.3.2堆的初始化

3.3.3堆的销毁

3.3.4插入 数据

3.3.5向上调整数据

3.3.6打印堆

3.3.7向下调整数据

3.3.8删除数据

3.3.9取根节点数据

3.3.10判断堆是否 为空

发表回复取消回复