数据结构：树的概念以及二叉树的实现

目录

一、树的概念

二、二叉树的概念

三、二叉树的实现

一、树的概念

• 树是一种非线性的数据结构

• 度：一个节点包含子树的数目（换种话来说，有多少条分支）
• 节点：用于存放数据，是构成复杂树的基本结构
• 双亲节点：如：A为B、C的双亲节点
• 孩子节点：如：B、C为A的孩子节点
• 兄弟节点：如：B、C有同个双亲节点，则B、C互为兄弟节点
• 叶子节点：度为0的节点（没有分支的节点），如D、E、F节点

树的层次与深度

• 树的层次：从根节点开始算起，根节点为第一层，每经过对应的孩子节点，则层数加1
• 树的高度：树中最高的层数为树的高度

二、二叉树的概念

二叉树的定义：

• 任意节点的度小于或者等于2的树（即：一个树中，一个节点的分支最多有2个）
• 树中的节点有序排列，次序不能颠倒！

二叉树的分类：

• 满二叉树：除了叶子节点外，每一个节点的度都为2（每一个节点都有2个孩子节点）
• 完美二叉树：除了叶子节点外，每一个节点的度都为2，并且填充满每一层（即最后一层一定全为叶子节点）
• 完全二叉树：最简单的识别方法：从根节点开始，自上而下，从左到右，能够按顺序进行连续编号
• 三种二叉树的包含关系：如下图所示

 二叉树的存储方式：

• 顺序存储：为完全二叉树时，可以完全填满空间。但为其他二叉树时，则会浪费大量存储空间。因此二叉树的存储方式一般均为链式存储。
• 链式存储：一般为将存储节点定义为：左孩子指针、数据、右孩子指针

二叉树的插入原理与删除原理：

• 插入：首先二叉树大小顺序为，小、中、大。然后通过比较插入数据与根节点的大小，来插入根节点的对应数据。我们插入的方法就是通过递归的方式，不断将比较后的节点作为新的根节点来进行插入。
• 删除：删除某个节点（根节点），可以使用该节点的左子树最大的节点替换或者使用该节点的右子树最小节点替换。我们需要做的与插入类似，通过递归的方法，不断将节点进行删除与替换。

二叉树的几种遍历方式：（不同种顺序的区别：根节点（父亲节点）的位置不同）

• 前序遍历：根节点（双亲节点）->左子节点->右子节点
• 中序遍历：左子节点->根节点（双亲节点）->右子节点
• 后序遍历：左子节点->右子节点->根节点（双亲节点）
• 按层遍历：从上到下，从左到右，一层一层遍历（通过队列来实现）

三、二叉树的实现

• 二叉树、与队列的结构体（用于实现二叉树的按层遍历）

//二叉树节点
typedef struct tree_Node
{
	int data;
	struct tree_Node *lchild, *rchild;
}treeNode,*linktree;


//队列存储节点
typedef struct sq_Node
{
	struct tree_Node *data;
	struct sq_Node *next;
}sqNode,*sqNode_p;

//队列管理结构体
typedef struct sq
{
	struct	sq_Node *front;
	struct	sq_Node *rear;
}sq,*sq_p;

• 初始化队列、入队、出队、判断队列是否为空。

/*初始化队列*/
sq_p init_sq()
{
	sq_p sq = malloc(sizeof(sq));
	if(sq != NULL)
	{
		//开辟 队列链表 的头结点,队头指向头结点
		sq->front = sq->rear = (sqNode_p)malloc(sizeof(sqNode));
		sq->rear->next = NULL;
		return sq;
	}
}

/*
	判断队列是否为空
 */
bool isEmpty(sq_p sq)
{
	return sq->front ==  sq->rear;
}

/*
	入队列：
	队列的地址   队列存储节点中的数据
*/
bool in_sq(sq_p sq, linktree data)
{
	sqNode_p new = malloc(sizeof(sqNode));//开辟新的队列存储节点
	if (new != NULL)
	{
		new->data = data;//优先处理新节点
		new->next = NULL;

		sq->rear->next = new;//队尾的节点链接上新的节点
		sq->rear = new;//新的节点为new

		return true;
	}
	else return false;
}

/*
	出队列：
	队列的地址 指向所需要数据的指针
*/
bool out_sq(sq_p sq, linktree *data)
{
	if(isEmpty(sq))
		return false;

	//队列的front一直指向头节点
	sqNode_p p = sq->front->next;//p指向第一个节点（相当于队列中的队头）
	*data = p->data;
	sq->front->next = p->next;//将第一个节点从链表中删除
	if (sq->rear == p)//如果为只有一个节点的情况，则需要更新队尾指针
	{
		sq->rear = sq->front;
	}
	free(p);

	return true;
}

• 二叉树节点的创建、插入、删除

/*创建新节点*/
linktree newTreeNode(int n)
{
	linktree new = malloc(sizeof(treeNode));
	if(new != NULL)
	{
		new->data = n;
		new->lchild = NULL;
		new->rchild = NULL;
	}

	return new;
}

