189 8069 5689

数据结构——使用二叉树-创新互联

目录

创新互联是一家集网站建设,太和企业网站建设,太和品牌网站建设,网站定制,太和网站建设报价,网络营销,网络优化,太和网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

1、二叉树的实现方式

顺序结构

链式结构

二、数组二叉树

顺序结构的实现

堆的实现

堆的插入和删除

三、链式二叉树

1、二叉树的实现方式

前面了解了二叉树的一些性质，现在我们将用代码实现二叉树。二叉树的分叉让人第一印象就是用链式结构来存储，但数组的顺序结构也能用来存储二叉树，下面就是两种方式的区别。

顺序结构

  顺序结构是用数组来存储，但是一般只储存完全二叉树，因为完全二叉树不会有空间的浪费

链式结构

  链式结构就很好理解了，每一个节点有三块区域，分别是左子树、右子树和数据。

二、数组二叉树 顺序结构的实现

  前面说了，顺序结构一般存储完全二叉树，现实中我们通常把堆存放在数组里，下面就简单的介绍一下堆

堆：堆一种完全二叉树。堆分为两类，大堆和小堆。大堆是每个父节点的数据都大于或等于两个子节点，小堆是每个父节点都小于或等于两个子节点

注意：只要父节点大于等于或小于等于两个子节点就可以，和父节点的兄弟节点没关系

堆的代码结构：

typedef int HPDataType;//数据类型
typedef struct Heap
{
	HPDataType* a;//一个数组
	int size;//当前数据个数
	int capacity;//数组最多能存储的数据个数
}
堆的实现

  想要建堆，先要学会堆的向下调整。向下调整有一个前提，左右子树必须都是堆，才可以向下调整。

向下调整的思想(以小堆为例)

  1. 从根结点处开始，选出左右孩子中值较小的孩子。这个根节点不一定是整棵树的根节点，也可以是子树的根节点，只要保证该节点的两棵子树都是堆就可以调整
  2. 让较小的子节点和父节点比较，若子节点比父节点还小，则该子节点与其父节点的位置进行交换。然后一直重复这个过程。
  3. 当遇到两个节点都比自己大的时候或者自己是叶子节点的时候调整已经完成

向下调整的代码：

void HPJestDown(HPDataType* a, int size, int parent)
{
	assert(a);    
	int child = parent * 2 + 1;//找到第一个子节点    
	while (child< size)//子节点不能越界，越界说明该节点是叶子节点
	{
        //第一个子节点和第二个子节点比较
        //这里是小堆所以要找子节点中最小的和父节点比较
        //并且还要判断一下这个父节点有没有右子节点防止越界
		if (child + 1< size && a[child]< a[child + 1])
		{
			child++;
		}
        //最小的子节点比父亲小则交换
		if (a[parent]< a[child])
		{
			Swap(&a[parent], &a[child]);//一个交换数据的函数
			parent = child;//从被交换的子节点开始继续向下排序
			child = child * 2 + 1;//找到这个子节点的子节点
		}
		else//不符合条件就跳出循环，调整完毕
		{
			return;
		}
	}
}

但是在创建堆时，根节点的左右子树都不是堆，我们可以把所有叶子节点看成一个堆，从他们的父节点开始调整，一直调整到根节点，最后就是一个堆了。      

我们发现，根节点下标*2+1是左子节点下标，根节点下标*2+2是右子节点下标，但是左子节点下标减1再除以2和右子节点减1再除以2都是父节点的下标，所以我们可以这样写

void HeapCreate(Heap* hp, HPDataType* a, int size)
{
	assert(a);
	hp->size = hp->capacity = size;
	HPDataType* newcapacity = (HPDataType*)malloc(sizeof(HPDataType) * size);
	if (newcapacity == NULL)
	{
		perror("realloc file");
	}
	hp->a = newcapacity;
	memcpy(hp->a, a,sizeof(a)*size);

    //先找到最后一个叶子节点的父节点
    //因为size是数据个数，对应下标要先减1，再减1后除以2
	int i = (size - 2) / 2;
    //从这个节点从后往前全部调整一边，调整完堆就建好了
	while (i >=0)
	{
		HPJestDown(hp->a, hp->size, i);
		i--;
	}
}
堆的插入和删除

插入数据

