关于二叉树的基本操作

1创建二叉树
2创建的二叉树以树状形式输出
3分别以先序，中序，后序，三钟遍历方式访问二叉树
4输出二叉树中的叶子结点以及叶子结点个数
5输出二叉树高度

以下是一个简单的C语言程序，用于创建二叉树并实现所需的操作。程序基于递归实现二叉树的各种操作。

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

// 二叉树结构体
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建二叉树
struct TreeNode* createBinaryTree() {
    int val;
    struct TreeNode* node = NULL;
    
    printf("Enter value (or -1 for no node): ");
    scanf("%d", &val);
    
    if (val == -1) {
        return NULL;
    } else {
        node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        
        node->val = val;
        node->left = createBinaryTree();
        node->right = createBinaryTree();
        
        return node;
    }
}

// 以树状形式输出二叉树
void printBinaryTree(struct TreeNode* root, int space) {
    if (root == NULL) {
        return;
    }
    
    space += 10;
    
    printBinaryTree(root->right, space);
    printf("\n");
    
    for (int i = 10; i < space; i++) {
        printf(" ");
    }
    
    printf("%d\n", root->val);
    
    printBinaryTree(root->left, space);
}

// 先序遍历二叉树
void preOrderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    printf("%d ", root->val);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

// 中序遍历二叉树
void inOrderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    inOrderTraversal(root->left);
    printf("%d ", root->val);
    inOrderTraversal(root->right);
}

// 后序遍历二叉树
void postOrderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%d ", root->val);
}

// 计算叶子结点数量
int countLeaves(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL) {
        return 1;
    } else {
        return countLeaves(root->left) + countLeaves(root->right);
    }
}

// 输出叶子结点
void printLeaves(struct TreeNode* root) {
    if (root == NULL) {
        return;
    } else if (root->left == NULL && root->right == NULL) {
        printf("%d ", root->val);
    } else {
        printLeaves(root->left);
        printLeaves(root->right);
    }
}

// 计算二叉树高度
int getHeight(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }
}

// 主函数
int main() {
    struct TreeNode* root;
    int choice;
    
    // 创建二叉树
    root = createBinaryTree();
    
    // 输出二叉树
    printBinaryTree(root, 0);
    
    // 遍历二叉树
    printf("Enter type of traversal: (1) Preorder, (2) Inorder, (3) Postorder\n");
    scanf("%d", &choice);
    
    switch (choice) {
        case 1:
            printf("Preorder traversal: ");
            preOrderTraversal(root);
            break;
        case 2:
            printf("Inorder traversal: ");
            inOrderTraversal(root);
            break;
        case 3:
            printf("Postorder traversal: ");
            postOrderTraversal(root);
            break;
        default:
            printf("Invalid choice.\n");
            break;
    }
    
    printf("\n");
    
    // 输出叶子结点及数量
    printf("Leaves: ");
    printLeaves(root);
    printf("\nNumber of leaves: %d\n", countLeaves(root));
    
    // 计算二叉树高度
    printf("Height of the tree: %d\n", getHeight(root));
    
    return 0;
}

在这个程序中，首先定义了一个结构体来表示二叉树节点，包括整数val，以及左右子节点指针left和right。使用createBinaryTree函数创建二叉树，printBinaryTree函数以树状形式输出二叉树。

然后实现了三种遍历方式：preOrderTraversal函数实现先序遍历，inOrderTraversal函数实现中序遍历，postOrderTraversal函数实现后序遍历。还实现了两个用于叶子结点的操作，countLeaves函数用于计算叶子结点数量，printLeaves函数用于输出叶子结点。

getHeight函数用于计算二叉树高度。主函数中，使用switch语句可以让用户选择遍历方式，然后输出遍历结果，叶子结点和数量以及二叉树高度。

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7451921
• 你也可以参考下这篇文章：二叉树 —— 创建二叉树 先序遍历 、中序遍历、后序遍历（递归方式、非递归方式）
• 除此之外, 这篇博客: 二叉树的基本操作（创建，先中后序遍历，计算叶子节点个数及输出，计算树高度）中的 内容 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 此文章用c语言实现了二叉树的基本操作，包括先序创建二叉树，先序、中序、后序遍历二叉树，计算叶子节点的个数以及输出叶子节点，求二叉树的深度

