C语言二叉树深度详解（附带源码）

一个节点含有的子树的个数称为该节点的度：度为0的节点：度不为0的节点：一个节点含有子节点，这个节点称为子节点的父节点（国外有些书称为双亲结点，涉及到女权主义）：一个节点含有的子树的跟节点称为该节点的子节点：还有同一个父节点的节点互称为兄弟节点：一棵树中，最大的节点的度称为数的度：从根节点开始，根为第一层，根的子节点为第二层，以此类推（关于空树的高度最好从1开始，如果从0开始，空二叉树高度为0，而你

乌龟跌倒

2861人浏览 · 2024-02-22 12:51:35

乌龟跌倒 · 2024-02-22 12:51:35 发布

五、搜索二叉树：任何一颗树的左子树都比它小，右子树都比它大

六、二叉树的存储结构

七、二叉树基本操作

八、源码（有需要的同学，可以直接拿去交作业了）

一、基本概念：

度：一个节点含有的子树的个数称为该节点的度
叶节点或者终端节点：度为0的节点
非终端节或和分支节点：度不为0的节点
双亲结点或父节点：一个节点含有子节点，这个节点称为子节点的父节点（国外有些书称为双亲结点，涉及到女权主义）
孩子节点或子节点：一个节点含有的子树的跟节点称为该节点的子节点
兄弟节点（亲兄弟）：还有同一个父节点的节点互称为兄弟节点
树的度：一棵树中，最大的节点的度称为数的度
树的层数、高度、深度：从根节点开始，根为第一层，根的子节点为第二层，以此类推
（关于空树的高度最好从1开始，如果从0开始，空二叉树高度为0，而你只有一个根节点也称为0，矛盾）
节点的祖先:从该节点开始，往上回溯，都是该节点的祖先
子孙:该节点以下的节点都是其子孙
森林：有n棵不相交的树的集合叫做森林

二叉树就是度不超过2的树

树在实际中的应用：文件系统的目录就是一个树结构

二、实现二叉树的数据结构：

1、左孩子右兄弟法：用链表实现，每个节点有一个左孩子和一个右兄弟。每个节点只有一个左孩子但是可以有多个右兄弟

2、双亲表示法：用数组实现，每一个节点只记录其父亲

二叉树的遍历一般采用分治算法：分而治之，将大问题分成类似的子问题，直到子问题不可再分割

因为任何一颗树可以分成三个部分：
1、根节点
2、左子树
3、右子树

二叉树的四种遍历策略：
1、先序（先根）：根左子树右子树。先根，再左子树，此时的左子树又可以看成以该左节点为根的左子树，再循环遍历；
直到访问到最后一个左子树，即左叶节点，此时该节点的左子树为NULL，再到右子树也为NULL，此时，该节点算访问完成，即左子树已经遍历完毕，
左子树既然遍历完了，那就自然到了右子树，如此循环

2、中序（中根）:左子树根右子树//也就是说实际上最小的问题是只剩下最后一个节点，再继续访问其左子树和右子树，但是为空，可以执行，不要忽略访问NULL，便于理解

3、后序（后根）：左子树右子树根

先序、中序、后序是相对于左子树、右子树、根节点的访问顺序而言的。
先序就是先第一个访问根节点
中序就是第二个访问根节点
后序就是最后一个访问根节点
但是不论怎么遍历，访问一棵树，总是从第一层的根节点开始的
前中后序也叫深度优先遍历
属于递归方式

4、层序遍历，也叫广度优先遍历
核心思路：一层带下一层

定义一个队列，每次出一个节点，就把该节点的左右孩子放进去，依次循环

typedef 重定义结构体只是多加了一个ytpedef，需要有完整的结构，要深入的理解typedef的意义

如果对一个代码不理解，或者对一个递归不理解
就画一个函数递归展开图

三、二叉树性质：

1、若规定根节点的层数为1，则一颗非空二叉树的i层上最多有2^(i-1)个节点
2、规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^k -1
3、对任意一颗二叉树，如果度为0的叶节点数为n0，度为2的分支节点的个数为n2则有n0=n2+1;
4、规定根节点层数为1，具有n个节点的满二叉树的深度为h=log2N
5、一棵有N个节点的树有N-1条边
6、二叉树深度：k=log2(N+1)

满二叉树：每一层都是的节点都是满的

