数据结构 day06

6. 双向链表
- 6.3. 双向循环链表
7. 树 tree
- 7.1. 特点
- - 7.1.1. 什么是树
  - 7.1.2. 树的特性
  - 7.1.3. 关于树的一些术语
- 7.2. 二叉树
- - 7.2.1. 什么是二叉树
  - 7.2.2. 二叉树的性质
  - 7.2.3. 满二叉树和完全二叉树的区别
  - 7.2.4. 二叉树的遍历（画图）
  - 7.2.5. 二叉树的顺序存储结构
  - 7.2.6. 二叉树的链式存储结构

6. 双向链表

6.3. 双向循环链表

用双向循环链表实现约瑟夫环

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
// 定义结构体，一个节点的结构体，一个头尾指针的结构体
typedef struct node
{
	datatype data;
	struct node *prior;
	struct node *next;
}node;
typedef struct double_list
{
	struct node *head;
	struct node *tail;
}list;
// 主函数
int main()
{
	int i = 0;	// 计数
	int all = 0;	// 总人数
	int start = 0;	// 开始报数的人
	int kill = 0;	// 死亡数字
	node *pdel = NULL;	// 用于杀死死者
	node *h = NULL;	// 指向正在报数的人
	node *pnew = NULL:	// 指向新创建的人
	printf("输入总人数，死亡数字，开始报数的人的编号：");
	scanf("%d %d %d", &all, &kill, &start);
	// 创建头尾指针
	list *p = (list *)malloc(sizeof(list));
	if(p == NULL)
	{
		perror("list malloc err");
		return -1;
	}
	// 初始化头尾指针
	p->head = NULL;
	p->tail = NULL;
	// 创建节点
	p->head = (node*)malloc(sizeof(node));
	if(p->head == NULL)
	{
		perror("node malloc err");
		free(p);
		return -1;
	}
	p->tail = p->head;
	// 初始化节点
	p->head->prior = NULL;
	p->head->next = NULL;
	p->head->data = 1;
	// 循环创建所有的人
	for(i = 2; i <= all; i++)
	{
		pnew = (node*)malloc(sizeof(node));
		if(pnew == NULL)
		{
			perror("pnewnode malloc err!!");
			return -1;
		}
		// 初始化pnew
		pnew->next = NULL;
		pnew->prior = NULL;
		pnew->data = i;
		// 建立链接
		pnew->prior = p->tail;
		p->tail->next = pnew;
		// 移动尾指针
		p->tail = p->tail->next;
	}
	// 首尾相连
	p->tail->next = p->head;
	p->head->prior = p->tail;
	// h指向开始报数的人
	h = p->head;
	while(h->data != start)
		h = h->next;
	// 开始报数，报到死亡数字之后杀人
	while(h != h->next)
	{
		for(i = 1; i <= kill; i++)
		{
			h = h->next;
		}
		pdel = h;
		h = h->next;
		printf("kill %d\n", pdel->data);
		// 杀死pdel
		pdel->prior->next = pdel->next;
		pdel->next->prior = pdel->prior;
		free(pdel);
		pdel = NULL;
	}
	printf("Survivor is %d", h->data);
	// 释放h
	free(h);
	h = NULL;
}

7. 树 tree

7.1. 特点

7.1.1. 什么是树

存在一个根节点（root）
其余节点可以分为若干子树

7.1.2. 树的特性

层次关系，一对多，
每个节点最多只有一个前驱，根节点无前驱
每个节点可以有多个后继，叶节点无后继

7.1.3. 关于树的一些术语

度数：节点的子树个数，节点有几个孩子
树度数：整个树中节点最大的度数
叶节点或终端节点，度数为0的节点，最末端的节点
分支节点：度数不为0，有孩子的节点
内部节点：除根节点以外的分支节点
节点层次：根节点到叶节点之间的个数，称为层数，根节点的层数是1
树的深度又叫树的高度：最大的节点层次

7.2. 二叉树

7.2.1. 什么是二叉树

每个节点最多只有两个孩子，分为左孩子和右孩子。由一个根节点和两个互不相交的左子树和右子树组成。二叉树严格区分左右孩子，哪怕只有一个孩子也要分左右。

7.2.2. 二叉树的性质

