【数据结构与算法】二叉树的综合运用--1

简介: 【数据结构与算法】二叉树的综合运用--1

一,层序遍历算法

       二叉树的层序遍历是一层一层的从左到右遍历,现在问题是二叉树不支持随机访问,因此,我们需要借助其它结构来实现这一功能。通常,对于这种遍历算法我们要借助队结构的概念。


       补充:树的层序遍历也叫做广度优先遍历,而广度优先遍历通常要借助队列的结构实现。


1-1,队列结构的设立

       队列的结构相信大家都已非常熟悉了,如果队列结构不清楚的可以观看本人以前讲解队列的文章,本文在这里就不做过多说明了。我们可定义一个头文件,将队列的基础算法写进去,其中,要注意的是队列中的元素是树中的结点,因为往队列中装数据装的是树的结点,不可直接装树结点的数据,否则设置此结构几乎没用,下文分析时会详细说明,在这里我们只需先构造队列中的基础算法即可。如下:


#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef struct Tree DataType;
typedef struct Node {
  DataType* val;
  struct Node* next;
}Node;
typedef struct Queue {
  Node* head;
  Node* tail;
}Queue;
void QueueInit(Queue* Q) {
  Q->head = Q->tail = 0;
}
void QueuePush(Queue* Q, DataType* x) {
  Node* node = (Node*)malloc(sizeof(Node));
  if (!node) {
  return;
  }
  node->val = x;
  node->next = 0;
  if (!Q->head) {
  Q->head = Q->tail = node;
  }
  else {
  Q->tail->next = node;
  Q->tail = node;
  }
}
void QueuePop(Queue* Q) {
  if (!Q->head) {
  return;
  }
  Node* node = Q->head->next;
  free(Q->head);
  Q->head = node;
}
bool QueueEmpty(Queue* Q) {
  return Q->head == NULL;
}
void QueueDestroy(Queue* Q) {
  if (!Q->head) {
  return;
  }
  Node* node = Q->head->next;
  while (Q->head != Q->tail) {
  free(Q->head);
  Q->head = node;
  node = node->next;
  }
  free(Q->head);
  free(Q);
}


1-2,逻辑分析

       队列结构设置完后,我们要考虑的是如何将每一层的数据从左到右放入队列中。如果直接将树结点中的数据直接导入,很显然,这跟用不用队列结构没多大关系,相当于直接层序遍历二叉树。因此,我们要考虑将树中结点导入,然后,利用结点间相连问题进行层序导入队列中。具体步骤和说明如下:


       首先,要将根结点导入队列,然后输出队列中首结点的数据,并先将此结点的左孩子导入进队列,再将右孩子导入进队列,最后删除首结点,以此类推,不断进行循环,当队列为空时相当于已层序遍历完整个二叉树。至于原因是因为我们输出首结点的元素后删除了首结点,所以当进行下一次循环将首结点的左右孩子导入时,相当于从树的下一层开始,从左到右导入数据。


代码如下:


void LevelOrder(Tree* root) {
  //空树直接退出
  if (!root) {
  return;
  }
  //建立队列结构
  Queue* Q = (Queue*)malloc(sizeof(Queue));
  QueueInit(Q);
  //先把根结点推入进去
  QueuePush(Q, root);
  //进行遍历,先将数据输出,导入队列左右孩子后要出队,即删除,当队为空时已遍历完。
  while (!QueueEmpty(Q)) {
  fprintf(stdout, "%d ", Q->head->val->val);
  if (Q->head->val->leftchild) {
    QueuePush(Q, Q->head->val->leftchild);
  }
  if (Q->head->val->rightchild) {
    QueuePush(Q, Q->head->val->rightchild);
  }
  QueuePop(Q);
  }
}

算法演示:


//设定队列结构和必要的头文件
#include "Queue.h"
typedef struct Tree {
  int val;//数据
  struct Tree* leftchild;//左孩子结点
  struct Tree* rightchild;//右孩子结点
}Tree;
//创建二叉树数据为x的结点
Tree* CreatNode(int x) {
  Tree* node = (Tree*)malloc(sizeof(Tree));
  node->val = x;
  node->leftchild = 0;
  node->rightchild = 0;
  return node;
}
//二叉树的销毁
void TreeDestroy(Tree* root) {
  if (!root) {
  return;
  }
  TreeDestroy(root->leftchild);
  TreeDestroy(root->rightchild);
  free(root);
}
//层序遍历算法(广度优先遍历)
void LevelOrder(Tree* root) {
  //空树直接退出
  if (!root) {
  return;
  }
  //建立队列结构
  Queue* Q = (Queue*)malloc(sizeof(Queue));
  QueueInit(Q);
  //先把根结点推入进去
  QueuePush(Q, root);
  //进行遍历,先将数据输出,导入队列左右孩子后要出队,即删除,当队为空时已遍历完。
  while (!QueueEmpty(Q)) {
  fprintf(stdout, "%d ", Q->head->val->val);
  if (Q->head->val->leftchild) {
    QueuePush(Q, Q->head->val->leftchild);
  }
  if (Q->head->val->rightchild) {
    QueuePush(Q, Q->head->val->rightchild);
  }
  QueuePop(Q);
  }
}
int main()
{
  //手动构建二叉树
  Tree* node1 = CreatNode(1);
  Tree* node2 = CreatNode(2);
  Tree* node3 = CreatNode(3);
  Tree* node4 = CreatNode(4);
  Tree* node5 = CreatNode(5);
  Tree* node6 = CreatNode(6);
  Tree* node7 = CreatNode(7);
  Tree* node8 = CreatNode(8);
  Tree* node9 = CreatNode(9);
  Tree* node10 = CreatNode(10);
  Tree* node11 = CreatNode(11);
  Tree* node12 = CreatNode(12);
  Tree* node13 = CreatNode(13);
  Tree* node14 = CreatNode(14);
  Tree* node15 = CreatNode(15);
  //结点的连接
  node1->leftchild = node2;
  node1->rightchild = node4;
  node2->leftchild = node3;
  node4->leftchild = node5;
  node4->rightchild = node6;
  node2->rightchild = node7;
  node3->leftchild = node8;
  node3->rightchild = node9;
  node7->leftchild = node10;
  node7->rightchild = node11;
  node5->leftchild = node12;
  node5->rightchild = node13;
  node6->leftchild = node14;
  node6->rightchild = node15;
  LevelOrder(node1);
  TreeDestroy(node1);
  return 0;
}


接下来我们用经典题型来进行解说二叉树的运用。


【数据结构与算法】二叉树的综合运用--2https://developer.aliyun.com/article/1424486?spm=a2c6h.13148508.setting.26.214f4f0e2QJGOK

目录
打赏
0
0
0
0
1
分享
相关文章
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
81 4
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
58 5
|
1月前
|
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
131 8
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
41 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
31 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
35 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
31 1
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
29 1
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
下一篇
DataWorks
AI助理

阿里云 AI 助理已上线!

快来体验一下吧。