• 您还可以看一下 王晨晨老师的硬件工程师入门实战-第二季（电源设计专题）课程中的 电源噪声调测小节, 巩固相关知识点
  
• 以下回答由chatgpt基于相关博客总结生成:
  1. 如何创建一个二叉树？

  二叉树的创建可以通过链式存储结构实现，我们可以定义一个二叉树的结构体来表示每个节点的信息，同时通过指针将左右子树链接起来。以下是一个简单的二叉树结构体的定义：

  struct TreeNode {
      int val;
      struct TreeNode* left;
      struct TreeNode* right;
  };
  

  对于每个节点，我们需要手动创建一个该结构体的实例，并进行赋值操作，构建出一颗符合要求的二叉树。

  以下是一个示例代码，实现创建一颗二叉树：

  #include <stdio.h>
  #include <stdlib.h>
  
  struct TreeNode {
      int val;
      struct TreeNode* left;
      struct TreeNode* right;
  };
  
  struct TreeNode* createTree(int val)
  {
      struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
      node->val = val;
      node->left = NULL;
      node->right = NULL;
      return node;
  }
  
  int main()
  {
      // 构建一个简单的二叉树
      struct TreeNode* root = createTree(1);
      root->left = createTree(2);
      root->right = createTree(3);
  
      return 0;
  }
  

  1. 如何以树状形式输出已创建的二叉树？

  为了以树状形式输出已创建的二叉树，我们可以使用递归算法对二叉树进行深度优先遍历（DFS），并在遍历的过程中将每个节点的信息输出到控制台上，同时通过控制缩进的方式来表示节点之间的层次关系。具体而言，对于每个节点，我们先输出该节点的值，然后分别对左右子树进行递归调用，并在递归前增加一定缩进，递归完成后再恢复缩进，以此体现出二叉树的层次关系。

  以下是一个示例代码，实现树状输出已创建的二叉树：

  #include <stdio.h>
  #include <stdlib.h>
  
  struct TreeNode {
      int val;
      struct TreeNode* left;
      struct TreeNode* right;
  };
  
  struct TreeNode* createTree(int val)
  {
      struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
      node->val = val;
      node->left = NULL;
      node->right = NULL;
      return node;
  }
  
  void printTree(struct TreeNode* root, int depth)
  {
      if (root == NULL) {
          return;
      }
      // 缩进实现层次结构
      for (int i = 0; i < depth; i++) {
          printf("  ");
      }
      printf("%d\n", root->val);
      printTree(root->left, depth + 1);
      printTree(root->right, depth + 1);
  }
  
  int main()
  {
      // 构建一个简单的二叉树
      struct TreeNode* root = createTree(1);
      root->left = createTree(2);
      root->right = createTree(3);
  
      // 树状形式输出已创建的二叉树
      printTree(root, 0);
  
      return 0;
  }
  

  1. 如何分别以先序、中序和后序遍历方式访问已创建的二叉树？

  对于先序、中序和后序遍历方式，我们同样可以使用递归算法对二叉树进行深度优先遍历，并在遍历的过程中对每个节点进行相应的操作。具体而言，对于先序遍历，我们先输出当前节点的值，再分别对左右子树进行遍历。对于中序遍历，我们先对左子树进行遍历，再输出当前节点的值，最后对右子树进行遍历。对于后序遍历，我们先对左右子树进行遍历，再输出当前节点的值。

  以下是一个示例代码，实现分别以先序、中序和后序遍历方式访问已创建的二叉树：

  #include <stdio.h>
  #include <stdlib.h>
  
  struct TreeNode {
      int val;
      struct TreeNode* left;
      struct TreeNode* right;
  };
  
  struct TreeNode* createTree(int val)
  {
      struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
      node->val = val;
      node->left = NULL;
      node->right = NULL;
      return node;
  }
  
  // 先序遍历
  void preorderTraversal(struct TreeNode* root)
  {
      if (root == NULL) {
          return;
      }
      printf("%d ", root->val);
      preorderTraversal(root->left);
      preorderTraversal(root->right);
  }
  
  // 中序遍历
  void inorderTraversal(struct TreeNode* root)
  {
      if (root == NULL) {
          return;
      }
      inorderTraversal(root->left);
      printf("%d ", root->val);
      inorderTraversal(root->right);
  }
  
  // 后序遍历
  void postorderTraversal(struct TreeNode* root)
  {
      if (root == NULL) {
          return;
      }
      postorderTraversal(root->left);
      postorderTraversal(root->right);
      printf("%d ", root->val);
  }
  
  int main()
  {
      // 构建一个简单的二叉树
      struct TreeNode* root = createTree(1);
      root->left = createTree(2);
      root->right = createTree(3);
  
      // 分别以先序、中序和后序遍历方式访问已创建的二叉树
      printf("Preorder traversal: ");
      preorderTraversal(root);
      printf("\n");
      printf("Inorder traversal: ");
      inorderTraversal(root);
      printf("\n");
      printf("Postorder traversal: ");
      postorderTraversal(root);
      printf("\n");
  
      return 0;
  }
  

  1. 如何输出已创建的二叉树中的叶子结点以及叶子结点的个数？

  对于输出已创建的二叉树中的叶子结点，我们同样可以使用递归算法对二叉树进行深度优先遍历，并在遍历的过程中判断当前节点是否为叶子节点，如果是则输出该节点的值。对于统计叶子结点的个数，我们可以在输出的过程中对计数器进行累加操作。

  以下是一个示例代码，实现输出已创建的二叉树中的叶子节点以及叶子节点的个数：

  #include <stdio.h>
  #include <stdlib.h>
  
  struct TreeNode {
      int val;
      struct TreeNode* left;
      struct TreeNode* right;
  };
  
  struct TreeNode* createTree(int val)
  {
      struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
      node->val = val;
      node->left = NULL;
      node->right = NULL;
      return node;
  }
  
  // 输出叶子节点
  void printLeaves(struct TreeNode* root, int* count)
  {
      if (root == NULL) {
          return;
      }
      if (root->left == NULL && root->right == NULL) {
          printf("%d ", root->val);
          (*count)++;
      }
      printLeaves(root->left, count);
      printLeaves(root->right, count);
  }
  
  int main()
  {
      // 构建一个简单的二叉树
      struct TreeNode* root = createTree(1);
      root->left = createTree(2);
      root->right = createTree(3);
      root->left->left = createTree(4);
      root->left->right = createTree(5);
      root->right->left = createTree(6);
      root->right->right = createTree(7);
  
      // 输出已创建的二叉树中的叶子节点并统计叶子节点个数
      int count = 0;
      printf("Leaves: ");
      printLeaves(root, &count);
      printf("\n");
      printf("Leaf count: %d\n", count);
  
      return 0;
  }
  

  1. 如何计算已创建的二叉树的高度？

  对于计算二叉树的高度，我们同样可以使用递归算法对二叉树进行深度优先遍历，并在遍历的过程中记录当前节点的深度。对于每个节点，我们先对左右子树进行递归遍历，分别求得左右子树的深度，然后取两者较大值，再加上1（当前节点的深度），即可得到该节点所在的子树的深度。对于根节点，我们从0开始计算，即树的高度为其根节点的深度。

  以下是一个示例代码，实现计算已创建的二叉树的高度：

  #include <stdio.h>
  #include <stdlib.h>
  
  struct TreeNode {
      int val;
      struct TreeNode* left;
      struct TreeNode* right;
  };
  
  struct TreeNode* createTree(int val)
  {
      struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
      node->val = val;
      node->left = NULL;
      node->right = NULL;
      return node;
  }
  
  // 递归计算树的高度
  int getHeight(struct TreeNode* root)
  {
      if (root == NULL) {
          return -1;
      }
      int leftHeight = getHeight(root->left);
      int rightHeight = getHeight(root->right);
      return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
  }
  
  int main()
  {
      // 构建一个简单的二叉树
      struct TreeNode* root = createTree(1);
      root->left = createTree(2);
      root->right = createTree(3);
      root->left->left = createTree(4);
      root->left->right = createTree(5);
      root->right->left = createTree(6);
      root->right->right = createTree(7);
  
      // 计算已创建的二叉树的高度
      int height = getHeight(root);
      printf("Tree height: %d\n", height);
  
      return 0;
  }