当我们有新的数据要插入时，我们必须把数据放在最后，一是如果放在最前面，数组内所有的数据都要挪动一下，二是我们辛辛苦苦建的堆会被破坏掉。放在最后再向上调整，向上调整的思想和向下调整类似，保证上面是堆，符合条件交换，直到不符合条件或到根节点停止。这里直接放代码和图片了

//这个是向上排序
void HPJestUP(HPDataType* a, int child)
{
	assert(a);
    //因为是向上调整，所以要找父节点
	int parent = (child - 1) / 2;
    //等于0就是根节点不需要再调整了
	while (child != 0)
	{
        
		if (a[parent]< a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入数据
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
    //判断是否需要扩容
	if (hp->size == hp->capacity)
	{
		hp->capacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* newcapacity = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * hp->capacity);
		if (newcapacity == NULL)
		{
			perror("realloc file");
		}
		hp->a = newcapacity;
	}
    //直接放在最后面
	hp->a[hp->size] = x;
	hp->size++;
	HPJestUP(hp->a, hp->size - 1);
}

删除数据

  删除堆的数据一般是删除堆顶的数据，删除其他地方的数据没有意义。在删除数据是，若是把后面所有的数据都往前挪一格，那我们的堆就被破坏掉了。我们可以把最后一个节点和堆顶交换一下，数据个数减1在把新的堆顶向下调整，这样我们堆既没有被破坏，也把堆顶删除了，在插入数据时会把后面的数据覆盖掉。

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
    //只需要把第一个和最后一个交换就可以了
    //如果只有一个数据的话，那就是自己交换了
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	HPJestDown(hp->a, hp->size, 0);
}

我们可以发现，每次删除都会把堆中最小的数据放在最后面。在不插入新的数据情况下，一直删下去我们数组中的数据变成有序的了。但是删除的话，堆的有效元素个数会变，在插入数据时会被覆盖。但我们可以利用这个思路来完成排序，拿到一个数组时，先将其建堆，再用这个思路排序。

注意： 升序要建大堆，降序要建小堆

void HeapSort(int* a, int n)
{
	assert(a);
	int i = (n - 2) / 2;
    //这里是建堆
	while (i >= 0)
	{
		HPJestDown(a, n, i);
		i--;
	}
	i = n - 1;
    //头尾交换，然后再向下调整
	while (i >= 0)
	{
		Swap(&a[0], &a[i]);
		HPJestDown(a, i, 0);
		i--;
	}
}
三、链式二叉树

  关于链式二叉树，我们先学习对链式二叉树的四种遍历方式。在这之前，我们先看一下二叉树的结构

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;//数据域
	struct BinaryTreeNode* left;//左子树
	struct BinaryTreeNode* right;//右子树
}BTNode;
  • 前序遍历：先访问根节点，再访问左子树，最后访问右子树。
  • 中序遍历：先访问左子树，再访问根节点，最后访问右子树。
  • 后序遍历：先访问左子树，再访问右子树，最后访问根节点。
  • 层序遍历：首先访问第一层的根结点，然后从左到右访问第2层上的节点，接着访问第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

前面三种我们可以用递归来完成，实现方式非常简单

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	printf("%d ", root->data);//先访问自己
	BinaryTreePrevOrder(root->left);//再访问左子树
	BinaryTreePrevOrder(root->right);//最后访问右子树
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	BinaryTreeInOrder(root->left);//再访问左子树
	printf("%d ", root->data);//先访问自己
	BinaryTreeInOrder(root->right);//最后访问右子树
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	BinaryTreePostOrder(root->left);//再访问左子树
	BinaryTreePostOrder(root->right);//最后访问右子树
	printf("%d ", root->data);//先访问自己
}

最后一个层序遍历，我们要借助队列来实现。在访问一个节点时，把它的两个子树放进去。

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue* queue = QueueCreate();//创建一个队列
	if (root)
	{
		QueuePush(queue, root);//树不为空时入队
	}

	while (!QueueEmpty(queue))
	{
        //取出队列里一个节点
		BTNode* p = QueueFront(queue);
		printf("%d ", p->data);
		QueuePop(queue);
        //左子树不为空入队
		if (p->left)
		{
			QueuePush(queue, p->left);
		}
        //右子树不为空入队
		if (p->right)
		{
			QueuePush(queue, p->right);
		}
	}

	printf("\n");
	QueueDestory(queue);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


分享文章：数据结构——使用二叉树-创新互联
本文链接：http://cdxtjz.cn/article/dcjpjd.html

其他资讯