二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)

这篇具有很好参考价值的文章主要介绍了二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、树概念及结构(了解) 

1.1树的概念 

1.2树的表示 

二、二叉树概念及结构 

2.1概念 

2.2现实中的二叉树:

2.3数据结构中的二叉树:

2.4特殊的二叉树: 

2.5 二叉树的存储结构 

2.51 顺序存储: 

2.5.2 链式存储:

三、二叉树性质相关选择题练习 

四、二叉树的实现

4.1头文件:

4.2Test.c

4.3前序,中序,后序(深度优先遍历)

 4.4二叉树所有节点的个数

​编辑

4.5叶节点的个数

4.6层序遍历(广度优先遍历,使用队列)


一、树概念及结构(了解) 

1.1树的概念 

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

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

有一个特殊的结点,称为根结点,根节点没有前驱结点除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继,因此,树是递归定义的。

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

  • 节点的度:一个节点含有的子树的个数称为该节点的度; 如下图:A的为6

  • 叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点

  • 非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点

  • 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B 的父节点

  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节 点

  • 兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点

  • 树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6

  • 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

  • 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4

关于树的高度,还有一种看法,就是把高度从0开始看,此时树的高度为3。

  • 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先

  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙

  • 森林:由m(m>0)棵互不相交的多颗树的集合称为森林;(数据结构中的学习并查集本质就是 一个森林)

1.2树的表示 

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一个孩子结点
    struct Node* _pNextBrother;   // 指向其下一个兄弟结点
    DataType _data;               // 结点中的数据域
};

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

另一种方式:顺序表存孩子的指针(不推荐使用)

struct TreeNode

{

        int data;

        vector<struct TreeNode*> childs;

}

还有一种表示方式,双亲表示法:

双亲表示法采用顺序表(数组)存储普通树,其实现的核心思想是:顺序存储各个节点的同时,给各节点附加一个记录其父节点位置的变量。

#define MAX_SIZE 100  // 宏定义树中结点的最大数量
 
typedef struct Snode{
    char data;
    int parent;
} PTNode;
 
typedef struct{
    PTNode tnode[MAX_SIZE];  // 存放树中所有结点
    int n;  // 结点数
} PTree;

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

1.3树在实际中的运用(表示文件系统的目录树结构) 

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

二、二叉树概念及结构 

2.1概念 

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

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

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

2.2现实中的二叉树:

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

2.3数据结构中的二叉树:

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

2.4特殊的二叉树: 

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉
树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。
2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对
于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号
从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉
树。

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

2.5 二叉树的存储结构 

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
二叉树的性质 
1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h- 1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2
+1
4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=logN + 1

2.51 顺序存储: 

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树
会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲
解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

2.5.2 链式存储:

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的
方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩
子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都
是二叉链,后面课程学到高阶数据结构如红黑树等会用到三叉链。

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

三、二叉树性质相关选择题练习 

1.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为( 

A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为
()
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
A 不存在这样的二叉树
B 200
C 198
D 199
2.在具有 2n 个结点的完全二叉树中,叶子结点个数为( )
A n
B n+1
C n-1
D n/2
3.一棵完全二叉树的节点数位为531个,那么这棵树的高度为( )
A 11
B 10
C 8
D 12
 

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

四、二叉树的实现

4.1头文件:

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



typedef int BTDataType;

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

4.2Test.c

int main()
{
	char str[100]; // 存储节点值的字符串  

	scanf("%s", str); // 读取输入字符串,注意应该直接传入数组名
	int i = 0; // 索引初始化为0  
	BTNode* root = CreatTree(str, &i); // 创建二叉树,并将根节点赋值给root  
	PrevOrder(root); // 前序遍历二叉树并输出结果  
	printf("\n");
	InOrder(root);//  中序遍历二叉树并输出结果
	printf("\n");
	PostOrder(root);//  后序遍历二叉树并输出结果

	printf("\n");
}

4.3创建一个二叉树

// 创建一个二叉树的函数,a是包含节点值的字符串,pi是指向当前要处理的字符的索引的指针  
BTNode* CreatTree(char* a, int* pi)
{
	// 如果当前字符是'#',表示这是一个空节点  
	if (a[*pi] == '#')
	{
		++(*pi); // 增加索引  
		return NULL; // 返回空指针表示这是一个空节点  
	}

	// 为新节点分配内存  
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		printf("malloc fail\n"); // 如果分配失败,输出错误信息  
		exit(-1); // 退出程序  
	}

	// 设置节点的值,并增加索引  
	root->data = a[*pi];
	++(*pi);

	// 递归地创建左子树和右子树  
	root->left = CreatTree(a, pi);
	root->right = CreatTree(a, pi);

	return root; // 返回新创建的节点
}

4.4前序,中序,后序(深度优先遍历)

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

// 先序遍历二叉树  
void PrevOrder(BTNode* root)
{
	// 如果当前节点为空,则打印"NULL"并返回  
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	// 访问当前节点的数据  
	printf("%c ", root->data);
	// 递归遍历左子树  
	PrevOrder(root->left);
	// 递归遍历右子树  
	PrevOrder(root->right);
}

// 中序遍历二叉树  
void InOrder(BTNode* root)
{
	// 如果当前节点为空,则打印"NULL"并返回  
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	// 递归遍历左子树  
	InOrder(root->left);
	// 访问当前节点的数据  
	printf("%c ", root->data);
	// 递归遍历右子树  
	InOrder(root->right);
}

