【数据结构】链式二叉树的实现(一)

简介: 【数据结构】链式二叉树的实现(一)

作者:一个喜欢猫咪的的程序员

专栏:《数据结构》

喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》

目录

1.二叉树的概念及结构

1.1二叉树的概念

1.2二叉树的类型分类:

1.3二叉树的结构

2.接口实现及其具体细节的讲解

2.1知识铺垫:二叉树的遍历方式

2.2前中后序遍历代码实现:

2.2.1前序遍历(PreOrder):

2.2.2中序遍历(InOrder):

2.2.3后序遍历(PostOrder):

2.3二叉树的节点个数和叶节点个数:

2.3.1二叉树节点的个数(TreeSize):

2.3.2二叉树叶子节点的个数(TreeLeafSize)

2.4树的高度及二叉树第K层的节点个数

2.4.1树的高度(TreeHeight):

2.4.2二叉树第K层的节点个数(TreeLevelSize):

2.5二叉树查找值为x的节点(TreeFind):

2.6层序遍历(LevelOrder):

2.7判断二叉树是否是完全二叉树及二叉树销毁

2.7.1判断二叉树是否是完全二叉树(BinaryTreeComplete)

2.7.2二叉树销毁(TreeDestory):

3.完整代码:

3.1test.c文件(二叉树实现):3.2Queue.h文件:

3.3Queue.c文件:


1.二叉树的概念及结构


1.1二叉树的概念


二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分。

1.2二叉树的类型分类:

二叉树分为两种:

  • 完全二叉树
  • 满二叉树

1.3二叉树的结构

由上图可知,二叉树是一个节点root,链接着一个左节点left和一个右节点right

定义二叉树的结构:

typedef int BTDataType;
typedef struct BinaryTreeNode
{//二叉树的结构
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

创建二叉树节点:

BTNode* BuyBTNode(BTDataType x)
{
  BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->left = newnode->right = NULL;
  return newnode;
}

在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树.

这里手动链接各方便大家理解后面的操作,以及对测试用例的修改来测试接口函数是否正确符合要求.

//构造二叉树
  BTNode* n1 = BuyBTNode(1);
  BTNode* n2 = BuyBTNode(2);
  BTNode* n3 = BuyBTNode(3);
  BTNode* n4 = BuyBTNode(4);
  BTNode* n5 = BuyBTNode(5);
  BTNode* n6 = BuyBTNode(6);
  BTNode* n7 = BuyBTNode(7);
  n1->left = n2;//链接二叉树
  n1->right = n4;
  n2->left = n3;
  n4->left = n5;
  n4->right = n6;
  n3->left = n7;

2.接口实现及其具体细节的讲解


2.1知识铺垫:二叉树的遍历方式

遍历顺序分为4种:(root为根节点)

  • 前序遍历:root  左子树 右子树
  • 中序遍历:左子树 root  右子树
  • 后序遍历:左子树 右子树  root
  • 层序遍历:一层一层遍历(后面会单独讲)

如:前序遍历是每颗子树都先遍历root节点,再遍历左子树,最后在遍历右子树。


以下图为例:我们来了解一下前序遍历的顺序。


先root节点出1,然后是1的左子树(以2为根节点的子树)出2,再到2的左子树出3,再出3的左子树NULL,然后返回3的位置再走3的右子树然后出NULL,再返回2走2的右子树出NULL再返回到1的位置,1的右子树也是如此,以此类推。

还是以上图为例子,前中后序的顺序如下:


2.2前中后序遍历代码实现:

2.2.1前序遍历(PreOrder):

前序遍历的遍历顺序:root  左子树 右子树

将一个二叉树分为根节点、左子树和右子树,它的子树也是可以这样分。

这样的操作是重复的,因此可以看成一个递归的底层过程。

只看最下面的部分的话


  • 当root为NULL时,打印NULL。
  • 当root不为NULL时,打印root->data的值。

只看最顶部 1 2 4的时候。


先打印root(1),然后递归找到左子树(2)打印2,再递归找到右子树(4)打印4。

从局部映射到整体后,函数递归写法就是如此。


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

2.2.2中序遍历(InOrder):

中序遍历与前序遍历不相同的地方就是在打印的先后顺序不同

因此递归的前后顺序随着改变。

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

2.2.3后序遍历(PostOrder):

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


2.3二叉树的节点个数和叶节点个数:

2.3.1二叉树节点的个数(TreeSize):

二叉树节点的个数,可以看成左子树的节点个数+右子树的节点个数+1(根节点)。

遇到NULL返回0。


当只有1个节点时,它也有左子树(NULL)和右子树(NULL)。


当树为 1 2 4时,1的左子树为2,右子树为4。那2和4的左子树和右子树又是相当于只有一个节点的情况。


...


扩张到n个节点的情况下,就是递归不断向下找并且返回的过程。

// 二叉树节点个数
int TreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  return TreeSize(root->left) + TreeSize(root->right) + 1;
}

2.3.2二叉树叶子节点的个数(TreeLeafSize)

计算叶子结点的个数,又跟就是二叉树节点个数不太一样

叶节点代表它没有左右节点了,也就是左右节点皆为NULL

  • 当左右左右节点皆为NULL时返回1
  • 叶节点数等于左子树的叶子个数+右子树的叶子个数
// 二叉树叶子节点个数
int TreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left == NULL && root->right == NULL)
    return 1;
  return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}


目录
打赏
0
0
0
0
1
分享
相关文章
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
50 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
49 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
136 4
|
3月前
|
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
224 8
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
356 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
58 1
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
145 77