首页 > 编程语言 >算法基础 -二叉树遍历

算法基础 -二叉树遍历

时间：2025-01-07 14:30:52浏览次数：3  
标签：lchild 遍历 BiTree BiTNode 算法 二叉树 rchild 节点

文章目录

1. 二叉树概念

二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树的特点是：

每个节点都包含一个数据元素和两个指向其他节点的指针（或链接），分别指向左子节点和右子节点。

二叉树的一些常见类型包括：

  • 完全二叉树：除了最后一层外，每一层都被完全填满，并且最后一层的节点尽可能地集中在左侧。
  • 满二叉树：所有层都被完全填满。
  • 平衡二叉树：任何两个子树的高度差不超过1，这种树可以保证操作的平衡性，常用于数据库索引。
  • 二叉搜索树（BST）：左子树的所有节点的值小于当前节点的值，右子树的所有节点的值大于当前节点的值。

二叉树的常见操作包括：

  • 插入：在树中插入一个新的节点，同时保持二叉树的性质。
  • 删除：从树中删除一个节点，同时保持二叉树的性质。
  • 搜索：在树中查找一个特定的值。
  • 遍历：按照特定的顺序访问树中的所有节点，常见的遍历方式有：
    • 前序遍历：先访问根节点，然后左子树，最后右子树。
    • 中序遍历：先访问左子树，然后根节点，最后右子树。
    • 后序遍历：先访问左子树，然后右子树，最后根节点。
    • 层序遍历：按照层次顺序访问节点，通常使用队列实现。

总结：其实不管是哪种遍历方式，我们最终的目的就是访问所有的树（子树）的根节点，左孩子，右孩子。那么在访问的过程中，肯定不能一次访问并打印完毕。这个时候就需要栈来暂存我们已经访问过的元素。在需要的时候将其打印出来即可（我们以左孩子节点为基准，先序遍历是在访问左孩子节点之前打印节点，中序遍历是在左孩子节点压栈之后打印节点，后序遍历是在访问完左右孩子节点之后打印节点）。

二叉树在计算机科学中有着广泛的应用，例如在文件系统、数据库索引、搜索算法、表达式解析等领域。

下面是一个简单的C++实现二叉树节点的示例：

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

这个结构定义了一个二叉树节点，其中val是节点存储的数据，left和right是指向左右子节点的指针。

2. 层序遍历

二叉树的层序遍历是一种按层次顺序访问所有节点的遍历方式，通常使用队列来实现。下面是二叉树层序遍历的步骤：

  • 初始化：创建一个队列来存储节点，将根节点加入队列。

  • 循环遍历：当队列非空时，执行以下操作：

    • 取出队列中的第一个节点，访问该节点的值。
    • 将该节点的左子节点和右子节点（如果它们存在）加入队列。

  • 收集结果：将每一层访问的节点值存储在一个列表中，然后将这些列表存储在一个更大的列表中，形成层序遍历的结果。

二叉树的层序遍历是一种常见的树遍历算法，其目的是按照从上到下，从左到右的顺序访问二叉树中的所有节点。层序遍历通常使用队列来实现，以下是一个解题思路：

  • 初始化：创建一个队列queue来存储二叉树的节点，首先将根节点root入队。

  • 遍历条件：当队列不为空时，执行以下步骤。

  • 获取队列大小：记录当前层的节点数level_size，这可以通过队列的大小来获取。

  • 逐层遍历：使用一个循环，循环次数为level_size，每次循环从队列中出队一个节点，并访问该节点的值。

  • 处理子节点：对于每个出队的节点，如果它有左子节点，将左子节点入队；如果它有右子节点，也将右子节点入队。

  • 收集结果：将每层访问的节点值存储在一个列表中，所有层的列表可以存储在一个更大的列表中，形成层序遍历的结果。

  • 返回结果：遍历结束后，返回包含所有层节点值的列表

2.1. 复杂度

  • 时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。

  • 空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

2.2. 示例1

//
// 二叉树层序遍历算法 C++