/*
	插入二叉树节点：
	递归调用
*/
linktree insert_TreeNode(linktree new, linktree root)
{
	//插入检验
	if (new == NULL)//如果new为NULL则直接返回
		return root;

	//退出条件（新节点插入位置）
	if (root == NULL)//如果root为空，则新的根节点为new
		return new;
	
	//比根节点数据大，则再比较右子节点(递归方式：以右子节点为根节点，再与要插入的节点进行比较)
	if (new->data > root->data)
	{
		root->rchild = insert_TreeNode(new, root->rchild);
	}
	else if(new->data < root->data)
	{
		root->lchild = insert_TreeNode(new, root->lchild);
	}
	else
	{
		printf("%d is already exist\n", new->data);
	}

	return root;
}

/*
	插入二叉树节点：
	非递归调用
 */
linktree insert_TreeNode_normal(linktree new, linktree root)
{
	//插入检验
	if(new == NULL)
		return root;

	//root为空的情况
	if (root == NULL)
		return new;

	//root不为空的情况
	linktree parents = NULL;
	linktree pos = root;
	while(pos)//parents保存要插入的节点位置
	{
		parents = pos;
		if(new->data > pos->data)
			pos = pos->rchild;
		else if(new->data < pos->data)
			pos = pos->lchild;
		else
			printf("%d is already exist\n", new->data);
	}

	//插入
	if (new->data > parents->data)
	{
		parents->rchild = new;
	}
	else if (new->data < parents->data)
	{
		parents->lchild = new;
	}

	return root;
}

/*
	删除节点:
	删除某个节点后，要用该节点的左子树中最大的节点替换，或者
	使用右子树中最小的节点替换
 */
linktree remove_TreeNode(linktree root , int n)
{
	//查找检验
	if (root == NULL)
		return NULL;

	//查找到需要删除的节点
	if(n < root->data)//查找数据比根节点数据要小，往左边查找
	{
		root->lchild = remove_TreeNode(root->lchild, n);
	}
	else if (n > root->data)//查找数据比根节点数据大，往右边查找
	{
		root->rchild = remove_TreeNode(root->rchild, n);
	}
	else if(n == root->data)//找到删除的节点,还需要判断要删除的节点是否有子树
	{
		linktree tmp;
		/*
			两种情况：
			1、有左子树或者有右子树（包括既有左子树又有右子树的情况）
			2、没有左子树，也没有右子树。（即：该节点为叶子节点,直接删除）
		 */
		if(root->lchild != NULL)
		{
			/*
				左子树不为空（只有左子树、既有左子树又有右子树）的情况下，找到左子树中最大的节点来代替根节点
			 */
			for(tmp=root->lchild; tmp->rchild!=NULL; tmp=tmp->rchild);
			root->data = tmp->data;//替换数据
			root->lchild = remove_TreeNode(root->lchild, tmp->data);//删除左子树中最大的节点。
		}
		else if (root->rchild != NULL)
		{
			/*
				左子树为空，有右子树的清空
			 */
			for(tmp=root->rchild; tmp->lchild!=NULL; tmp=tmp->lchild);
			root->data = tmp->data;//替换数据
			root->rchild = remove_TreeNode(root->rchild, tmp->data);//删除右子树中最小的节点
		}
		else
		{
			/*
				为叶子节点的情况
			 */
			free(root);
			return NULL;
		}

	}

	return root;
}

• 二叉树的排序（按层遍历、前序、中序、后序）

/*
	按层遍历：
 */
void level_travel(linktree root)
{
	if (root == NULL)
		return;

	//先创建一个队列
	sq_p head = init_sq();
	//根结点入队
	in_sq(head, root);

	linktree tmp;
	while(1)
	{
		if (!out_sq(head,&tmp))//出队，如果为空队则跳出循环
			break;

		printf("%d\t", tmp->data);
		if (tmp->lchild != NULL)
		{
			in_sq(head,tmp->lchild);
		}
		if (tmp->rchild != NULL)
		{
			in_sq(head,tmp->rchild);
		}
	}

}

/*
	前序遍历节点：
	父节点 - 左子节点 - 右子节点
*/
void pre_travel(linktree root)
{
	//退出条件
	if (root == NULL)
		return;

	printf("%d\t", root->data);
	pre_travel(root->lchild);
	pre_travel(root->rchild);
}

/*
	中序遍历节点：
	左子节点 - 父节点 - 右子节点
*/
void mid_travel(linktree root)
{
	//退出条件
	if(root == NULL)
		return;

	mid_travel(root->lchild);//左子节点
	printf("%d\t", root->data);//父节点
	mid_travel(root->rchild);//右子节点
}

/*
	后序遍历节点：
	左子节点 - 右子节点 - 父节点
 */
void last_travel(linktree root)
{
	//退出条件
	if(root == NULL)
		return;

	last_travel(root->lchild);//左子节点
	last_travel(root->rchild);//右子节点
	printf("%d\t", root->data);//父节点

}