1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树1 4.中序遍历二叉树2 5.后序遍历二叉树 6.层序遍历二叉树 7.求二叉树的深度 8.退出
时间: 2024-05-11 19:13:22 浏览: 246
1. 创建二叉树:
二叉树是一种树形结构,其中每个节点最多有两个子节点,我们可以通过递归的方式来创建一个二叉树。具体步骤如下:
首先,我们需要定义二叉树节点的结构体:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
然后,我们可以通过递归方式创建二叉树,示例代码如下:
```
TreeNode* createTree() {
int val;
cin >> val; // 输入节点的值
if (val == -1) { // 如果值为-1,表示该节点为空
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = createTree(); // 递归创建左子树
root->right = createTree(); // 递归创建右子树
return root;
}
```
2. 先序遍历二叉树:
先序遍历是指先访问节点本身,再遍历其左子树和右子树。示例代码如下:
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " "; // 访问节点本身
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
```
3. 中序遍历二叉树1:
中序遍历是指先遍历左子树,再访问节点本身,最后遍历右子树。示例代码如下:
```
void inorderTraversal1(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal1(root->left); // 遍历左子树
cout << root->val << " "; // 访问节点本身
inorderTraversal1(root->right); // 遍历右子树
}
```
4. 中序遍历二叉树2:
与中序遍历1不同,这里给出一种非递归的中序遍历方法,需要使用到栈。示例代码如下:
```
void inorderTraversal2(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* p = root;
while (p != NULL || !st.empty()) {
while (p != NULL) {
st.push(p);
p = p->left;
}
p = st.top();
st.pop();
cout << p->val << " ";
p = p->right;
}
}
```
5. 后序遍历二叉树:
后序遍历是指先遍历左子树,再遍历右子树,最后访问节点本身。示例代码如下:
```
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left); // 遍历左子树
postorderTraversal(root->right); // 遍历右子树
cout << root->val << " "; // 访问节点本身
}
```
6. 层序遍历二叉树:
层序遍历是指按照从上到下、从左到右的顺序遍历每个节点。需要使用到队列。示例代码如下:
```
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != NULL) {
q.push(node->left);
}
if (node->right != NULL) {
q.push(node->right);
}
}
}
```
7. 求二叉树的深度:
二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数。可以使用递归方式求解。示例代码如下:
```
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
```
8. 退出
阅读全文
相关推荐