#include <iostream>
#include <queue>

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 层序遍历二叉树的函数
void levelOrderTraversal(TreeNode* root)
{
  if (root == nullptr) return;
  std::queue<TreeNode*> q; // 使用队列存储待访问的节点
  q.push(root); // 将根节点加入队列

  while (!q.empty())
  {
    TreeNode* current = q.front(); // 获取队列前端节点
    q.pop(); // 从队列中移除该节点
    std::cout << current->val << " "; // 输出节点值

    if (current->left != nullptr)
    {
      q.push(current->left); // 将左子节点加入队列
    }
    if (current->right != nullptr)
    {
      q.push(current->right); // 将右子节点加入队列
    }
  }
}

int main()
{
  // 构建一个简单的二叉树:
  //           1
  //      /         \
  //     2           3
  //   /   \       /   \
  //  4     5     6     7
  // / \   / \   / \   / \
  // 8  9 10 11 12 13 14 15

  //Layer1: Root
  TreeNode* root = new TreeNode(1); // 1

  //Layer2:
  root->left = new TreeNode(2);  // 1 -> 2
  root->right = new TreeNode(3); // 1 -> 3

  //Layer3:
  root->left->left = new TreeNode(4);   // 1 -> 2 -> 4
  root->left->right = new TreeNode(5);  // 1 -> 2 -> 5
  root->right->left = new TreeNode(6);  // 1 -> 3 -> 6
  root->right->right = new TreeNode(7); // 1 -> 3 -> 7

  //Layer4
  root->left->left->left = new TreeNode(8);
  root->left->left->right = new TreeNode(9);
  root->left->right->left = new TreeNode(10);
  root->left->right->right = new TreeNode(11);
  root->right->left->left = new TreeNode(12);
  root->right->left->right = new TreeNode(13);
  root->right->right->left = new TreeNode(14);
  root->right->right->right = new TreeNode(15);


  std::cout << "二叉树的层序遍历结果是：";
  levelOrderTraversal(root); // 调用层序遍历函数
  std::cout << std::endl;

  return 0;

}

运行结果：

二叉树的层序遍历结果是：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2.3. 示例2

#include <iostream>
#include <vector>
#include <queue>

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 层序遍历函数
std::vector<std::vector<int>> levelOrder(TreeNode* root)
{
  std::vector<std::vector<int>> result;

  if (!root) return result;  // 如果根为空，直接返回空结果

  std::queue<TreeNode*> q;  // 使用队列来存储节点
  q.push(root);  // 将根节点入队

  while (!q.empty())
  {
    int level_size = q.size();  // 当前层的节点数量

    std::vector<int> current_level;  // 当前层的节点值列表

    for (int i = 0; i < level_size; ++i)
    {
      TreeNode* node = q.front();  // 取出队列前端的节点
      q.pop();  // 弹出队列
      current_level.push_back(node->val);  // 将节点值加入到当前层列表

      // 将非空的左右子节点入队
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }

    result.push_back(current_level);  // 将当前层的节点值列表加入到结果中
  }

  return result;
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* node) {
  if (!node) return;
  deleteTree(node->left);
  deleteTree(node->right);
  delete node;
}

int main()
{
  //init sample001:
  //TreeNode* root = new TreeNode(3);
  {
    // 创建一个示例二叉树
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
  }


  //init sample002
  //Layer1: Root
  TreeNode* root = new TreeNode(1); // 1
  {
    // 构建一个简单的二叉树:
    //           1
    //      /         \
    //     2           3
    //   /   \       /   \
    //  4     5     6     7
    // / \   / \   / \   / \
    // 8  9 10 11 12 13 14 15

    //Layer2:
    root->left = new TreeNode(2);  // 1 -> 2
    root->right = new TreeNode(3); // 1 -> 3

    //Layer3:
    root->left->left = new TreeNode(4);   // 1 -> 2 -> 4
    root->left->right = new TreeNode(5);  // 1 -> 2 -> 5
    root->right->left = new TreeNode(6);  // 1 -> 3 -> 6
    root->right->right = new TreeNode(7); // 1 -> 3 -> 7

    //Layer4
    root->left->left->left = new TreeNode(8);
    root->left->left->right = new TreeNode(9);
    root->left->right->left = new TreeNode(10);
    root->left->right->right = new TreeNode(11);
    root->right->left->left = new TreeNode(12);
    root->right->left->right = new TreeNode(13);
    root->right->right->left = new TreeNode(14);
    root->right->right->right = new TreeNode(15);


  }

  // 层序遍历二叉树
  std::vector<std::vector<int>> levels = levelOrder(root);

  // 打印层序遍历结果
  for (const auto& level : levels)
  {
    for (int val : level)
    {
      std::cout << val << " ";
    }
    std::cout << std::endl;
  }

  // 释放二叉树内存
  deleteTree(root);

  return 0;
}

