数据结构-二叉树

---

在学习二叉树之前我们先来了解一下树吧

简单了解树

树的概念

树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的

树的特点

形状图：

（1）节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的为6
（2）叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I…等节点为叶节点非终端节点或分支节点:度不为0的节点;如上图:D、E、F、G…等节点为分支节点
（3）双亲节点或父节点:若一个节点含有子节点，则这个节点称为其子节点的父节点;如上图:A是B
（4）孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;如上图:B是A的孩子节
（5）兄弟节点:具有相同父节点的节点互称为兄弟节点（亲兄弟）;如上图:B、C是兄弟节点亲兄弟
（6）树的度:一棵树中，最大的节点的度称为树的度;如上图:树的度为6
（7）节点的层次:从根开始定义起，根为第1层，根的子节点为第2层，以此类推;树的高度或深度:树中节点的最大层次;如上图:树的高度为4
（8）节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
（9）森林:由m(m>0)棵互不相交的多颗树的集合称为森林;(数据结构中的学习并查集本质就是一日常很少碰到森林，并查集就是一个森林

区分树与非树

二叉树

二叉树的概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

二叉树的特点

1.每个结点最多有两棵子树即二叉树不存在度大于2的结点。
2.二叉树的子树有左右之分，其子树的次序不能颠倒。

结构图

特殊的二叉树

1.满二叉树:一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k)-1，则它就是满二叉树。

2.完全二叉树:完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树

二叉树的性质

1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
2.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
3.对任何一棵二叉树,如果度为0其叶结点个数为n0,度为2的分支结点个数为n2则有n0=n2+1
4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=1og√n+1

练习1

1.某二叉树共有 399 个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为()
A 不存在这样的二叉树
B200
C 198
D 199
解析：
根据上面的性质：度为2的分支结点个数为n2则有n0=n2+1，就可以得出叶节点个数为 ：199+1=200，所以这题选择A
2.在具有 2n 个结点的完全二叉树，叶子结点个数为()
A n
B n+1
c n-1
Dn/2
解析：

3.一棵完全二叉树的节点数位为531个，那么这棵树的高度为()
A 11
B 10
C 8
D 12
解析：

实现遍历

1.思想：

按照分治算法的思想，将大问题转化为各个子问题，所以这里我们要用到递归

2.快速构建二叉树
树的图：

