C语言数据结构详细解析二叉树的操作

目录
  • 二叉树分类
  • 二叉树性质
  • 性质的使用
  • 二叉树的遍历
    • 前序遍历
    • 中序遍历
    • 后序遍历
    • 层序遍历
  • 求二叉树的节点数
  • 求二叉树叶子结点个数
  • 求二叉树的最大深度
  • 二叉树的销毁

二叉树分类

满二叉树

除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。也可以理解为每一层的结点数都达到最大值的二叉树。

完全二叉树

一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

简单的说,完全二叉树就是最后一层可以有缺失的满二叉树(完全二叉树是一种特殊的满二叉树),并且是从右往左的缺失。

二叉树性质

  • 若规定根节点的层数为1,则一棵树非空二叉树的第 i 层上最多有2^(i-1)个节点。
  • 若规定根节点层数为1,则深度为h的二叉树的最大节点数是2^h−1
  • 对任何一颗二叉树,如果叶节点(度为0的节点)个数为 n0 ,度为 2 的节点个数为 n2 ,则n0 = n2 + 1。
  • 若规定根节点层数为1,具有N个节点的满二叉树的深度为小于(log_2)​N+1的最大整数。

性质的使用

在具有 2n 个结点的完全二叉树中,叶子结点个数为( )

A n

B n + 1

C n - 1

D n / 2

分析:

设度为 0 的结点有 x0 个

设度为 1 的结点有 x1 个

设度为 2 的结点有 x2 个

x0 + x1 + x2 = 2n

x0 = x2 + 1

由上面两个式子可推出:2 * 2x2 + x1 + 1 = 2n

因为是完全二叉树,x1 可能是0,1,但是要使上式结果为偶数,x1只能是1,所以 x2 等于n , 选A。

二叉树的遍历

首先我们先创建一个简单的二叉树

typedef char BTDataType;
typedef struct BinaryTreeNode {
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
int main()
{
	BTNode* A = (BTNode*)malloc(sizeof(BTNode));
	A->data = 'A';
	A->left = NULL;
	A->right = NULL;
	BTNode* B = (BTNode*)malloc(sizeof(BTNode));
	B->data = 'B';
	B->left = NULL;
	B->right = NULL;
	BTNode* C = (BTNode*)malloc(sizeof(BTNode));
	C->data = 'C';
	C->left = NULL;
	C->right = NULL;
	BTNode* D = (BTNode*)malloc(sizeof(BTNode));
	D->data = 'D';
	D->left = NULL;
	D->right = NULL;
	BTNode* E = (BTNode*)malloc(sizeof(BTNode));
	E->data = 'E';
	E->left = NULL;
	E->right = NULL;
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	LevelOrder(A);
}

前序遍历

前序(先序): 根 -> 左子树 -> 右子树

预期结果:A B D E C

//前序
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//为了结果更加直观,将NULL打印
		printf("NULL ");
		return;
	}
	//先打印根的数据
	printf("%c ", root->data);
	//遍历左子树
	PrevOrder(root->left);
	//遍历右子树
	PrevOrder(root->right);
}

编译结果:

中序遍历

中序:左子树 -> 根 -> 右子树

预期结果:D B E A C

void MidOrder(BTNode* root)
{
	//为了结果更加直观,将NULL打印
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	MidOrder(root->left);
	printf("%c ", root->data);
	MidOrder(root->right);
}

编译结果:

后序遍历

后续:左子树 -> 右子树 -> 根

预期结果:D E B C A

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

编译结果:

层序遍历

void LevelOrder(BTNode* root)
{
	//创建队列q
	Queue q;
	//初始化队列
	QueueInit(&q);
	//如果根结点不为空,将根节点入队列
	if (root) QueuePush(&q, root);
	//进行循环,直到队列为空
	while (!QueueEmpty(&q))
	{
		//获取队列的第一个数据,并打印
		QDataType front = QueueFront(&q);
		printf("%c ", front->data);
		//对头数据出队列
		QueuePop(&q);
		//如果左子树不为空,左子树入队列
		if (front->left != NULL)
		{
			QueuePush(&q, front->left);
		}
		//如果右子树不为空,右子树入队列
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
}

求二叉树的节点数

int BTSize(BTNode* root)
{
	return root == NULL ? 0 :1 + BTSize(root->left) + BTSize(root->right);
}

求二叉树叶子结点个数

int BTLeafSize(BTNode* root)
{
	if (root == 0) return 0;
	return root->left == NULL && root->right == NULL ? 1 : BTLeafSize(root->right) + BTLeafSize(root->left);
}

求二叉树的最大深度

int maxDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + fmax(maxDepth(root ->left),maxDepth(root ->right));
}

二叉树的销毁

//二叉树的销毁
//传二级指针是为了改变指针的指向
void DistoryTree(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	DistoryTree(&(*root)->left);
	DistoryTree(&(*root)->right);
	free(*root);
	*root = NULL;
}