运行结果：


1 
2 3 
4 5 6 7 
8 9 10 11 12 13 14 15

3. 层次遍历2

3.1. 层次遍历规则

按照二叉树中的层次从左到右依次遍历每层中的结点。通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。

3.2. 层次遍历举例

在这里插入图片描述

例如，层次遍历如上图中的二叉树：
* 1.根结点 1 入队；
* 2.根结点 1 出队，出队的同时，将左孩子 2 和右孩子 3 分别入队；
* 3.队头结点 2 出队，出队的同时，将结点 2 的左孩子 4 和右孩子 5 依次入队；
* 4.队头结点 3 出队，出队的同时，将结点 3 的左孩子 6 和右孩子 7 依次入队；
* 5.不断地循环，直至队列内为空。

3.3. 层次遍历代码

/*
 * @Description: 二叉树的层次遍历
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-20 14:52:38
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:41:48
 */ 
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
//初始化队头和队尾指针开始时都为0
int front=0,rear=0;
typedef struct BiTNode{
    //数据域
    TElemType data;
    //左右孩子指针
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//采用顺序队列，初始化创建队列数组
BiTree a[20];
/**
 * @Description: 初始化二叉树
 * @Param: BiTree *T 二叉树的结构体指针数组
 * @Return: 无
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
   
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
   
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
   
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
   
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 入队
 * @Param: BiTree *a 二叉树结构体指针  BiTree node 入队的节点
 * @Return: 无
 * @Author: Carlos
 */
void EnQueue(BiTree *a,BiTree node){
    a[rear++]=node;
}
/**
 * @Description: 出队
 * @Param: BiTree *node 二叉树结构体指针数组
 * @Return: 结构体指针
 * @Author: Carlos
 */
BiTree DeQueue(BiTree *node){
    return a[front++];
}
/**
 * @Description: 二叉树输出函数
 * @Param: BiTree node 输出的节点
 * @Return: 无
 * @Author: Carlos
 */
void displayNode(BiTree node){
    printf("%d ",node->data);
}
int main() {
    BiTree tree;
    //初始化二叉树
    CreateBiTree(&tree);
    BiTree p;

    //根结点入队
    EnQueue(a, tree);
    
    //当队头和队尾相等时，表示队列为空
    while(front<rear) 
    {
        //队头结点出队
        p=DeQueue(a);
        displayNode(p);
        //将队头结点的左右孩子依次入队
        if (p->lchild!=NULL) {
            EnQueue(a, p->lchild);
        }
        if (p->rchild!=NULL) {
            EnQueue(a, p->rchild);
        }
    }
    return 0;
}

4. 先序遍历

https://cloud.tencent.com/developer/article/1826606

4.1. 先序遍历规则

先序遍历的核心思想：1.访问根节点；2.访问当前节点的左子树；3.若当前节点无左子树，则访问当前节点的右子树；即考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)

4.2. 先序遍历举例

如图所示，采用先序遍历访问这颗二叉树的详细过程为：
* 1.访问该二叉树的根节点，找到 1；
* 2.访问节点 1 的左子树，找到节点 2；
* 3.访问节点 2 的左子树，找到节点 4；
* 4.由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
* 5.由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
* 6.访问节点 3 左子树，找到节点 6；
* 7.由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
* 8.节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；
* 因此，图 中二叉树采用先序遍历得到的序列为：1 2 4 5 3 6 7