二叉树第k层上的节点最多有2^k-1个
深度为k的二叉树最多有2^k-1个节点
叶节点的数量比度数为2的节点的数量多1
计算
度数为0：n₀
总节点数为各类节点之和：n = n₀ + n₁ + n₂
总节点数为所有子节点数加一：n = 1n₁ + 2n₂ + 1
0 = n₂ + 1 - n₀
n₀ = n₂ + 1

7.2.3. 满二叉树和完全二叉树的区别

满二叉树：深度为k时节点为2^k-1
完全二叉树：只有最下面两层有度数小于2的节点，最下面一层的叶节点都是左孩子，那么就是完全二叉树
非完全二叉树：两种情况：

除最下面两层外还有别的地方有度数不为2的二叉树
只有最下面两层有度数不为2的二叉树，最下面一层存在右孩子

7.2.4. 二叉树的遍历（画图）

前序：根左右，先找根，再找左孩子
中序：左根右，先找左孩子，再找根，再找右孩子
后序：左右根

每个节点左边画圈，沿着最左边划线，沿线顺序就是前序的遍历顺序

练习：
已知遍历结果如下，试画出对应的二叉树。
前序： A B C E H F I J D G K
中序： A H E C I F J B D K G
提示：用前序确定根节点，然后用中序找到根节点然后再找左右子。

7.2.5. 二叉树的顺序存储结构

完全二叉树的节点编号方法为从上到下，从左到右，根节点为1号节点
公式：完全二叉树的节点数为n，某节点编号为i

当 i > 1 （不为根节点）时，有父节点。父节点编号为i/2;
当2i <= n时，有左孩子，其编号为2i，否则没有左孩子，是叶节点
当 2i <= n 时，有右孩子，其编号为 2i + 1，否则没有右孩子

n个节点可以用n+1个元素的数组顺序存储，节点号和数组下标一一对应，下标为0的位置不用，非完全二叉树虚构节点组成完全二叉树之后存储，会造成空间的浪费

7.2.6. 二叉树的链式存储结构

用链表实现，基于完全二叉树规律创建二叉树，按照完全二叉树的编号方法，从上到下，从左到右

1. 头文件 tree.h

#ifndef __TREE_H__
#define __TREE_H__

typedef struct tree_t
{
	int data;
	int id;
	tree_t* lchild;
	tree_t* rchild;
}tree;

// 1. 创建二叉树
tree* CreateBitTree(int n, int i);
// 2. 前序遍历
void PreOrder(tree* p);
// 3. 中序遍历
void InOrder(tree* p);
// 4. 后序遍历
void PostOrder(tree* p);
#endif

创建二叉树，用递归函数创建。

tree* p CreateBitTree(int n, int i) //i根节点的编号，n：节点数
{
	// 申请空间存放根节点
	tree* p = (tree*)malloc(sizeof(tree));
	// 容错判断
	if(p == NULL)
	{
		perror("BitTree malloc err!!");
		return NULL;
	}
	
	// 初始化
	p->id = i;
	p->data = i;
	if(2*i <= n)
		p->lchild = CreateBitTree(n, 2*i);
	else
		p->lchild = NULL;
	if(2*i+1 <= n)
		p->rchild = CreateBitTree(n, 2*i+1);
	else
		p->rchild = NULL;
	
	return p;
}

正序遍历二叉树，根左右

void PreOrder(tree* p)
{
	if(p == NULL)
		return;
	// 根节点输出
	printf("%-4d", p->data);
	
	// 查看左孩子
	if(p->lchild != NULL)
		PreOrder(p->lchild);
	
	// 查看右孩子
	if(p->rchild != NULL)
		PreOrder(p->rchild);
}

中序遍历，左根右

void InOrder(tree* p)
{
	if(p == NULL)
		return;
	if(p->lchild != NULL)
		InOrder(p->lchild);
	printf("%-4d", p->data);
	if(p->rchild != NULL)
		InOrder(p->rchild);
}

后序遍历，左右根

void PostOrder(tree* p)
{
	if(p->lchild !=  NULL)
		PostOrder(p->lchild);
	if(p->rchild != NULL)
		PostOrder(p->rchild);
	printf("%-4d", p->data);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/971165.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！