【数据结构与算法】two X 树的遍历以及功能实现(下)

简介: 【数据结构与算法】two X 树的遍历以及功能实现(下)
求二叉树的高度(BTreeHeight)

先比较一下以下的哪种代码更优:

方案一:

      在递归调用BTreeHeight函数之后,并没有对返回值进行保存和比较,而是直接返回了当前节点的左子树和右子树的高度中较大的一个加1。这样的实现虽然能够得到正确的结果,但是效率较低。因为在计算左子树的高度和右子树的高度时,每次都会重复递归调用 BTreeHeight函数

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

为了更好地理解方案一的解释,这里写出一个不用三目运算符,但是等价于上述代码的代码

画图理解:

这里其实用到的是分治算法,通常分为三个步骤:

  1. 分解(Divide):将原问题划分为若干个规模较小的子问题。这一步通常在递归的过程中进行,直到问题足够简单,可以直接求解
  2. 解决(Conquer):递归地解决子问题。对于每个子问题,如果它的规模足够小,可以直接求解;否则,继续递归地将子问题划分为更小的子问题。
  3. 合并(Combine):将子问题的解合并得到原问题的解。这一步通常在递归的回溯过程中进行。

89b3c3b2c2e7416bbd7651dc5b2e17be.png

代码实现:

int BTreeHeight(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int h = 0;
  if (BTreeHeight(root->left) > BTreeHeight(root->right))
  {
      h = BTreeHeight(root->left) + 1;
  }
  else
  {
    h = BTreeHeight(root->right) + 1;
  }
  return h;
}


力扣执行:

4147ec23044c4aa98ac67e85d8344300.png

方案二:

c9382f982ef04d588a585f1ef55fe95b.png

使用了两个变量leftHeightrightHeight分别保存了左子树和右子树的高度。通过递归调用BTreeHeight函数分别计算左子树和右子树的高度,并将结果保存在这两个变量中。然后比较leftHeightrightHeight的值,将较大值加1作为当前节点的高度返回。这样的实现避免了重复计算,提高了效率。

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


力扣执行:

f72d670ade4340d99a7268dcbd8b6808.png

二叉树第k层节点个数(BTreeLevelKSize)

子问题:

转换成左子树的第k-1层和右子树的右子树的第k-1层

结束条件:

  • k == 1且节点不为空
  • 节点为空

eedde8dc750e4df3909764c298de00ee.png

代码实现:

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


二叉树查找值为x的节点(BTreeFind)

       思路:就如果根节点为空,直接返回NULL,如果找到了就返回x这个节点的地址。

从根节点开始遍历,先从左子树开始找,继续循环上述思路,如果节点不为NULL,但是节点不为x,那也是返回NULL,注意这个NULL是返回上一层的,谁调用它就返回给此函数。之后找右子树,也是一样的思路。

      左子树整体找完之后,从右子树整体开始找,重复上述过程。特别强调一个点,return返回的时候不会return到最外层,一定是逐层逐层返回的,没有跳跃的一个过程

画出递归展开图:

16fef971fff142c988eecbd1adc452f4.png

代码实现:

BTNode* BTreeFind(BTNode* root,BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  int ret1 = BTreeFind(root->left, x);
  if (ret1)
    return ret1;
  int ret2 = BTreeFind(root->right, x);
  if (ret2)
    return ret2;
  return NULL;
}


二叉树的层序遍历(LevelOrder)

层序遍历是用队列实现的,所以要使用队列的结构体,以下的结构体都要用到

typedef struct BTNode* QDataType;//注意这个地方的类型
typedef struct QueueNode
{ 
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;//表示队列整体,一个是出数据,一个是入数据.
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;


画处解析图:

队列:先进先出

核心思路:上一层出时带下一层进队列

f90a027510264a93a139c3d9c7857a6e.png

画处解析图:

队列:先进先出

核心思路:上一层出时带下一层进队列

980ac4df898a47a8a6b16d99c6d5ecb4.png

代码实现:

void LevelOrder(BTNode* root)
{
  Queue q;//在函数内部,定义了一个队列q,并通过调用QueueInit函数对队列进行初始化。
  QueueInit(&q);
    //如果根节点root不为空,将根节点入队,即调用QueuePush函数将root指针插入到队列q中。
  if (root)
    QueuePush(&q,root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);//首先通过调用QueueFront函数获取队列q的队首元素,并将其赋值给指针变量front
    QueuePop(&q);//调用QueuePop函数将队首元素出队
    printf("%d ", front->data);//通过printf函数打印front指向的节点的数据值
    //如果front的左子节点不为空,将左子节点入队,
    //即调用QueuePush函数将front->left指针插入到队列q中   
        if (front->left)
      QueuePush(&q, front->left);//后面这个参数是一个值,不是地址
    //如果front的右子节点不为空,将右子节点入队,
    //即调用QueuePush函数将front->right指针插入到队列q中。
    if (front->right)
      QueuePush(&q, front->right);//后面这个参数是一个值,不是地址
//循环体内的操作完成后,继续下一次循环,直到队列q为空。
  }
//最后,打印换行符表示层序遍历结束,
//并调用QueueDestroy函数销毁队列q,释放内存。
  printf("\n");
  QueueDestroy(&q);
}


二叉树的销毁(BTDestroy)

      解析:要先判断根节点本身是否为空,为空就不销毁,返回。

       销毁是用到后序遍历的,因为中途删掉了根节点,那么左右指针就找不到了,所以后序遍历适合实现二叉树的销毁。

画图:


void BTDestroy(BTNode* root)
{
  if (root == NULL)
  {
    return NULL;
  }
  BTDestroy(root->left);
  BTDestroy(root->right);
  free(root);
}
判断一棵树是否为完全二叉树(BinaryTreeComplete)

非完全二叉树

7c3a8ef8dc2d40709c33e4ead8cd438d.png

完全二叉树

       思路一样的就不画动图了,只要前面遇到一次空,立即跳出循环,停止插入元素,然后检查后面的元素是否为空,后面全是空就是完全二叉树了。

ade67aa8f2ce4b2098c02dc11b6ce878.png

以下这个二叉树就不是完全二叉树了

c09506d68e684be0924ac2700681dee6.png

代码实现:

bool BTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q,root);
  while (!QueueEmpty(&q))//遍历树直到找到第一个空节点
  {
  BTNode* front= QueueFront(&q);
  QueuePop(&q);
  //遇到空就跳出
  if (front == NULL)
  {
    break;
  }
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 检查后面的节点有没有非空
  // 有非空,不是完全二叉树
  while (!QueueEmpty(&q))//由于中途遇到空,所以跳出循环,这次循环是为了检查后面元素是否为空
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front)
    {
      QueueDestroy(&q);
      return false;
    } 
  }
  QueueDestroy(&q);
  return true;
}


执行:

b243a2d5ebd54dfc8d5305d68bd6ba98.png

  本篇到此结束,感谢来访!

相关文章
|
1月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
49 0
|
23天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
44 5
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
75 16
|
1月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
1月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
58 5
|
1月前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
37 2
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
41 0
|
1月前
|
算法
数据结构之文件系统模拟(树数据结构)
本文介绍了文件系统模拟及其核心概念,包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境,模拟文件的创建、删除、移动、搜索等操作,展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现,包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性,如灵活性高但节点移除效率低等问题。
50 0
|
2月前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
38 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
178 9
下一篇
DataWorks