在这里插入图片描述

4.3. 先序遍历代码（递归）

/*
 * @Description: 
 * @Version: 
 * @Autor: Carlos
 * @Date: 2020-05-29 16:55:41
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:03:23
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


//构造结点的结构体
typedef struct BiTNode
{
    int data;//数据域
    
    struct BiTNode *lchild,*rchild;//左右孩子指针
    
}BiTNode,*BiTree;

/**
 * @Description: 初始化树的函数
 * @Param: BiTree *T 结构体指针的指针
 * @Return: 无
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    //根节点
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
    //1节点的左孩子2
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //2节点的右孩子5
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    //1节点的右孩子3
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    //3节点的左孩子6
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //3节点的右孩子7
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    //2节点的左孩子4
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}


/**
 * @Description: 模拟操作结点元素的函数，输出结点本身的数值
 * @Param:BiTree elem 就结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}

/**
 * @Description: 先序遍历
 * @Param: BiTree T 结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void PreOrderTraverse(BiTree T){
    if (T) {
        PrintBiT(T);//调用操作结点数据的函数方法
        PreOrderTraverse(T->lchild);//访问该结点的左孩子
        PreOrderTraverse(T->rchild);//访问该结点的右孩子
    }
    //如果结点为空，返回上一层
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍历: \n");
    PreOrderTraverse(Tree);
}
4.4. 先序遍历代码（非递归）

因为要在遍历完某个树的根节点的左子树后接着遍历节点的右子树，为了能找到该树的根节点，需要使用栈来进行暂存。中序和后序也都涉及到回溯，所以都需要用到栈。


#include <stdio.h>
#include <string.h>
#include <stdlib.h>


//构造结点的结构体
typedef struct BiTNode
{
    int data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode, *BiTree;

int top = -1;

//定义一个顺序栈
BiTree  a[20];


/**
 * @Description: 初始化树
 * @Param: BiTree *T 指针的指针
 * @Return: 无
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    //根节点
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
    //1节点的左孩子2
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //2节点的右孩子5
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    //1节点的右孩子3
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    //3节点的左孩子6
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    //3节点的右孩子7
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    //2节点的左孩子4
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 打印二叉树
 * @Param: BiTree elem 指针的指针
 * @Return: 无
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 二叉树压栈函数
 * @Param: BiTree* a 结构体指针的指针（也可以理解为指针数组） BiTree elem 结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void Push(BiTree* a,BiTree elem)
{
     a[++top]=elem;
}
/**
 * @Description: 二叉树弹栈函数
 * @Param: 无
 * @Return: 无
 * @Author: Carlos
 */
void Pop()
{
    if (top==-1) {
        return ;
    }
    top--;
}
/**
 * @Description: 获取栈顶元素
 * @Param: BiTree*a 结构体指针数组
 * @Return: 结构体指针
 * @Author: Carlos
 */