struct erchashu {
	shuju data;
	ST* n;//左
	ST* m;//右
};
int main() {
    //以下构建5个结点
	ST* A = (ST*)malloc(sizeof(ST));
	A->data = 'A';
	A->n = NULL;
	A->m = NULL;
	ST* B = (ST*)malloc(sizeof(ST));
	B->data = 'B';
	B->n = NULL;
	B->m = NULL;
	ST* C = (ST*)malloc(sizeof(ST));
	C->data = 'C';
	C->n = NULL;
	C->m = NULL;
	ST* D= (ST*)malloc(sizeof(ST));
	D->data = 'D';
	D->n = NULL;
	D->m = NULL;
	ST* E = (ST*)malloc(sizeof(ST));
	E->data = 'E';
	E->n = NULL;
	E->m = NULL;
	//按照树的形状构建
	A->n = B;
	A->m = C;
	B->n = D;
	B->m = E;

3.前序
前序是先搜索根，再到左子树，最后右子树
如：

代码实现：

void  qian(ST* q) {//前序
//限制条件，当为空时打印NULL并且返回空
	if (q == NULL) {
		printf("NULL ");
		return;
	}	
	else {
		printf("%c ", q->data);//打印根的数据
		qian(q->n);// 左  迭代后进行递归
		qian(q->m);//右  迭代后进行递归
	}
}

递归过程图：

运行结果：

4.中序
中序是先左子树，再根，最后右子树
如：

代码实现：

void  zho(ST* q) {//中序
//限制条件，当为空时打印NULL并且返回空
	if (q == NULL) {
		printf("NULL ");
		return;
	}
	else {
		zho(q->n);//先左子树，迭代递归
		printf("%c ", q->data);
		zho(q->m);//后右子树，迭代递归
	}
}

运行结果：

5.后序
后序是先左子树，再右子树，最后根
如：

代码实现：

void  ho(ST* q) {//后序
	if (q == NULL) {
		printf("NULL ");
		return;
	}
	else {
		ho(q->n);//先左
		ho(q->m);//再右
		printf("%c ", q->data);
	}
}

运行结果：

6.节点个数

代码实现：

int jiedian2(ST* q) {
	if (q == NULL)
		return 0;//空就返回0
		//左右子树和根（这里的1代表的就是根（一个根就是一个节点））累加的结果
	return jiedian2(q->n) + jiedian2(q->m) + 1;
	
}

递归展开图：

运行结果：

7.叶子个数
求叶的个数和求结点的方法差不多，就是返回条件换成了左右为空才返回1

//叶点
int  yezi(ST* q) {
	if (q->n == NULL && q->m == NULL)//左右都为空就返回1
		return 1;
	return yezi(q->n) + yezi(q->m);//先从左再到右，最后返回两边叶的和
}

运行结果：

9.以上代码总览

struct erchashu {
	shuju data;
	ST* n;//左
	ST* m;//右
};
void  qian(ST* q) {//前序
	if (q == NULL) {
		printf("NULL ");
		return;
	}
	else {
		printf("%c ", q->data);
		qian(q->n);
		qian(q->m);
	}
}
void  zho(ST* q) {//中序
	if (q == NULL) {
		printf("NULL ");
		return;
	}
	else {
		zho(q->n);
		printf("%c ", q->data);
		zho(q->m);
	}
}
void  ho(ST* q) {//后序
	if (q == NULL) {
		printf("NULL ");
		return;
	}
	else {
		ho(q->n);
		ho(q->m);
		printf("%c ", q->data);
	}
}
//结点-遍历
void jiedian1(ST* q, int* n) {
	if (q == NULL)
		return;
	else {
		(*n)++;
		jiedian1(q->n,n);
		jiedian1(q->m, n);
	}
}
//结点-递归
int jiedian2(ST* q) {
	if (q == NULL)
		return 0;
	return jiedian2(q->n) + jiedian2(q->m) + 1;
}
//叶点
int  yezi(ST* q) {
	if (q->n == NULL && q->m == NULL)
		return 1;
	return yezi(q->n) + yezi(q->m);
}
int main() {
	ST* A = (ST*)malloc(sizeof(ST));
	A->data = 'A';
	A->n = NULL;
	A->m = NULL;
	ST* B = (ST*)malloc(sizeof(ST));
	B->data = 'B';
	B->n = NULL;
	B->m = NULL;
	ST* C = (ST*)malloc(sizeof(ST));
	C->data = 'C';
	C->n = NULL;
	C->m = NULL;
	ST* D= (ST*)malloc(sizeof(ST));
	D->data = 'D';
	D->n = NULL;
	D->m = NULL;
	ST* E = (ST*)malloc(sizeof(ST));
	E->data = 'E';
	E->n = NULL;
	E->m = NULL;
	A->n = B;
	A->m = C;
	B->n = D;
	B->m = E;
	qian(A);
	printf("\n");
	zho(A);
	printf("\n");
	ho(A);
	printf("\n");
	int n = 0;
	jiedian1(A, &n);
	printf("%d\n", n);
	printf("%d\n", jiedian2(B));
	printf("%d\n", yezi(A));
	return 0;
}

10.广度优先遍历
我们上面的前序和中序后序也叫深度优先遍历
广度优先遍历：
从上到下，一层一层遍历
如：

那么怎么实现捏？
我们这里是通过队列去实现的
队列的特点是先进的先出，那么我们可以让树的根先进队列，再保留根的左子树和右子树，然后让根出列，最后用保留的左右子树作为下一次的根（NULL不用进队），一直遍历到最后队列为空就结束。
执行过程图：

代码实现：
队列：
Queue.h

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
typedef  struct erchashu  ST;
typedef   char   shuju;
typedef ST* QDataType;

struct erchashu {
	shuju data;
	ST* n;//左
	ST* m;//右
};
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);

