数据结构 day06

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)
	{
		printf("list malloc err\n");
		return -1;
	}
	// 初始化头尾指针
	p->head = NULL;
	p->tail = NULL;
	// 创建节点
	p->head = (node*)malloc(sizeof(node));
	if(p->head == NULL)
	{
		printf("node malloc err\n");
		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)
		{
			printf("pnewnode malloc err!!\n");
			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. 什么是树

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

7.1.2. 树的特性

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

7.1.3. 关于树的一些术语

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

7.2. 二叉树

7.2.1. 什么是二叉树

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

7.2.2. 二叉树的性质

1. 二叉树第k层上的节点最多有2^k-1个
2. 深度为k的二叉树最多有2^k-1个节点
3. 叶节点的数量比度数为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的节点，最下面一层的叶节点都是左孩子，那么就是完全二叉树
非完全二叉树：两种情况：

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

1. 当 i > 1 （不为根节点）时，有父节点。父节点编号为i/2;
2. 当2i <= n时，有左孩子，其编号为2i， 否则没有左孩子，是叶节点
3. 当 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

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

tree* p CreateBitTree(int n, int i) //i根节点的编号，n：节点数
{
	// 申请空间存放根节点
	tree* p = (tree*)malloc(sizeof(tree));
	// 容错判断
	if(p == NULL)
	{
		printf("BitTree malloc err!!\n");
		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;
}

2. 正序遍历二叉树，根左右

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);
}

3. 中序遍历，左根右

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);
}

4. 后序遍历，左右根

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