BiTree GetTop(BiTree*a){
    return a[top];
}
/**
 * @Description: 先序遍历
 * @Param: BiTree Tree 结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void PreOrderTraverse(BiTree Tree)
{
   //临时指针
    BiTree p;
    
    //根结点进栈
    Push(a, Tree);
    
    while (top!=-1) 
    {
        //取栈顶元素
        p=GetTop(a);
        
        //弹栈
        Pop();
        
        while (p) 
        {
            //调用结点的操作函数
            PrintBiT(p);
            
            //如果该结点有右孩子，右孩子进栈
            if (p->rchild) 
            {
                Push(a,p->rchild);
            }
            
            p=p->lchild;//一直指向根结点最后一个左孩子
            
        }
    }
}

int main() 
{
    BiTree Tree;
    
    CreateBiTree(&Tree);
    
    printf("先序遍历: \n");
    PreOrderTraverse(Tree);
    
}

5. 中序遍历

https://cloud.tencent.com/developer/article/1826606

5.1. 中序遍历规则

二叉树中序遍历的实现思想是：1.访问当前节点的左子树；2.访问根节点；3.访问当前节点的右子树。即考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)

5.2. 中序遍历举例

在这里插入图片描述

以上图为例，采用中序遍历的思想遍历该二叉树的过程为：
 * 1.访问该二叉树的根节点，找到 1；
 * 2.遍历节点 1 的左子树，找到节点 2；
 * 3.遍历节点 2 的左子树，找到节点 4；
 * 4.由于节点 4 无左孩子，因此找到节点 4，并遍历节点 4 的右子树；
* 5.由于节点 4 无右子树，因此节点 2 的左子树遍历完成，访问节点 2；
 * 6.遍历节点 2 的右子树，找到节点 5；
 * 7.由于节点 5 无左子树，因此访问节点 5 ，又因为节点 5 没有右子树，因此节点 1 的左子树遍历完成，访问节点 1 ，并遍历节点 1 的右子树，找到节点 3；
 * 8.遍历节点 3 的左子树，找到节点 6；
 * 9.由于节点 6 无左子树，因此访问节点 6，又因为该节点无右子树，因此节点 3 的左子树遍历完成，开始访问节点 3 ，并遍历节点 3 的右子树，找到节点 7；
 * 10.由于节点 7 无左子树，因此访问节点 7，又因为该节点无右子树，因此节点 1 的右子树遍历完成，即整棵树遍历完成；
 因此，上图中二叉树采用中序遍历得到的序列为：4 2 5 1 6 3 7

5.3. 中序遍历代码（递归）

/*
 * @Description: 递归实现的中序遍历
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-18 14:53:29
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:21:06
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//构造结点的结构体
typedef struct BiTNode{
    //数据域
    TElemType data;
    //左右孩子指针
    struct BiTreelchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化树
 * @Param: BiTree *T  结构体指针的指针（指针数组）
 * @Return: 无
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
  
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 显示函数
 * @Param: BiTree elem 结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 中序遍历
 * @Param: BiTree T 结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void INOrderTraverse(BiTree T){
    if (T) {
        INOrderTraverse(T->lchild);//遍历左孩子
        PrintBiT(T);//调用操作结点数据的函数方法
        INOrderTraverse(T->rchild);//遍历右孩子
    }
    //如果结点为空，返回上一层
    return;
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("中序遍历算法: \n");
    INOrderTraverse(Tree);
}
5.4. 中序遍历代码（非递归）

和非递归先序遍历类似，唯一区别是考查到当前节点时，并不直接输出该节点。而是当考查节点为空时，从栈中弹出的时候再进行输出(永远先考虑左子树，直到左子树为空才访问根节点)。


/*
 * @Description: 二叉树的先序遍历（非递归）
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-17 16:35:27
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-18 14:51:01
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DBG_PRINTF(fmt, args...)  \
do\
{\
    printf("<<File:%s  Line:%d  Function:%s>> ", __FILE__, __LINE__, __FUNCTION__);\
    printf(fmt, ##args);\
}while(0)
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
    //数据域
    TElemType data;
    //左右孩子指针
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化树
 * @Param: BiTree *T  结构体指针的指针
 * @Return: 无
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 中序遍历使用的进栈函数
 * @Param: BiTree* a 指向树的指针数组 BiTree elem 进栈的元素
 * @Return: 无
 * @Author: Carlos
 */
void Push(BiTree* a,BiTree elem){
    //指针进栈
    a[++top]=elem;
}
/**
 * @Description: 前序遍历使用的弹栈函数
 * @Param: 无
 * @Return: 无
 * @Author: Carlos
 */
void Pop( ){
    if (top==-1) {
        return;
    }
    top--;
}
/**
 * @Description: 显示函数
 * @Param: BiTree elem 指向树的指针
 * @Return: 无
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
 * @Description: 拿到栈顶元素
 * @Param: BiTree*a 指针数组
 * @Return: 栈顶元素的地址
 * @Author: Carlos
 */
