C ++ 从单链表到创建二叉树到二叉树的遍历（结构体）

首先我们要了解二叉树的数据结构是什么，本质上二叉树是一个有两个节点的链表，我们先了解的单链表的相关定义

单链表

创建一个朴素的单链表

#include <iostream>using namespace std;struct Node{int val;Node* next;Node(int x) : val(x), next(nullptr) {}
};int main()
{return 0;
}

Node(int value) : data(value), next(nullptr) {}

1. 构造函数定义: Node(int value) 是构造函数的声明，它接受一个 int 类型的参数 value。

2. 成员初始化列表: : data(value), next(nullptr) 是成员初始化列表，用于初始化类成员。

   • data(value) 将构造函数的参数 value 赋给 data 成员变量。
   • next(nullptr) 将 next 指针初始化为 nullptr，表示该节点最初不指向任何其他节点。

3. 空体: {} 表示构造函数的主体，这里是空的，因为所有初始化工作都在成员初始化列表中完成了。

简而言之，这个构造函数创建一个 Node 对象时，设置 data 为提供的 value 值，而 next 则默认指向空，表示没有下一个节点。

创建一颗二叉树

比如我想要创建一颗这样的二叉树

在结构体当中定义两个结点，并且初始化这棵树

#include <iostream>using namespace std;struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 初始化
void init(TreeNode* root){root -> left = new TreeNode(2);root -> right = new TreeNode(3);root -> left -> left = new TreeNode(4);root -> left -> right = new TreeNode(5);root -> right -> left = new TreeNode(6);root -> right -> right = new TreeNode(7);
}int main()
{// 初始化根节点是1TreeNode* root = new TreeNode(1); init(root);return 0;
}

前序遍历、中序遍历、后序遍历

这里是利用了递归的思想，详细请看洛谷B3642 二叉树的遍历（前序、中序、后序）-CSDN博客

前序的代码如下，中序、后序就不展示了

#include <iostream>using namespace std;struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 初始化
void init(TreeNode* root){root -> left = new TreeNode(2);root -> right = new TreeNode(3);root -> left -> left = new TreeNode(4);root -> left -> right = new TreeNode(5);root -> right -> left = new TreeNode(6);root -> right -> right = new TreeNode(7);
}void dfs(TreeNode* root){if(root == nullptr) return;cout << root -> val << " ";dfs(root -> left);dfs(root -> right);
}int main()
{// 初始化根节点是1TreeNode* root = new TreeNode(1); init(root);dfs(root);return 0;
}

层次遍历

这里讲一下层次遍历以上面那棵树为例

首先要对队列很熟悉，层次遍历是每一层从左往右依此遍历，那么这棵树的层次遍历就是1234567

那就很明确了，从第一层开始，从左往右加入队列即可

#include <iostream>
#include <queue>using namespace std;struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 初始化
void init(TreeNode* root){root -> left = new TreeNode(2);root -> right = new TreeNode(3);root -> left -> left = new TreeNode(4);root -> left -> right = new TreeNode(5);root -> right -> left = new TreeNode(6);root -> right -> right = new TreeNode(7);
}void bfs(TreeNode* root){queue<TreeNode*> q;q.push(root);while(!q.empty()){TreeNode* node = q.front();q.pop();cout << node -> val << " ";if(node -> left != nullptr) q.push(node -> left);if(node -> right != nullptr) q.push(node -> right);}
}int main()
{// 初始化根节点是1TreeNode* root = new TreeNode(1); init(root);bfs(root);return 0;
}

加油