C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

C语言二叉树常见操作详解

什么是二叉树

二叉树是一种重要的数据结构，它由节点组成，每个节点最多有两个子节点，左子节点和右子节点。

二叉树具有以下性质:

1. 每个节点最多有两个子节点。
2. 左子节点的值小于父节点的值。
3. 右子节点的值大于父节点的值。
4. 左右子树都是二叉树。

二叉树的基本操作

1.创建一个二叉树

使用递归的方式来创建一个二叉树，每次创建节点时，递归创建左右子树。以下是一个示例代码：

typedef struct TreeNode{
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* createBinaryTree(){
    int data;
    scanf("%d", &data);
    if(data == -1) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = data;
    root->left = createBinaryTree();
    root->right = createBinaryTree();
    return root;
}

使用外部数据输入的方式来创建二叉树，当输入 -1 时，代表该节点为空。

2.前序遍历二叉树

前序遍历的顺序是：先访问根节点，再遍历左子树和右子树。以下是一个示例代码：

void preOrderTraverse(TreeNode* root){
    if(root!=NULL) {
        printf("%d ",root->data);
        preOrderTraverse(root->left);
        preOrderTraverse(root->right);
    }
}

例如，对于下图所示的二叉树：

     1
   /   \
  2     3
 / \   / \
4   5  6  7

它的前序遍历结果为: 1 2 4 5 3 6 7

3.中序遍历二叉树

中序遍历的顺序是：先遍历左子树，再访问根节点，最后遍历右子树。以下是一个示例代码：

void inOrderTraverse(TreeNode* root){
    if(root!=NULL) {
        inOrderTraverse(root->left);
        printf("%d ",root->data);
        inOrderTraverse(root->right);
    }
}

例如，对于下图所示的二叉树：

     1
   /   \
  2     3
 / \   / \
4   5  6  7

它的中序遍历结果为: 4 2 5 1 6 3 7

4.后序遍历二叉树

后序遍历的顺序是：先遍历左子树，再遍历右子树，最后访问根节点。以下是一个示例代码：

void postOrderTraverse(TreeNode* root){
    if(root!=NULL) {
        postOrderTraverse(root->left);
        postOrderTraverse(root->right);
        printf("%d ",root->data);
    }
}

例如，对于下图所示的二叉树：

     1
   /   \
  2     3
 / \   / \
4   5  6  7

它的后序遍历结果为: 4 5 2 6 7 3 1

5.层次遍历二叉树

层次遍历的顺序是：按照从上往下、从左往右的方式，逐层遍历每一个节点。以下是一个示例代码：

void levelOrderTraverse(TreeNode* root){
    if(root == NULL){
        return;
    }
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while(!isEmpty(&q)){
        TreeNode* node = dequeue(&q);
        printf("%d ", node->data);
        if(node->left != NULL) enqueue(&q, node->left);
        if(node->right != NULL) enqueue(&q, node->right);
    }
}

其中，使用队列来存储每一层的节点队列，先将根节点入队，之后每次出队一个节点并输出，再将该节点的左右子节点入队。

例如，对于下图所示的二叉树：

     1
   /   \
  2     3
 / \   / \
4   5  6  7

它的层次遍历结果为: 1 2 3 4 5 6 7

6.非递归查找

使用非递归的方式，从根节点开始查找二叉树中是否存在某个节点。以下是一个示例代码：

TreeNode* find(TreeNode* root, int val){
    if(root == NULL) return NULL;
    Stack s;
    initStack(&s);
    push(&s, root);
    while(!isEmptyStack(&s)){
        TreeNode* node = top(&s); pop(&s);
        if(node->data == val) return node;
        if(node->right != NULL) push(&s, node->right);
        if(node->left != NULL) push(&s, node->left);
    }
    return NULL;
}

其中，使用栈来存储每一个节点，先将根节点入栈，之后每次取出一个节点并比较，如果相等则返回该节点，否则将其右子节点和左子节点入栈。

7.统计节点个数

统计二叉树中节点的个数，包括根节点和左右子树中的所有节点。以下是一个示例代码：

int count(TreeNode* root){
    if(root == NULL) return 0;
    return count(root->left) + count(root->right) + 1;
}

其中，使用递归的方式遍历每一个节点，并计数。

8.二叉树比较

比较两个二叉树是否相同，相同返回 true，否则返回 false。以下是一个示例代码：

bool isEqual(TreeNode* root1, TreeNode* root2){
    if(root1 == NULL && root2 == NULL) return true;
    if(root1 == NULL || root2 == NULL) return false;
    if(root1->data != root2->data) return false;
    return isEqual(root1->left, root2->left) && isEqual(root1->right, root2->right);
}

其中，使用递归的方式分别比较两个二叉树的根节点、左子树和右子树。

9.求二叉树深度

求二叉树的深度，即二叉树的最大深度。以下是一个示例代码：

int maxDepth(TreeNode* root){
    if(root == NULL) return 0;
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return left > right ? left + 1 : right + 1;
}

其中，使用递归的方式分别求左子树和右子树的深度，并加上根节点的深度 1，最后返回较大值。

示例说明

示例一

我们输入以下数据：

1
2
4
-1
-1
5
-1
-1
3
6
-1
-1
7
-1
-1

使用示例代码中的 createBinaryTree() 方法，得到以下的二叉树：

     1
   /   \
  2     3
 / \   / \
4   5  6  7

使用示例代码中的各种遍历、查找、比较、求深度等方法可以对该二叉树进行各种操作。

示例二

我们输入以下数据：

1
-1
2
-1
3
-1

使用示例代码中的 createBinaryTree() 方法，得到以下的二叉树：

  1
   \
    2
     \
      3

使用示例代码中的各种遍历、查找、比较、求深度等方法可以对该二叉树进行各种操作，例如：

• 中序遍历结果： 1 2 3
• 非递归查找 4，结果为 NULL
• 统计节点个数为 3
• 求深度为 3

总结

二叉树是一种常用的数据结构，常用的操作包括创建、遍历、查找、比较和求深度等。掌握这些基本操作后，可根据实际需求进行扩展。