BiTree GetTop(BiTree*a){
    return a[top];
}
/**
 * @Description: 中序遍历非递归算法，先左，然后回退，然后右。从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，
 * 从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作
 * @Return: 栈顶元素的地址
 * @Author: Carlos
 */
void InOrderTraverse1(BiTree Tree){
    //定义一个顺序栈
    BiTree a[20];
    //临时指针
    BiTree p;
    //根结点进栈
    Push(a, Tree);
    //top!=-1说明栈内不为空，程序继续运行
    while (top!=-1) {
        //一直取栈顶元素，且不能为NULL
        while ((p=GetTop(a)) &&p){
            //将该结点的左孩子进栈，如果没有左孩子，NULL进栈
            Push(a, p->lchild);
        }
        //跳出循环，栈顶元素肯定为NULL，将NULL弹栈。 打印的第一个元素没有右孩子，所以也会Pop掉，再取栈顶元素就是第一个元素的父节点
        Pop();
        if (top!=-1) {
            //取栈顶元素
            p=GetTop(a);
            //栈顶元素弹栈
            Pop();
            //遍历完所有左孩子之后，打印栈顶的元素。
            PrintBiT(p);
            //将p指向的结点的右孩子进栈
            Push(a, p->rchild);
        }
    }
}
/**
 * @Description: 中序遍历非递归算法。中序遍历过程中，只需将每个结点的左子树压栈即可，右子树不需要压栈。
 * 当结点的左子树遍历完成后，只需要以栈顶结点的右孩子为根结点，继续循环遍历即可
 * @Param: 无
 * @Return: 栈顶元素的地址
 * @Author: Carlos
 */
void InOrderTraverse2(BiTree Tree){
    //定义一个顺序栈
    BiTree a[20];
    //临时指针
    BiTree p;
    p=Tree;
    //当p为NULL或者栈为空时，表明树遍历完成
    while (p || top!=-1) {
        //如果p不为NULL，将其压栈并遍历其左子树
        if (p) {
            Push(a, p);
            p=p->lchild;
        }
        //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树  弹出时顺便访问右子树
        else{
            p=GetTop(a);
            Pop();
            PrintBiT(p);
            p=p->rchild;
        }
    }
}
int main(){
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("中序遍历: \r\n");
    InOrderTraverse2(Tree);
    DBG_PRINTF("123456\r\n");
    return 0;
}

6. 后序遍历

https://cloud.tencent.com/developer/article/1826606

6.1. 后序遍历规则

二叉树后序遍历的实现思想是：1.访问左子树；2.访问右子树；3.完成该节点的左右子树的访问后，再访问该节点。即考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)

6.2. 后序遍历举例

在这里插入图片描述

如上图中，对此二叉树进行后序遍历的操作过程为：
 * 从根节点 1 开始，遍历该节点的左子树（以节点 2 为根节点）；
 * 1.遍历节点 2 的左子树（以节点 4 为根节点）；
 * 2.由于节点 4 既没有左子树，也没有右子树，此时访问该节点中的元素 4，并回退到节点 2 ，遍历节点 2 的右子树（以 5 为根节点）；
 * 3.由于节点 5 无左右子树，因此可以访问节点 5 ，并且此时节点 2 的左右子树也遍历完成，因此也可以访问节点 2；
 * 4.此时回退到节点 1 ，开始遍历节点 1 的右子树（以节点 3 为根节点）；
 * 5.遍历节点 3 的左子树（以节点 6 为根节点）；
 * 6.由于节点 6 无左右子树，因此访问节点 6，并回退到节点 3，开始遍历节点 3 的右子树（以节点 7 为根节点）；
 * 7.由于节点 7 无左右子树，因此访问节点 7，并且节点 3 的左右子树也遍历完成，可以访问节点 3；节点 1 的左右子树也遍历完成，可以访问节点 1；
 * 由此，对上图 中二叉树进行后序遍历的结果为：4 5 2 6 7 3 1

6.3. 后序遍历代码（递归）

