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


    前言:
            前面我们已经提到过树、二叉树的概念及结构、堆排序、Top-k问题等的知识点,这篇文章我们来详解一下二叉树的链式结构等问题。

    💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥

    ✨✨专栏:http://t.csdn.cn/oXkBa

    ⛳⛳本篇内容:c语言数据结构--二叉树的遍历以及功能实现

    目录

    一.链式二叉树存储的概念

    二.链式二叉树结构的实现

    2.1 前置说明

    2.2二叉树的遍历

    前序遍历(Preorder Traversal)

    中序遍历(Inorder Traversal)

    后续遍历(Postorder Traversal)

    层序遍历(LevelOrder)

    2.3二叉树功能的实现

    二叉树结构定义(struct BinaryTreeNode)

    二叉树节点的创建(CreatBinaryTree)

    二叉树的前序遍历函数(PrevOrder)

    二叉树的中序遍历函数(InOrder)

    二叉树的后序遍历函数(PostOrder)

    统计二叉树节点个数(BTreeSize)

    求出叶子节点的数量(BTreeLeafSize)

    求二叉树的高度(BTreeHeight)

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

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

    二叉树的层序遍历(LevelOrder)

    判断一棵树是否为完全二叉树(BinaryTreeComplete)


    一.链式二叉树存储的概念

            二叉树的链式存储结构是指: 用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。
            
            通常的方法是链表中每个结点由三个域组成, 数据域和左右指针域,左右指针分别用来给出该结点 左孩子和右孩子所在的链结点的存储地址
            
            链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面课程学到高阶数据结构如红黑树等会用到三叉链。

    二.链式二叉树结构的实现

    2.1 前置说明

            在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。
            由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,
            此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式。
    1. typedef int BTDataType;
    2. typedef struct BinaryTreeNode
    3. {
    4. BTDataType data;
    5. struct BinaryTreeNode* left;
    6. struct BinaryTreeNode* right;
    7. }BTNode;
    8. BTNode* BuyNode(BTDataType x)
    9. {
    10. BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    11. if (node == NULL)
    12. {
    13. perror("malloc fail");
    14. return NULL;
    15. }
    16. node->data = x;
    17. node->left = NULL;
    18. node->right = NULL;
    19. return node;
    20. }
    21. BTNode* CreatBinaryTree()
    22. {
    23. BTNode* node1 = BuyNode(1);
    24. BTNode* node2 = BuyNode(2);
    25. BTNode* node3 = BuyNode(3);
    26. BTNode* node4 = BuyNode(4);
    27. BTNode* node5 = BuyNode(5);
    28. BTNode* node6 = BuyNode(6);
    29. node1->left = node2;
    30. node1->right = node4;
    31. node2->left = node3;
    32. node4->left = node5;
    33. node4->right = node6;
    34. return node1;
    35. }
    注意:上述代码并不是创建二叉树的方式,真正创建二叉树方式后序详解重点讲解。
    再看二叉树基本操作前,再回顾下二叉树的概念, 二叉树是:
    1. 空树
    2. 非空:根节点,根节点的左子树、根节点的右子树组成的。
            从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。

    2.2二叉树的遍历

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

    以先序遍历为例子:

    前序遍历(Preorder Traversal)

            亦称先序遍历,访问根结点的操作发生在遍历其左右子树之前.

    中序遍历(Inorder Traversal)

    访问根结点的操作发生在遍历其左右子树之中(间)

    后续遍历(Postorder Traversal)

    访问根结点的操作发生在遍历其左右子树之后.

            由于被访问的结点必是某子树的根, 所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历

    层序遍历(LevelOrder)

    层序遍历 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

    2.3二叉树功能的实现

    二叉树结构定义(struct BinaryTreeNode)

    代码实现:

    1. typedef int BTDataType;
    2. typedef struct BinaryTreeNode
    3. {
    4. BTDataType data;
    5. struct BinaryTreeNode* left;
    6. struct BinaryTreeNode* right;
    7. }BTNode;

    二叉树节点的创建(CreatBinaryTree)
    1. BTNode* BuyNode(BTDataType x)//树中一个节点的创建
    2. {
    3. BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    4. if (node == NULL)
    5. {
    6. perror("malloc fail");
    7. return NULL;
    8. }
    9. node->data = x;
    10. node->left = NULL;
    11. node->right = NULL;
    12. return node;
    13. }
    14. BTNode* CreatBinaryTree()//树的构造
    15. {
    16. BTNode* node1 = BuyNode(1);
    17. BTNode* node2 = BuyNode(2);
    18. BTNode* node3 = BuyNode(3);
    19. BTNode* node4 = BuyNode(4);
    20. BTNode* node5 = BuyNode(5);
    21. BTNode* node6 = BuyNode(6);
    22. node1->left = node2;
    23. node1->right = node4;
    24. node2->left = node3;
    25. node4->left = node5;
    26. node4->right = node6;
    27. return node1;
    28. }

    二叉树的前序遍历函数(PrevOrder)

            递归不可能一直调用函数,因为这个过程一直在创建栈帧,即使栈再大,也会栈溢出。所以肯定会回归,回归的本质就是销毁栈帧。

    递归是由两个部分构成:

    1.子问题 

    2.返回条件

    图解:

    代码实现:

    1. void PrevOrder(BTNode* root)
    2. {
    3. if (root == NULL)
    4. {
    5. printf("N ");
    6. return;
    7. }
    8. printf("%d ", root->data);
    9. PrevOrder(root->left);
    10. PrevOrder(root->right);
    11. }
    二叉树的中序遍历函数(InOrder)

    绘图:

    1. void InOrder(BTNode* root)
    2. {
    3. if (root == NULL)
    4. {
    5. printf("N ");
    6. return;
    7. }
    8. InOrder(root->left);
    9. printf("%d ", root->data);
    10. InOrder(root->right);
    11. }

    二叉树的后序遍历函数(PostOrder)

            跟前中序的思路相差不大,这里就不绘图了。

    代码实现:

    1. void PostOrder(BTNode* root)
    2. {
    3. if (root == NULL)
    4. {
    5. printf("N ");
    6. return;
    7. }
    8. PostOrder(root->left);
    9. PostOrder(root->right);
    10. printf("%d ", root->data);
    11. }

    统计二叉树节点个数(BTreeSize)

    画出递归展开图:

    1. int BTreeSize(BTNode* root)
    2. {
    3. //写法一
    4. if (root == NULL)
    5. return 0;
    6. return BTreeSize(root->left) + BTreeSize(root->right) + 1;
    7. //写法二
    8. return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
    9. }

    求出叶子节点的数量(BTreeLeafSize)

            进入函数首先判断根节点是否为空,为空就直接返回0,说明树为空,直接返回叶子节点数量为0。

            接下来,检查当前的节点是叶子节点还是分支节点,若代码检查当前节点是否为叶子节点,即该节点的左子节点和右子节点都为空。如果是叶子节点,返回叶子节点数量为1。

            如果当前节点为分支节点,则继续调用该函数,计算左子树和右子树的叶子节点数量,并将它们相加,得到当前节点为根的子树的叶子节点数量。

            最后,函数返回左子树和右子树叶子节点数量的和,即整个二叉树的叶子节点数量。

    1. int BTreeLeafSize(BTNode* root)//接受一个指向二叉树节点的指针root作为参数
    2. {
    3. if (root == NULL)//代码检查根节点是否为空
    4. {
    5. return 0;
    6. }
    7. if ( root->left==NULL &&root->right==NULL)
    8. {
    9. return 1;
    10. }
    11. return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
    12. }

    求二叉树的高度(BTreeHeight)

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

    方案一: 

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

    1. int BTreeHeight(BTNode* root)
    2. {
    3. if (root == NULL)
    4. {
    5. return 0;
    6. }
    7. return BTreeHeight(root->left) > BTreeHeight(root->right) ?
    8. BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1;
    9. }

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

    画图理解:

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

    1. 分解(Divide):将原问题划分为若干个规模较小的子问题。这一步通常在递归的过程中进行,直到问题足够简单,可以直接求解

    2. 解决(Conquer):递归地解决子问题。对于每个子问题,如果它的规模足够小,可以直接求解;否则,继续递归地将子问题划分为更小的子问题。

    3. 合并(Combine):将子问题的解合并得到原问题的解。这一步通常在递归的回溯过程中进行。

    代码实现: 

    1. int BTreeHeight(BTNode* root)
    2. {
    3. if (root == NULL)
    4. {
    5. return 0;
    6. }
    7. int h = 0;
    8. if (BTreeHeight(root->left) > BTreeHeight(root->right))
    9. {
    10. h = BTreeHeight(root->left) + 1;
    11. }
    12. else
    13. {
    14. h = BTreeHeight(root->right) + 1;
    15. }
    16. return h;
    17. }

    力扣执行:

    方案二:

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

    1. int BTreeHeight(BTNode* root)
    2. {
    3. if (root == NULL)
    4. {
    5. return 0;
    6. }
    7. int leftHeight = BTreeHeight(root->left);
    8. int rightHeight = BTreeHeight(root->right);
    9. return leftHeight > rightHeight ? leftHeight + 1 : rightHeight+ 1;
    10. }

    力扣执行:

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

    子问题:

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

    结束条件:

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

    代码实现:

    1. int BTreeLevelKSize(BTNode* root, int k)
    2. {
    3. assert(k > 0);
    4. if (root == NULL)
    5. return 0;
    6. if (k == 1)
    7. return 1;
    8. return BTreeLevelKSize(root->left, k - 1)
    9. + BTreeLevelKSize(root->right, k - 1);
    10. }

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

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

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

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

    画出递归展开图:

    代码实现:

    1. BTNode* BTreeFind(BTNode* root,BTDataType x)
    2. {
    3. if (root == NULL)
    4. return NULL;
    5. if (root->data == x)
    6. return root;
    7. int ret1 = BTreeFind(root->left, x);
    8. if (ret1)
    9. return ret1;
    10. int ret2 = BTreeFind(root->right, x);
    11. if (ret2)
    12. return ret2;
    13. return NULL;
    14. }

    二叉树的层序遍历(LevelOrder)

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

    1. typedef struct BTNode* QDataType;//注意这个地方的类型
    2. typedef struct QueueNode
    3. {
    4. QDataType data;
    5. struct QueueNode* next;
    6. }QNode;
    7. typedef struct Queue
    8. {
    9. QNode* phead;
    10. QNode* ptail;
    11. int size;
    12. }Queue;//表示队列整体,一个是出数据,一个是入数据.
    13. typedef int BTDataType;
    14. typedef struct BinaryTreeNode
    15. {
    16. BTDataType data;
    17. struct BinaryTreeNode* left;
    18. struct BinaryTreeNode* right;
    19. }BTNode;

    画处解析图:

    队列:先进先出

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

    解析:  其实就是由原来的队列里面data的int类型,变成了struct BTreeNode* 类型的指针,指向了这个数节点。

    代码实现: 

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

    二叉树的销毁(BTDestroy)

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

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

     画图:

    1. void BTDestroy(BTNode* root)
    2. {
    3. if (root == NULL)
    4. {
    5. return NULL;
    6. }
    7. BTDestroy(root->left);
    8. BTDestroy(root->right);
    9. free(root);
    10. }

    判断一棵树是否为完全二叉树(BinaryTreeComplete)

    非完全二叉树

    完全二叉树

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

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

     代码实现:

    1. bool BTreeComplete(BTNode* root)
    2. {
    3. Queue q;
    4. QueueInit(&q);
    5. if (root)
    6. QueuePush(&q,root);
    7. while (!QueueEmpty(&q))//遍历树直到找到第一个空节点
    8. {
    9. BTNode* front= QueueFront(&q);
    10. QueuePop(&q);
    11. //遇到空就跳出
    12. if (front == NULL)
    13. {
    14. break;
    15. }
    16. QueuePush(&q, front->left);
    17. QueuePush(&q, front->right);
    18. }
    19. // 检查后面的节点有没有非空
    20. // 有非空,不是完全二叉树
    21. while (!QueueEmpty(&q))//由于中途遇到空,所以跳出循环,这次循环是为了检查后面元素是否为空
    22. {
    23. BTNode* front = QueueFront(&q);
    24. QueuePop(&q);
    25. if (front)
    26. {
    27. QueueDestroy(&q);
    28. return false;
    29. }
    30. }
    31. QueueDestroy(&q);
    32. return true;
    33. }

    执行: 

     

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

  • 相关阅读:
    Spring的事务
    Mac下使用Docker快速布署FastGPT实现AI私有知识库
    SQL Server教程 - T-SQL-索引(INDEX)
    C++入门-day02
    mock 点击图片显示Too big of an image!
    利用JDBC及Servlet实现对信息录入注册功能的实现
    小程序隐私保护授权处理方式之弹窗组件
    【LeetCode】49. 字母异位词分组
    用FIR滤波器设计数字微分器和数字希尔伯特变换器
    网络代理的多重应用与安全保障
  • 原文地址:https://blog.csdn.net/weixin_65186652/article/details/133894482