到此这篇关于C语言数据结构详细解析二叉树的操作的文章就介绍到这了,更多相关C语言二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现线索二叉树的定义与遍历示例

    本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C语言二叉树层序遍历

    实现下面图中的二叉树层序遍历 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <unistd.h> typedef struct node { char data; struct node *lchild; struct node *rchild; }NODE, *PNODE; typedef struct qnode { PNODE pnode; struct qno

  • C语言中二叉树的后序遍历详解

    目录 一.二叉树的后序遍历.(递归) 二.二叉树的后序遍历(迭代) 总结 首先我们从两个方面讲解二叉树的后序遍历(递归+迭代) 一.二叉树的后序遍历.(递归) 思想: 首先我们从二叉树的根节点开始先遍历其左孩子,①接着同样继续遍历其左孩子的左孩子,直到某个左孩子节点的左孩子为NULL时,②开始遍历其右孩子,如果其为NULL则访问该节点的值域,并返回其双亲节点重复第二步的操作,如果其不为NULL则以该节点为根节点重复第一步的操作.直到访问完所有节点时结束递归. 代码: void BTreePost

  • C语言实现二叉树层次遍历介绍

    目录 什么是层次遍历? 那我们如何来实现这个算法呢? 主体代码: 总结 什么是层次遍历? 对于一颗二叉树来说,从根节点开始,按从上到下.从左到右的顺序访问每一个结点. 注:每一个结点有且访问一次. 那我们如何来实现这个算法呢? 实现原理: 对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下.从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历. 这里我们需要引用队列来实现. 主体代码: BiTree

  • C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C语言二叉树的遍历示例介绍

    在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率. #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW 3 typedef int Status; typedef

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言数据结构详细解析二叉树的操作

    目录 二叉树分类 二叉树性质 性质的使用 二叉树的遍历 前序遍历 中序遍历 后序遍历 层序遍历 求二叉树的节点数 求二叉树叶子结点个数 求二叉树的最大深度 二叉树的销毁 二叉树分类 满二叉树 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树.也可以理解为每一层的结点数都达到最大值的二叉树. 完全二叉树 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下.从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为

  • C语言 数据结构之中序二叉树实例详解

    C语言数据结构 中序二叉树 前言: 线索二叉树主要是为了解决查找结点的线性前驱与后继不方便的难题.它只增加了两个标志性域,就可以充分利用没有左或右孩子的结点的左右孩子的存储空间来存放该结点的线性前驱结点与线性后继结点.两个标志性域所占用的空间是极少的,所有充分利用了二叉链表中空闲存的储空间. 要实现线索二叉树,就必须定义二叉链表结点数据结构如下(定义请看代码): left leftTag data rightTag right 说明: 1.       leftTag=false时,表示left

  • C语言超详细讲解文件的操作

    目录 一.为什么使用文件 二.什么是文件 1.程序文件 2.数据文件 3.文件名 三.文件指针 四.文件的打开和关闭 五.文件的顺序读写 六.文件的随机读写 fseek ftell rewind 七.文件结束判定 一.为什么使用文件 当我们写一些项目的时候,我们应该要把写的数据存储起来.只有我们自己选择删除数据的时候,数据才不复存在.这就涉及到了数据的持久化的问题,为我们一般数据持久化的方法有,把数据存在磁盘文件.存放到数据库等方式.使用文件我们可以将数据直接存放在电脑的硬盘上,做到了数据的持久

  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    链接:C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树. 它的度可以为 1 也可以为 0,但是度最大为 2 . 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子. ② 二叉树的子树有左右之分,分别为左孩子和右孩子.次序不可颠倒,因此二叉树是有序树. 注意:对

  • C语言printf详细解析

     1.类型: 表示输出类型的格式字符 格式字符意义 a                                            浮点数.十六进制数字和p-计数法(C99 A                                            浮点数.十六进制数字和p-计数法(C99)c 输出单个字符d 以十进制形式输出带符号整数(正数不输出符号)e 以指数形式输出单.双精度实数E 以指数形式输出单.双精度实数f   以小数形式输出单.双精度实数 g 以%f%e中较

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • C语言数据结构之平衡二叉树(AVL树)实现方法示例

    本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

  • C语言数据结构之vector底层实现机制解析

    目录 一.vector底层实现机制刨析 二.vector的核心框架接口的模拟实现 1.vector的迭代器实现 2.reserve()扩容 3.尾插尾删(push_back(),pop_back()) 4.对insert()插入时迭代器失效刨析 5.对erase()数据删除时迭代器失效刨析 一.vector底层实现机制刨析 通过分析 vector 容器的源代码不难发现,它就是使用 3 个迭代器(可以理解成指针)来表示的: 其中statrt指向vector 容器对象的起始字节位置: finish指

随机推荐