/*
 * @Description: 二叉树的后序遍历（递归）
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-18 16:23:57
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-30 17:29:38
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//构造结点的结构体
typedef struct BiTNode{
    //数据域
    TElemType data;
    //左右孩子指针
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
* @Description: 初始化树
* @Param: BiTree *T  结构体指针
* @Return: 无
* @Author: Carlos
*/
void CreateBiTree(BiTree *T){
    *T=(BiTree)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTree)malloc(sizeof(BiTNode));
  
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTree)malloc(sizeof(BiTNode));

    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;

    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;

    (*T)->rchild->rchild=(BiTree)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}

/**
* @Description: 显示函数
* @Param: BiTree elem 指向树的结构体指针
* @Return: 无
* @Author: Carlos
*/
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}
/**
* @Description: 先序遍历
* @Param: BiTree T 指针数组，存放各个节点的指针
* @Return: 无
* @Author: Carlos
*/
void PreOrderTraverse(BiTree T){
    if (T) {
        PreOrderTraverse(T->lchild);//访问该结点的左孩子
        PreOrderTraverse(T->rchild);//访问该结点的右孩子
         PrintBiT(T);//调用操作结点数据的函数方法
    }
    //如果结点为空，返回上一层
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍历: \n");
    PreOrderTraverse(Tree);
}
6.4. 后序遍历代码（非递归）

/*
 * @Description: 二叉树的后序遍历（非递归）
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-18 16:23:57
 * @LastEditors: Carlos
 * @LastEditTime: 2020-05-18 16:24:29
 */ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
