二叉树遍历-C语言

客官°小女子只卖身不卖艺 2022-12-24 13:58 137阅读 0赞

## 二叉树遍历-C语言 ##

二叉树遍历有**先序遍历**，**中序遍历**、**后序遍历**以及面试经常遇到的**层序遍历**。往往有递归实现和非递归实现，递归实现代码简单，非递归实现往往要借助栈和队列等数据结构。  
层序遍历（往往也对应**广度优先遍历**）我在面试中遇到过三四次，借用队列还是很容易实现的。博客内容是针对[leetcode][]的代码可以通过为标准。  
多提一下递归，递归的实现主要考虑两点：  
1.终止条件，即递归如何终止；

if(root==NULL)
    	return NULL;

2.递归需要扩展到更小的规模，例如本例中从根节点分别扩展到左子节点和右子节点.  
接下来分别介绍四种遍历代码。

1.  先序遍历（pre-order traversal）：

即先遍历根节点，再遍历左子节点，最后遍历右子节点。

#include <stdio.h>
    #include <stdlib.h>
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    
    
    /**
     * Note: The returned array must be malloced, assume caller calls free().
     */
     //Q1：如何计算二叉树节点数目，即返回值returnSize
     //Q2：遍历时候如何将值val的插入位置进行更新
    int* preorderTraversal(struct TreeNode* root, int* returnSize){
        
        if(root==NULL)
        {
        
            (*returnSize)=0;                        //尽管为空，也要将returnSize置为0
            return NULL;
        }
        int node_num=0;
        int position = 0;
        find_node_num(root, &node_num);
        //printf("node_num=%d\n",node_num);
        *returnSize = node_num;
        int * ret = malloc(sizeof(int)*node_num);
        travel(root,ret,&position);
        return ret;
    }
    
    void find_node_num(struct TreeNode * root, int * node_num)
    {
        
        if(root == NULL)
            return;
        (*node_num)++;                                         //*node_num++竟然是先++
        find_node_num(root->left,node_num);
        find_node_num(root->right,node_num);
    }
    
    void travel(struct TreeNode * root, int * ret, int* position)
    {
        
        if(root==NULL)
            return;
        ret[*position]=root->val;
        //printf("%d\n",root->val);
        (*position)++;
        //travel(root,ret,position);                                //递归竟然没改变条件
        travel(root->left,ret,position);
        travel(root->right,ret,position);
    }

1.  中序遍历（In-order Traversal）：

即先查看左子节点，然后查看根节点，最后查看右子节点。对于代码来说，只需要修改travel函数中遍历顺序。

void travel(struct TreeNode * root, int * ret, int* position)
    {
        
        if(root==NULL)
            return;
        travel(root->left,ret,position);
        ret[*position]=root->val;
        //printf("%d\n",root->val);
        (*position)++;
        //travel(root,ret,position);                                //递归竟然没改变条件
        travel(root->right,ret,position);
    }

1.  后序遍历（Post-order Traversal）：

即先查看左子节点，再查看右子节点，最后查看根节点。也是仅仅修改travel函数即可。

void travel(struct TreeNode * root, int * ret, int* position)
    {
        
        if(root==NULL)
            return;
        travel(root->left,ret,position);
        //travel(root,ret,position);                                //递归竟然没改变条件
        travel(root->right,ret,position);
         ret[*position]=root->val;
        //printf("%d\n",root->val);
        (*position)++;
    }

4.层序遍历  
层序遍历[leetcode][leetcode 1]对我自身来说，需要借助队列，变形题目有类似于“Z”型打印树的节点。因为需要再创建一个队列，另外再安排一篇文章来描述吧。

[leetcode]: https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xezko3/
[leetcode 1]: https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/