// 后序遍历二叉树  
void PostOrder(BTNode* root)
{
	// 如果当前节点为空,则打印"NULL"并返回  
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	// 递归遍历左子树  
	PostOrder(root->left);
	// 递归遍历右子树  
	PostOrder(root->right);
	// 访问当前节点的数据  
	printf("%c ", root->data);
}

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

 4.4二叉树所有节点的个数

 二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

//方法一:定义全局变量(不推荐)

// 全局变量,用于记录树的大小(节点数)  
// 注意:使用全局变量通常不是好的做法,应该尽量避免  
int size = 0;  
  
// 计算二叉树的大小(节点数)
void TreeSize(BTNode* root)  
{  
	// 如果节点为空,则不计算大小,直接返回  
	if (root == NULL)  
	{  
		return; // 在 void 函数中这样写是可以的,但如果是 int 类型函数则需要返回一个整数值  
	}  
	else {  
		// 节点非空,增加 size 的计数  
		++size;  
	}  
  
	// 递归计算左子树的大小  
	TreeSize(root->left);  
	// 递归计算右子树的大小  
	TreeSize(root->right);  
	
}

方法二:传址调用

// 定义TreeSize函数,用于计算二叉树的大小(节点数)  
// 参数:root - 指向二叉树根节点的指针;psize - 指向一个整数的指针,用于存储节点数  
void TreeSize(BTNode* root, int* psize)  
{  
	// 如果根节点为空(即树为空),则直接返回,不执行任何操作  
	if (root == NULL)  
	{  
		return;  
	}  
	else // 如果根节点不为空(即树非空)  
	{  
		// 通过解引用psize指针来递增其指向的整数值,表示当前节点被计数  
		++(*psize);  
	}  
  
	// 递归调用TreeSize函数来计算左子树的大小  
	TreeSize(root->left, psize);  
	// 递归调用TreeSize函数来计算右子树的大小  
	TreeSize(root->right, psize);  
}

方法三:递归、分治思想:
否则,返回左子树节点数 + 右子树节点数 + 1(当前节点)

int TreeSize(BTNode* root)
{
    // 如果树为空(即根节点为NULL),则返回0  
    // 否则,返回左子树节点数 + 右子树节点数 + 1(当前节点)
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

4.6叶节点的个数

int LeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return TreeSize(root->left) + TreeSize(root->right);

}
// 计算二叉树中叶子节点的数量(但存在错误)  
int LeafSize(BTNode* root)  
{  
    // 如果当前节点为空,说明不是叶子节点,返回0  
    if (root == NULL)  
        return 0;  
  
    // 如果当前节点既没有左子树也没有右子树,那么它是一个叶子节点,返回1  
    if (root->left == NULL && root->right == NULL)  
        return 1;  
  
    // 递归计算左子树和右子树中的叶子节点数量,并返回它们的和
    return TreeSize(root->left) + TreeSize(root->right); 
}

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

4.7层序遍历(广度优先遍历,使用队列)

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

这是使用的队列的代码

//队列初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

//队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}


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

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
		//表示这是第一个节点
	}
	else
	{
		pq->tail->next = newnode;
		//tail的后面加上新节点
		pq->tail = newnode;
		//再让tail指向newnode
	}
}
// 队头出
void QueuePop(Queue* pq)
{
	
	assert(pq);
	assert(pq->head);

	// 1、一个
	// 2、多个
	if (pq->head->next == NULL)
	{
		free(pq->head);//释放队头的空间
		pq->head = pq->tail = NULL;
		//队列为空
	}
	else
	{
		QNode* next = pq->head->next;
		//存储队头下一个节点的空间
		free(pq->head);
		//释放队头的空间
		pq->head = next;
		//让队头指向之前队头的下一个节点
	}
}

//队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}
//队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}
//队列数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}

	return size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
// 层序遍历二叉树  
void LevelOrder(BTNode* root)  
{  
    // 定义一个队列q  
	Queue q;  
    // 初始化队列  
	QueueInit(&q);  
    // 如果根节点不为空  
	if (root)  
	{  
        // 将根节点入队  
		QueuePush(&q, root);  
	}  
    // 当队列不为空时循环  
	while (!QueueEmpty(&q))  
	{  
        // 取出队列的队首元素,但不从队列中移除  
		BTNode* front = QueueFront(&q);    
  
        // 从队列中移除队首元素  
		QueuePop(&q);  
        // 访问队首元素的数据  
		printf("%c ", front->data);  
  
        // 如果队首元素有左子节点,将左子节点入队  
		if (front->left)  
		{  
			QueuePush(&q, front->left);  
		}  
        // 如果队首元素有右子节点,将右子节点入队  
		if (front->right)  
		{  
			QueuePush(&q, front->right);  
		}  
	}  
    // 销毁队列,释放其占用的资源  
	QueueDestory(&q); 
}

​​​​​​​二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言​​​​​​​

新年第一篇!!!

祝大家新年快乐

二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数),算法,数据结构,笔记,c语言,开发语言

看到这里了还不给博主扣个:
⛳️ 点赞☀️收藏 ⭐️ 关注!

你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。文章来源地址https://www.toymoban.com/news/detail-771504.html

到了这里,关于二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包