//top变量时刻表示栈顶元素所在位置
int top=-1;
//构造结点的结构体
typedef struct BiTNode{
    //数据域
    TElemType data;
    //左右孩子指针
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
 * @Description: 初始化树
 * @Param: BiTree *T  结构体指针数组
 * @Return: 无
 * @Author: Carlos
 */
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/**
 * @Description: 后序遍历使用的弹栈函数
 * @Param: 无
 * @Return: 无
 * @Author: Carlos
 */
void Pop( ){
    if (top==-1) {
        return ;
    }
    top--;
}
/**
 * @Description: 显示函数
 * @Param: 无
 * @Return: 无
 * @Author: Carlos
 */
void PrintBiT(BiTree elem){
    printf("%d ",elem->data);
}

//增加左右子树的访问标志
typedef struct SNode{
    BiTree p;
    int tag;
}SNode;
/**
 * @Description: 后序遍历使用的进栈函数
 * @Param: SNode *a 指向树和标志位的结构体的指针 BiTree sdata 进栈的元素
 * @Return: 无
 * @Author: Carlos
 */
void Push(SNode *a,SNode sdata){
    a[++top]=sdata;
}
/**
 * @Description: 后序遍历非递归算法。后序遍历是在遍历完当前结点的左右孩子之后，才调用操作函数，所以需要在操作结点进栈时，为每个结点配备一个标志位。
 * 当遍历该结点的左孩子时，设置当前结点的标志位为 0，进栈；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。这样，当遍历完成，该结点弹栈时，
 * 查看该结点的标志位的值：如果是 0，表示该结点的右孩子还没有遍历；反之如果是 1，说明该结点的左右孩子都遍历完成，可以调用操作函数。
 * @Param: 结构体指针数组
 * @Return: 无
 * @Author: Carlos
 */
void PostOrderTraverse(BiTree Tree){
    //定义一个顺序栈
    SNode a[20];
    //临时指针
    BiTree p;
    int tag;
    SNode sdata;
    p=Tree;
    while (p||top!=-1) {
        //左孩子进栈
        while (p) {
            //为该结点入栈做准备
            sdata.p=p;
            //由于遍历是左孩子，设置标志位为0
            sdata.tag=0;
            //压栈
            Push(a, sdata);
            //以该结点为根结点，遍历左孩子
            p=p->lchild;
        }
        //取栈顶元素 取左孩子的父节点
        sdata=a[top];
        //栈顶元素弹栈
        Pop();
        p=sdata.p;
        tag=sdata.tag;
        //右孩子进栈
        //如果tag==0，说明该结点还没有遍历它的右孩子
        if (tag==0) {
            sdata.p=p;
            sdata.tag=1;
            //更改该结点的标志位，重新压栈
            Push(a, sdata);
            //以该结点的右孩子为根结点，重复循环
            p=p->rchild;
        }
        //如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以调用操作函数了
        else{
            PrintBiT(p);
            p=NULL;
        }
    }
}
int main(){
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍历: \n");
    PostOrderTraverse(Tree);
}

标签：lchild,遍历,BiTree,BiTNode,算法,二叉树,rchild,节点
From： https://blog.csdn.net/limeigui/article/details/144957394

相关文章

  • 代码随想录算法训练营第五十六天|KM108.冗余连接|KM109.冗余连接Ⅱ
    108.冗余连接本题光看题目没理解具体什么意思；看了题解有点明白了；（个人觉得还是力扣的题目描述比较容易理解）题目意思：大概就是加一条边使树结构有环，然后再环中去掉一条边（如果环中多条边可取，则去掉最后一条边），仍然变成一颗树结构；思路：观察两个节点是否再一个集合，如果不在，也可以将......
  • 高效驰骋棋盘：马踏棋盘算法优化攻略与实践
    文章目录......
  • 【优选算法】Bit-Samurai：位运算的算法之道
    文章目录1.常见位运算总结1.1基础位运算符号1.2给一个数n，确定它的二进制表示中的第x位是0还是11.3将一个数n的二进制表示的第x位修改成11.4将一个数n的二进制表示的第x位修改成01.5位图的思想1.6提取一个n二进制表示中最右侧的11.7干掉一个数......
  • 代码随想录算法训练营第二十八天-贪心算法-122. 买卖股票的最佳时机II
    有奇妙的解法分析要获得利润，就是当天卖出前一天买入的的利润，也就是当天价格减去前一天的价格通过这样的运算，可以得到一个新的序列，这个序列就是上一道53的最大子序和的应用了而且把这些子序和中所有正数值都加到一起就是最大利润了#include<iostream>#include<vector>c......
  • 双指针算法专题
    目录1.移动零1.1算法原理1.2算法代码 2.复写零2.1算法原理  2.2算法代码3.快乐数3.1算法原理3.2算法代码4.盛水最多的容器4.1算法原理 4.2算法代码5.有效三角形的个数5.1算法原理5.2算法代码6. 剑指offer：和为s的两个数(原)6.1算法......
  • 【复现】基于自适应遗传算法的分布式电源优化配置[IEEE33、IEEE118节点]（Matlab代码实
     ......
  • 排序算法模板--python版
    在刷算法题时，排序是一个非常常见的操作。Python提供了多种排序算法的实现方式，而在一些经典的算法题中，我们需要手动实现不同的排序算法以符合题目要求。以下是一些常见的排序算法模板，包含了冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序，这些算法的模板通常会在刷......
  • 关于app签名算法一些问题
    app签名算法相关问题如何修改签名算法1.为什么要修改签名算法？1.生成新的密钥库（KeyStore）和密钥（Key）2.修改签名算法（使用新的签名算法）3.确认签名算法是否生效4.兼容性和注意事项总结如何将SHA256中的1024位密钥改为2048位密钥步骤概览1.生成新的RSA2048位密......
  • java毕业设计-基于springboot+vue的协同过滤推荐算法旅游信息管理平台设计和实现，基于
    博主介绍：✌️码农一枚，专注于大学生项目实战开发、讲解和毕业......
  • 欧拉回路算法
    网络上关于求欧拉回路的线性算法的资料普遍缺少证明。本文将通过分析欧拉回路的性质直接推导出这一算法。算法流程基本的定义可以参考Alex_Wei的博客，本文不再赘述。算法流程部分仅推导求无向图欧拉回路的算法，求有向图欧拉回路的算法的推导过程是类似的，更改一些对应术语即可。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99