提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、树的概念
二、使用步骤
- 1.引入库
- 2.读入数据
总结

前言

树是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由 n(n>0)个有限节点组成一个具有层次关系的集合。

一、树的各种概念

满足树的条件：

1、有且仅有一个根节点

2、其余的节点可以分为m个互不相交的有限集合

1. 度数

一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树种节点的最大度数

2. 树叶

度数为0的节点

3. 深度（高度）

节点的层数等于父节点的层数加1，根节点的层数定义为1，把树种节点层数的最大值称为该树的深度或者高度

4. 边数

一个节点系列k1,k2, ……,ki,ki+1, ……,kj,并满足ki是ki+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1,即路径中的边数

5. 二叉树

5.1概念

二叉树是n个节点的有限集合，它或者是空集，或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成

注意：二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右

5.2 特征

1、二叉树最多有两个子节点

2、严格区分左子树和右子树

5.3 二叉树的性质

二叉树第i（i>=1）层上的节点最多为2i-1个
深度为k（k>=1）的二叉树最多有2k-1个节点

总节点的个数：n = 2^0+2^1+2^2 +……+2^(k-1)

2n = 2^1+2^2+……2^(k-1)+2^k

两个相减：n = 2k-1

3、在任意二叉树中，树叶的数目比度数为2的数目多1：

所有节点的个数为n = 所有的子节点的个数+1（根节点）

度数为0的节点的个数为n0，它的子节点的个数为0

度数为1的节点的个数为n1，它的子节点的个数为n1

度数为2的节点的个数为n2，它的子节点的个数为2n2

n = 0+n1+2n2+1

n0+n1+n2 = 0+n1+2n2+1

n0 = n2+1

案例：2、具有10个叶节点的二叉树有(B )个度数为2的节点

A．8 B.9 C.10 D.11

5.4二叉树的遍历

解题思路：一般来说，会给出一个前序遍历的结果或者一个后序遍历的结果，再给出一个中序遍历的结果，求另外一个遍历结果。

先看前/后序遍历，可以的出根是谁，再看中序看根左边有谁右边有谁，轮换着看，知道最后画出相应的图。

二、使用步骤

1.引入库

代码如下（示例）：

//创建树的根结点
Tree *createTree(data_type item)
{
	Tree *pBoot = NULL;
	pBoot = (Tree *)malloc(sizeof(Tree));
	if(NULL == pBoot)
	{
		perror("malloc error");
		return NULL;
	}
	memset(pBoot,0,sizeof(Tree));

	pBoot->data = item;

	return pBoot;
}
//向数中插入数据
int insertTree(Tree *pBoot,data_type item)
{
	//1.入参判断
	if(NULL == pBoot)
	{
		return PBOOTNULL;
	}
	//2.创建一个新节点
	Tree *pNew = (Tree *)malloc(sizeof(Tree));
	if(NULL == pNew)
	{
		perror("malloc error");
		return MALLOCERROR;
	}
	memset(pNew,0,sizeof(Tree));
	pNew->data = item;
	//3.插入
	while(1)
	{
		//判断pNew是左孩子还是右孩子
		if(pNew->data < pBoot->data)
		{
			//左孩子
			if(pBoot->lChild != NULL)
			{
				pBoot = pBoot->lChild;
			}
			else
			{
				pBoot->lChild = pNew;
				return OK;
			}
		}
		else
		{
			//右孩子
			if(pBoot->rChild != NULL)
			{
				pBoot = pBoot->rChild;
			}
			else
			{
				pBoot->rChild = pNew;
				return OK;
			}
		}
	}
}

//中序遍历
void midOrder(Tree *pBoot)
{
	if(NULL == pBoot)
	{
		return ;
	}
	midOrder(pBoot->lChild);
	printf("%d ",pBoot->data);
	midOrder(pBoot->rChild);
}

2.读入数据

代码如下（示例）：

int main(void)
{
	int i;
	data_type arr[20] = {54,26,33,42,98,77,88,12,5,18};
	Tree *pBoot = createTree(arr[0]);

	for(i = 1; i < 10; i++)
	{
		insertTree(pBoot,arr[i]);
	}

	midOrder(pBoot);
	printf("\n");
	
	return 0;
}

总结

学习树这一块，主要是把概念记清楚，并记住遍历的方式等。这一块的代码并不难写，还需要加深学习。

本文含有隐藏内容，请开通VIP 后查看

关于树的一些学习心得