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

目录
  • 前言:
  • Ⅰ. 定义二叉树
    • 0x00二叉树的概念(回顾)
    • 0x00定义二叉树
    • 0x01 手动创建二叉树
  • Ⅱ. 二叉树的遍历
    • 0x00关于遍历
    • 0x01二叉树前序遍历
    • 0x02二叉树中序遍历
    • 0x03二叉树后序遍历
    • 0x04层序遍历

前言:

学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习。等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式。

Ⅰ.  定义二叉树

0x00 二叉树的概念(回顾)

我们之前讲过二叉树的概念了,这里我们简单的回顾下二叉树的概念。

复习链接:C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

二叉树是什么?① 空树   ② 非空:根节点、根节点的左子树与根节点的又子树组成的。

解读:从概念中我们不难看出,二叉树的定义是递归式的。因此后续基本操作中,我们基本都是按照该概念来实现的!我们可以来看一下,我们不去看 A,我们来看 A 的左子树,把 B 看作为根节点,是不是一颗二叉树?

所以,我们可以通过采用递归的手法来玩二叉树。

0x00 定义二叉树

BinaryTree.h:

typedef int BTDataType;              

typedef struct BinaryTreeNode {
	struct BinaryTreeNode* left;       // 记录左节点
	struct BinaryTreeNode* right;      // 记录右节点
	BTDataType data;                   // 存储数据
} BTNode;                         

解读:

① 还是老规矩,我们创建一个二叉树的数据类型  BTDataType 。

② 由于是链式二叉树,根据二叉树的概念我们定义出 left 和 right 来分别记录根节点的左子树与根节点的右子树,再创建一个变量来存储节点中的数据即可。

③ 最后为了方便表达,我们将这个结构体 typedef 为 BTNode,因为 "struct BinaryTreeNode" 比较麻烦。

0x01 手动创建二叉树

在学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作。由于我们刚刚接触二叉树,为了能够先易后难地学习,我们手动创建一颗简单的二叉树来来方便大家学习。等二叉树结构了解后,后期我们会带着读者研究二叉树地真正的创建方式。

手动创建一颗二叉树(以上图为例来创建)

/* 创建新节点 */
BTNode* BuyNode(BTDataType x) {
	BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
	if (new_node == NULL) {
		printf("malloc failed!\n");
		exit(-1);
	}
	new_node->data = x;
	new_node->left = new_node->right = NULL;

	return new_node;
}