满二叉树节点数N：N = 2^k -1（N为节点数）
完全二叉树：前k-1都是满的，只有最后一层不满，但是最后一层的节点依然要求有顺序，即从左到右连续

四、相关计算

计算一颗完全二叉树的高度：
h=log2(N+1+x)//最后一层缺了X个节点
由于x不可能超过N，所以，可以近似认为，完全二叉树的高度就是log2(N+1)
而事实上，log2(N+1)和log2(N)没什么区别
所以当求一个完全二叉树的深度时,k=log2N,取低位整数

普通二叉树的增删查改没有实际意义。

五、搜索二叉树：任何一颗树的左子树都比它小，右子树都比它大

这样的结构非常适用于进行搜索：找一个数字，比节点大，只可能在它的右子树，比节点小，只可能在左子树，以此类推，画图，一目了然。
增加也是同样的道理。先加左边，再加右边
搜索查找一个数，最多查找数次为其高度，效率非常高

六、二叉树的存储结构

1、顺序存储，也就是使用数组来存储。但是一般用来存储完全二叉树，如果不是完全二叉树就会造成空间的浪费

2、链式结构
有两种：一种是二叉链，一种是三叉链
二叉链就是只有两个指针，一个指向左孩子，一个指向右孩子
三叉链就是有三个指针，多一个指针指向parent

七、二叉树基本操作

1、计算二叉树的节点数：
TrreeSize();
访问一个节点，不为空，++size
一种方式是：
定义一个全局变量，再对全局变量进行++zise（前置++相较于后置++略微高效）
但是如要调用第二次调用这个函数计算其他的二叉树，就会出现累加，在使用前都要对size置0，有问题。
同时，如果同时调用多个这个函数，size只有一个，有问题，这关系到多线程的问题
所以，使用传参的方式比较合适，即你计算你的，我计算我的，互不干涉，但是注意传参数要传地址，否则Asize不会改变
还有一种方式：
return root == NULL ? 0 : TreeeSize(root->left) + TreeSize(righe) + 1;
博客画图分析，画函数递归图，
这就是一个遍历思想的后序思想

2、求叶子叶节点的个数：
if(root ==Null) return 0;
if(root->left==NULL && root->right ==NLL) return 1;
return TreeSize(root->left) + TreeSize(root->right);

3、先序遍历

4、中序遍历

5、后续遍历

6、层序遍历

理解了写不出来就是没有理解，或者只是理解了一部分

7、非递归层序遍历

先序和中序可以还原一一颗树：先序可以确定根，中序可以确定左右子树
但是先序和后序不可以
后序加中序也是可以得到：后续最后一个可以确定根，中国可以确定左右子树

递归要注意传址，否则返回时就会销毁，每调用一个函数就是一个函数栈帧，这个函数里面的数据的改变不会影响上一层递归函数的值
即每一层都有一个i，下一层的++i不会影响上一层的i

八、源码（有需要的同学，可以直接拿去交作业了）

队列的层序遍历需要用到队列，所以我们需要单独创建一个队列相关的功能函数。C语言麻烦就麻烦在这里，造轮子比较麻烦。

头文件：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;//头
	QNode* rear;//尾
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
//void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

实现函数文件：

#include"BinaryTree.h"
#include"queue.h"

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[(*pi)] == '#') 
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc fail \n");
		exit(-1);
	}

	root->data = a[(*pi)++];
	root->left = BinaryTreeCreate(a,pi);
	root->right = BinaryTreeCreate(a,pi);
	printf("%c ", root->data);

	return root;
}

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root )
	QueuePush(&q, root);
	//根、左子树、右子树
	//当前节点入队列，然后出队列，再把当前节点的左右子节点入队列
	int levelsize = 1;
	while (!QueueEmpty(&q))
	{
		while(levelsize--)
		{
			BTNode* front = QueueFront(&q);
			QueuePop(&q);
			printf("%d ", front->data);

			if (front->left)
				QueuePush(&q, front->left);

			if (front->right)
				QueuePush(&q, front->right);
		}
		printf("\n");
		
		levelsize = QueueSize(&q);

	}

	QueueDestroy(&q);
	}


// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL) 
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
	root = NULL;
	printf("\n销毁成功 ");
}


// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	//分治：根、左子树、右子树
	//等于左子树的节点个数加上右子树的节点个数
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	//左子树的叶子节点+右子树的叶子节点个数
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return  1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//分治
	//找K层的节点个数，等于K-1层
	//找第三层的节点个数，就等于找第二层的下一层节点个数
	//如果当前已经是第K层，那就直接返回1
	//对于每一个节点进行判断，如果这个节点是第k层，那么返回1，不用继续往下
	//如果这个节点不是k层，那么就继续往下，判断他的左子树和右子树
	assert(k);
	if (root == NULL)
		return 0;
	//如果是第K层
	if (k - 1 == 0)
		return 1;
	//不是第k层
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	//对每一个节点进行检查
	//当前节点不是，找左子树和右子树
	//找到了，返回当前节点的值
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	//依旧是进入队列
	//如果出队列遇到空，如果此时队列为空，就是完全二叉树
	//如果队列不为空，就不是完全二叉树、
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return 1;
	QueuePush(&q,root);
	//根、左子树、右子树
	//在层序的基础上+
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//前面遇到空，跳出，如果后面还有非空的数据，那就不是完全二叉树
	//仅仅判断非空不行，因为空的二叉树节点也push了，此时就不是空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		
		if (front)
			return false;
	}
	
	QueueDestroy(&q);
	return   true;
}

#include"queue.h"
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

// 初始化队列 
void QueueInit(Queue* q)
{
	q->front = q->rear = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	if (q == NULL)
		return;
	if ( q->front == NULL)
	{
		QNode* temp = (QNode*)malloc(sizeof(QNode));
		if (temp == NULL)
		{
			perror("malloc fail!\n");
			exit(-1);
		}
		temp->data = data;
		temp->next = NULL;
		q->front = q->rear = temp;
		q->size++;
	}
	else
	{
		QNode* temp = (QNode*)malloc(sizeof(QNode));
		if (temp == NULL)
		{
			perror("malloc fail!\n");
			exit(-1);
		}
		temp->data = data;
		temp->next = NULL;
		q->rear->next = temp;
		q->rear = temp;
		q->size++;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	if (q->front == NULL)
	{
		return;
	}
	QNode* second = q->front->next;
	free(q->front);
	q->front = second;
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	if(q->rear == NULL)
	{
		return;
	}
	return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	if (q->rear == NULL)
	{
		return;
	}
	return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	if (q->size == 0)
	{
		return 1;
	}
	else
	{


		return  0;
	}
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	if (q->rear == NULL)
	{
		return;
	}
	QNode* cur = q->front;

	while (q->size--)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

测试文件：

#include"BinaryTree.h"
#include"queue.h"
BTNode* BuyBinaryTreeNode(int date)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = date;
	newnode->left = NULL;
	newnode->right = NULL;
	return  newnode;
}

int main()
{
	BTNode* node1 = BuyBinaryTreeNode(1);
	BTNode* node2 = BuyBinaryTreeNode(2);
	BTNode* node3 = BuyBinaryTreeNode(3);
	BTNode* node4 = BuyBinaryTreeNode(4);
	BTNode* node5 = BuyBinaryTreeNode(5);
	BTNode* node6 = BuyBinaryTreeNode(6);
	BTNode* node7 = BuyBinaryTreeNode(7);
	BTNode* node8 = BuyBinaryTreeNode(8);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->right = node6;
	node3->left = node7;

	printf("前序：");
	BinaryTreePrevOrder(node1);
	printf("\n");

	printf("中序：");
	BinaryTreeInOrder(node1);
	printf("\n");

	printf("后序：");
	BinaryTreePostOrder(node1);
	printf("\n");

	printf("层序：\n");
	BinaryTreeLevelOrder(node1);
	printf("\n");
	
	printf("叶子节点个数：%d\n", BinaryTreeLeafSize(node1));
	printf("第%d层节点个数：%d\n",2,BinaryTreeLevelKSize(node1, 2));

	//查找节点
	if (BinaryTreeFind(node1, 0))
		printf("存在：%d\n", BinaryTreeFind(node1, 0)->data);
	else
		printf("不存在该节点\n");
	
	//判断完全二叉树
	int ret = BinaryTreeComplete(node1);
	if(ret)
		printf("是完全二叉树\n");
	else
		printf("不是完全二叉树\n");

	BTDataType a[] = "ABD##E#H##CF##G##";
	int i = 0;
	BinaryTreeCreate(a,&i);
	BinaryTreeDestory(node1);
	return 0;
}