// 队尾入
void QueuePush(Queue* pq, QDataType x);
// 队头出
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);//头出
int QueueSize(Queue* pq);//个数
bool QueueEmpty(Queue* pq);//是否为空

Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void QueueInit(Queue* pq) {//初始化
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x) {//队尾入
	assert(pq);
	QNode* p = (QNode*)malloc(sizeof(QNode));
	if (p == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	p->data = x;
	p->next = NULL;
	if (pq->tail == NULL)
		pq->head = pq->tail = p;
	else {
		pq->tail->next = p;
		pq->tail = p;
	}
}

void QueuePop(Queue* pq) {
	assert(pq);
	//一个
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//多个
	else {
		Queue* p = pq->head->next;
		free(pq->head);
		pq->head = NULL;
		pq->head = p;
	}
}

QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
int QueueSize(Queue* pq) {
	assert(pq);
	assert(pq->tail);
	int n = 0;
	QNode* p = pq->head;
	while (p)
	{
		n++;
		p = p->next;
	}
	return  n;
}

bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head==NULL;
}

void QueueDestory(Queue* pq) {
	assert(pq);
	while (pq->head) {
		QNode* p = pq->head->next;
		free(pq->head);
		pq->head = NULL;
		pq->head = p;
	}
	pq->head = pq->tail = NULL;
}

二叉树：

void guangdu(ST* q) {
	Queue p;
	QueueInit(&p);
	if (q)//不为空进队
		QueuePush(&p, q);
	while (!QueueEmpty(&p)) {//判断是否为空
		ST* te = QueueFront(&p);//用变量保留根
		QueuePop(&p);//出列
		printf("%c ", te->data);
		if(te->n)//不为空就入队
			QueuePush(&p, te->n);
		if(te->m)
			QueuePush(&p, te->m);
	}
	QueueDestory(&p);//释放
}


int main() {
	ST* A = (ST*)malloc(sizeof(ST));
	A->data = 'A';
	A->n = NULL;
	A->m = NULL;
	ST* B = (ST*)malloc(sizeof(ST));
	B->data = 'B';
	B->n = NULL;
	B->m = NULL;
	ST* C = (ST*)malloc(sizeof(ST));
	C->data = 'C';
	C->n = NULL;
	C->m = NULL;
	ST* D= (ST*)malloc(sizeof(ST));
	D->data = 'D';
	D->n = NULL;
	D->m = NULL;
	ST* E = (ST*)malloc(sizeof(ST));
	E->data = 'E';
	E->n = NULL;
	E->m = NULL;
	A->n = B;
	A->m = C;
	B->n = D;
	B->m = E;
	guangdu(A);
	return 0;
}

运行结果：

练习2

1.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为()
A .E
B. F
C.G
D.H
解析：

2.设一课二叉树的中序遍历序列:badce，后序遍历序列:bdeca，则二叉树前序遍历序列为_____。
A adbce
B decab
C debac
D abcde
解析：

总结：

先+中序能还原树
中+后序也能还原树

练习3

二叉树最大深度

分析：
1.我们先算左和右子树的深度，再左右对比返回大的一方再加1
2.我们可以通过递归计算每次左右子树的大小
代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root) {
    if(root==NULL)//限制条件
    return 0;
    int t=maxDepth(root->left);//左子树长度
    int f=maxDepth(root->right);//右子树长度
return t>f?t+1:f+1;//对比，返回大的+1
}

以上就是我的分享了，如果有什么错误，欢迎在评论区留言。
最后，谢谢大家的观看！