/* 手动创建二叉树 */
BTNode* CreateBinaryTree() {
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

int main(void)
{
	BTNode* root = CreateBinaryTree();
}

画图解析:

Ⅱ.  二叉树的遍历

0x00 关于遍历

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历,就是按照某种特定的规则,一次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。 访问节点所做的操作要看具体的应用问题。遍历是二叉树上最重要的运算之一,也是二叉树上进行其他运算的基础。

二叉树遍历(Traversal):沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。 按照规则,二叉树的遍历有:前序 / 中序 / 后序 的递归结构遍历。除了前序、中序和后续遍历外,我们还可以对二叉树进行层序遍历。

0x01 二叉树前序遍历

前序遍历(Preorder Traversal):访问根节点的操作发生在遍历其右子树之前。

即,首先访问根结点,然后遍历左子树,最后遍历右子树。

代码实现前序遍历:

(这里我们用 Ø 符号来表示 NULL)

/* 二叉树前序遍历 */
void PreOrder(BTNode* root) {
	/* 首先判断根是否为空,为空就返回 */
	if (root == NULL) {
		printf("Ø ");	// 暂时打印出来,便于观察
		return;
	}

	/* 走到这里说明不为空,根据前序遍历,先访问根节点 */
	printf("%c ", root->data);

	/* 然后遍历左子树(利用递归) */
	PreOrder(root->left);

	/* 最后遍历右子树(利用递归) */
	PreOrder(root->right);
}

解读:

① 首先判断根是否为空,如果根为空,则返回。这里为了表示,我们把空节点以 " Ø " 打印出来。

② 如果跟不为空,这说明有数据。由于是前序遍历(Preorder),前序遍历是先访问根节点,然后遍历左子树,最后再遍历右子树。所以,我们这里先要访问的是根节点,我们把根节点的数据打印出来。

③ 然后我们需要遍历左子树,这时我们利用递归就可以实现。将根节点 root 的左数 left 传入 PreOrder 函数(将其左树看作根),一直递归下去,直到碰到 root == NULL 则返回。

④ 最后,遍历完左子树后遍历右子树。利用递归,方法同上。

0x02 二叉树中序遍历

中序遍历(Inorder Traversal):访问根节点的操作发生在遍历其左右子树之中。

即,首先遍历左子树,然后访问根结点,最后遍历右子树。

/* 二叉树中序遍历 */
void InOrder(BTNode* root) {
	/* 首先判断根是否为空,为空就返回 */
	if (root == NULL) {
		printf("Ø ");  // 暂时打印出来,便于观察
		return;
	}

	/* 走到这里说明不为空,根据中序遍历,先遍历左子树 */
	InOrder(root->left);

	/* 然后访问根节点(利用递归) */
	printf("Ø ", root->data);

	/* 最后遍历右子树(利用递归) */
	InOrder(root->right);
}

解读:

① 首先判断根是否为空,如果根为空,则返回。

② 如果跟不为空,这说明有数据。由于是中序遍历(Inorder),中序遍历是先遍历左子树,然后访问根节点,最后遍历右子树。

0x03 二叉树后序遍历

后序遍历(Postorder Traversal):访问根节点的操作发生在遍历其左右子树之后。

即,首先遍历左子树,然后遍历右子树,最后访问根结点。

/* 二叉树后序遍历 */
void PostOrder(BTNode* root) {
	/* 首先判断根是否为空,为空就返回 */
	if (root == NULL) {
		printf("/ ");
		return;
	}

	/* 走到这里说明不为空,根据后序遍历,先遍历左子树(利用递归) */
	PostOrder(root->left);

	/* 然后遍历右子树(利用递归) */
	PostOrder(root->right);

	/* 最后访问根节点 */
	printf("%c ", root->data);
}

解读:

① 首先判断根是否为空,如果根为空,则返回。

② 如果跟不为空,这说明有数据。由于是后序遍历(Postorder),后序遍历是先遍历左子树,然后遍历右子树,最后访问根节点。

0x04 层序遍历

层序遍历(Level Traversal):设二叉树的根节点所在的层数为1的情况下,从二叉树的根节点出发,首先访问第1层的树根节点,然后再从左到右访问第2层上的节点。接着是第3层的节点……以此类推,自上而下、从左向右地逐层访问树的节点。

该如何实现层序遍历呢?

我们可以利用队列的性质来实现!

我们之前再讲过队列,这里你可以选择自己实现一个队列。如果不想实现就直接 CV 即可,因为我们这里重点要学的是层序遍历!

链接:C语言数据结构系列队列篇

Queue.h:

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

typedef int QueueDataType;

typedef struct QueueNode {
	struct QueueNode* next;
	QueueDataType data;
} QueueNode;

typedef struct Queue {
	QueueNode* pHead;
	QueueNode* pTail;
} Queue;

void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

Queue.c:

 #define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

/* 队列初始化 */
void QueueInit(Queue* pQ) {
	assert(pQ);
	pQ->pHead = pQ->pTail = NULL;
}

/* 销毁队列 */
void QueueDestroy(Queue* pQ) {
	assert(pQ);
	QueueNode* cur = pQ->pHead;
	while (cur != NULL) {
		QueueNode* cur_next = cur->next;
		free(cur);
		cur = cur_next;
	}
	pQ->pHead = pQ->pTail = NULL;
}

/* 判断队列是否为空 */
bool QueueIfEmpty(Queue* pQ) {
	assert(pQ);
	return pQ->pHead == NULL;
}

/* 入队 */
QueueNode* CreateNewNode(QueueDataType x) {
	QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
	if (new_node == NULL) {
		printf("malloc failed!\n");
		exit(-1);
	}
	new_node->data = x;
	new_node->next = NULL;

	return new_node;
}
void QueuePush(Queue* pQ, QueueDataType x) {
	assert(pQ);
	QueueNode* new_node = CreateNewNode(x);

	if (pQ->pHead == NULL) {
		pQ->pHead = pQ->pTail = new_node;
	}
	else {
		pQ->pTail->next = new_node;
		pQ->pTail = new_node;
	}
}

/* 出队 */
void QueuePop(Queue* pQ) {
	assert(pQ);
	assert(!QueueIfEmpty(pQ));

	QueueNode* save_next = pQ->pHead->next;
	free(pQ->pHead);
	pQ->pHead = save_next;

	if (pQ->pHead == NULL) {
		pQ->pTail = NULL;
	}
}

/* 返回队头数据 */
QueueDataType QueueFront(Queue* pQ) {
	assert(pQ);
	assert(!QueueIfEmpty(pQ));

	return pQ->pHead->data;
}

/* 返回队尾数据 */
QueueDataType QueueBack(Queue* pQ) {
	assert(pQ);
	assert(!QueueIfEmpty(pQ));

	return pQ->pTail->data;
}

/* 求队列大小 */
int QueueSize(Queue* pQ) {
	assert(pQ);
	int count = 0;
	QueueNode* cur = pQ->pHead;

	while (cur != NULL) {
		count++;
		cur = cur->next;
	}

	return count;
}

这里为了方便讲解 #include "展开" 的特点,我们把树的定义放到 test.c 中,并且在 test.c 里完成层序遍历。

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

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

//#include "Queue.h"  解决方案?

/* 创建新节点 */
BTNode* BuyNode(BTDataType x) {
	BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
	if (new_node == NULL) {
		printf("malloc failed!\n");
		exit(-1);
	}
	new_node->data = x;
	new_node->left = new_node->right = NULL;

	return new_node;
}

/* 手动创建二叉树 */
BTNode* CreateBinaryTree() {
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

由于是我们的数据类型是 BTNode,我们需要修改一下 Queue.h 的 QueueDataType,我们之前一直强调的 typedef 的好处,这里就显现出来了。我们只需要把 int 改成 BTNode 就可以了,而不需要改很多地方。

Queue.h:

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

typedef BTNode* QueueDataType;

typedef struct QueueNode {
	struct QueueNode* next;
	QueueDataType data;
} QueueNode;

typedef struct Queue {
	QueueNode* pHead;
	QueueNode* pTail;
} Queue;

void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

这时我们运行一下代码会出现一个问题,我们发现它报错了:

它说,缺少 " { " ,这明显是胡说八道的,咱编译器也没有那么只能,毕竟是也不是VS2077。

这里产生问题的原因是什么呢?

编译器原则:编译器认识 int,因为 int 是一个内置类型。但是 BTNode* 编译器并不认识,就需要 "往上面" 去找这个类型。这里显然往上找,是找不到它的定义的,所以编译器会报错。

如果你要用这个类型,你就需要先定义这个类型。test.c文件中 #include "Queue.h" ,相当于把这里的代码拷贝过去了。这时,由于BTNode*会在上面展开,导致找不到 BTNode*  。

我把 #include 移到 定义类型的代码 的后面,可以解决问题吗?

可以!遗憾的是只能解决这里 typedef BTNode* 的问题,还有 Queue.c 里的问题……

那我们该怎么做,能彻底解决呢?

解决方案:前置声明。 这样就不会带来问题了,满足了先声明后使用。

Queue.h (修改后):

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

// 前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QueueDataType;

typedef struct QueueNode {
	struct QueueNode* next;
	QueueDataType data;
} QueueNode;

typedef struct Queue {
	QueueNode* pHead;
	QueueNode* pTail;
} Queue;

void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

似乎有些扯远了,这块在《维生素C语言》中没有详细的说,所以这里还是需要说一下的。解决了这个报错的问题后,我们就可以正式开始写层序遍历了。

思路如下:

① 让根节点先入队。

② 记录当前队头后打印,并让队头出队,然后检测,如过孩子不为空就把孩子带进去。

(上一层节点出队时带入下一层节点入队)

③ 只要队列不为空就说明还没完。如果队列为空,说明下面最后一层没有节点,遍历结束。

注意事项:使用完队列后别忘了要销毁!

代码实现:

void BinaryTreeLevelOrder(BTNode* root) {
	if (root == NULL) {		// 判断根是否为空
		return;
	}

	Queue pQ;			// 建立队列
	QueueInit(&pQ);		// 初始化队列
	QueuePush(&pQ, root);	// 先让根进入队列
	while (!QueueIfEmpty(&pQ)) {	// 只要队列内还有元素,就进入循环
		BTNode* front = QueueFront(&pQ);	// 记录当前对头数据
		printf("%c ", front->data);  // 打印队头数据
		QueuePop(&pQ);	 // 当队头出队

		if (front->left != NULL) {		// 如果队头元素的左子树不为空
			QueuePush(&pQ, front->left);	// 让左子树进入队列
		}
		if (front->right != NULL) {		// 如果对头元素的右子树不为空
			QueuePush(&pQ, front->right);	// 让右子树进入队列
		}
	}

	QueueDestroy(&pQ);	 // 销毁队列
}

解读:

① 首先判断根是否为空,如果为空就没有必要往下走了。

② 建立和初始化队列后,首先让根节点进入队列。只要队列内还有元素存在(说明还没遍历完)就进入循环。每次循环进入后都记录一下当前队头,这里使用 QueueFront 取队头数据即可。之后打印对头的数据。

③ 打印完后让队头出队,随后判断它的左子树和右子树,如果不为空就允许它们进队。我们先判断 left,再判断 right,这样就可以做到一层一层从左往右走的效果了。

④ 最后使用完队列后,别忘了销毁队列!

参考资料:

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

笔者:王亦优

更新: 2022.1.12

勘误: 无

声明: 由于作者水平有限,本文有错误和不准确之处在所难免,本人也很想知道这些错误,恳望读者批评指正!

本篇完。

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

(0)

相关推荐

  • 统计C语言二叉树中叶子结点个数

    树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的,下面我们就用简单小栗子来简单说明关于统计C语言二叉树中叶子结点个数的方法吧 简单小栗子: #include<stdio.h> #include<stdlib.h>   typedef char ElemType; typedef struct BTNode {     ElemType data;     struct B

  • C语言实现线索二叉树的前中后创建和遍历详解

    目录 1.结构 1.1初始化tag 2.基本操作 2.1先序创建二叉树 2.2.先序线索化 2.2.1.先序遍历 2.3.中序线索化 2.3.1中序遍历 2.4.后序线索化 2.4.1后序遍历 总结 1.结构 #include<stdio.h> #include<stdlib.h> #define false 0 #define true 1 using namespace std; typedef struct BTnode{ int data; struct BTnode *l

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

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

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

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

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

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

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • C语言数据结构之二叉链表创建二叉树

    目录 一.思想(先序思想创建) 二.创建二叉树 (1)传一级参数方法 (2)传二级参数方法 一.思想(先序思想创建) 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右

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

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

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

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

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

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

  • C语言数据结构系列队列篇

    目录 一.队列(Queue) 0x00队列的概念 0x01队列的结构 二.队列的定义 0x00链式队列 0x02 接口函数 三.队列的实现 0x00队列初始化(QueueInit) 0x01销毁队列(QueueDestroy) 0x02判断队列是否为空(HeapIsEmpty) 0x03入队(QueuePush) 0x04出队(QueuePop) 0x05 返回队头数据(QueueFront) 0x06 返回队尾数据(QueueBack) 0x07 求队列大小(QueueSize) 0x08完整

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

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

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

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

  • C语言数据结构系列之树的概念结构和常见表示方法

    0x00 树的概念 树是一种非线性的数据结构,它是由 n(n >= 0)个有限节点组成的一个具有层次关系的集合. 那么为什么叫 "树" 呢? 我们之所以把它成为 "树",是因为它很像我们现实生活中的树.只是它是倒过来的,根朝上叶子朝下. 0x01 树的结构 ① 有一个特殊的节点,成为根节点,根节点不存在前驱节点. ② 除根节点外,其余节点被分成 M(M>0) 个互不相交的集合 T1.T2.…….Tm,期中没一个集合 Ti(1 <= i <=

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

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

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

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

随机推荐