树形结构-数据结构

一、基本知识

1. 树：一对多的树形结构
2. 顶层的结点：称为根节点
3. 叶子结点（终端结点）：最外围的结点，只有前驱结点，没有后继结点的结点
4. ，其结点的度是0
5. 分支结点：分支点是描述数据结构中的从根部出发（对有向图而言）有入度和出度的节点，（对无向图而言）不属于 叶子节点 的节点。 出度不为0的结点称为分枝点。 在 完全m叉树 中，如树叶数为t，分支点数为i，则（m-1）i=t-1。注意实际上就是除了根节点和叶子结点之外的都是。
6. 度

• 深度：层数
• 广度：（默认为度），结点的度最大的结点的度即为树的广度。
• 结点的度：子节点的个数。（当前结点出发）

二、二叉树

结点的度数不能超过2，或者说度为2的树称为2

满二叉树

在不增加层数的前提下，增加结点，不能增加的树称为满二叉树

每一层的度数2

满二叉树的计算

1. 第K层节点个数：2 ^(k-1)
2. K层满二叉树：总共节点个数：2^(k) - 1
3. 高度计算：满二叉树的高度可以通过节点数和2的幂次关系计算得到。对于有N个节点的满二叉树，其高度H可以表示为H = log2(N+1)。
4. 查找叶子节点：在满二叉树中，叶子节点的位置可以通过深度和2的幂次关系计算得到。对于深度为d的满二叉树，第i个叶子节点的位置可以表示为i = 2^(d-1)。
5. 查找非叶子节点：在满二叉树中，非叶子节点的位置可以通过其子节点的位置计算得到。对于第i个非叶子节点，其左子节点的位置为2i，右子节点的位置为2i+1。

完全二叉树

在满二叉树的基础上，要删除结点的话，只能从右至左，从上到下，进行连续按照顺序删除，插入的顺序也是如此。（也就是说，一层一层来，如果上一层没有插完，只能在上面插入）

注意

满二叉树一定是完全二叉树

完全二叉树不一定是满二叉树

三、二叉树的遍历

1、前序遍历

先遍历根节点，再按照前序结点遍历左子树，右子树

顺序：根、左、右，一层一层往进拔清

2、中序遍历

先遍历左子树，再按照前序结点遍历根节点，右子树

顺序：左、根、右

3、后序遍历

先遍历左子树，再按照前序结点遍历右子树，根节点

顺序：左、右、根

前三种称为深度优先

4、层序遍历（广度优先）

从上至下，从左至右，逐层遍历

把每一层按照从左到右的顺序进行排列

自我理解

实现，就是增加一个队列，将结点加入，加入之后，再将其的左右子节点的数据。

也就是说一层一层进行入队，只要根结点不为空，那么我们就可以进行打印，出栈结点，出完之后再将其左右结点入队，再循环往复进行操作

注意

• 只知道其种一个遍历结果没有办法进行还原
• 已知前序+中序，可以唯一的还原一棵二叉树
• 后序+中序，可以唯一的还原一棵二叉树
• 判空并不代表出错方式，而是每一条分支结束的时候的条件
• 后序最后出现的一定是根
• 确定一个二叉树实际上就是根据我们结点的出现的特点，两两配合进行创建出唯一一棵确定的二叉树

四、二叉树的算法

1、创建二叉树

char tree[] = {"ABEH###G##CF#D##I##"};
int idx = 0;

TNode_t *create_bin_tree()
{
	TDataType data = tree[idx++];
	if (data == '#')
	{
		return NULL;
	}
	
	TNode_t *pnode = malloc(sizeof(TNode_t));
	if (NULL == pnode)
	{
		perror("fail malloc");
		return NULL;
	}
	pnode->data = data;
	pnode->pl = create_bin_tree();
	pnode->pr = create_bin_tree();
	
	return pnode;
}

2、前序遍历

void pre_order(TNode_t *proot)
{
	if (NULL == proot)
	{
		return;
	}
	printf("%c", proot->data);
	pre_order(proot->pl);
	pre_order(proot->pr);
}

3、中序遍历

void mid_order(TNode_t *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	mid_order(proot->pl);
	printf("%c", proot->data);
	mid_order(proot->pr);
}

4、后序遍历

void pos_order(TNode_t *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	pos_order(proot->pl);
	pos_order(proot->pr);
	printf("%c", proot->data);
}

5、层序遍历

void layer_order(TNode_t *proot)
{
	QDataType outdata;
	Queue_t *pque = create_queue();	
	if (NULL == pque)
	{
		printf("fail create_queue\n");
		return ;
	}

	push_queue(pque, proot);

	while (!is_empty_queue(pque))
	{
		pop_queue(pque, &outdata);
		printf("%c", outdata->data);
		if (outdata->pl != NULL)
		{
			push_queue(pque, outdata->pl);
		}
		if (outdata->pr != NULL)
		{
			push_queue(pque, outdata->pr);
		}
	}

	destroy_queue(pque);
}

6、计算结点个数

int get_tree_node_cnt(TNode_t *proot)
{
	if (NULL == proot)
	{
		return 0;
	}
	return get_tree_node_cnt(proot->pl)+get_tree_node_cnt(proot->pr)+1;
}

7、计算层数

int get_tree_layer_cnt(TNode_t *proot)
{
	if (NULL == proot)
	{
		return 0;
	}
	int cntl = get_tree_layer_cnt(proot->pl);
	int cntr = get_tree_layer_cnt(proot->pr);

	return cntl > cntr ? cntl + 1 : cntr + 1;
}

8、销毁树

void destroy_tree(TNode_t *proot)
{
	if (NULL == proot)
	{
		return ;
	}
	destroy_tree(proot->pl);
	destroy_tree(proot->pr);
	free(proot);
}

五、程序在书写过程中遇到的问题

为在预编译指令进行解析的时候，会在这里来回跳转包含

头文件推迟包含，哪里需要哪里包，否则会头文件进行包含重复

为了防止，头文件中你中有我，我中有你的问题，还是哪里需要哪里包含即可