C语言每日一题（49）二叉树的三种基本遍历方法

对编程一片赤诚的小吴

发布于 2024-01-31 10:28:47

900

发布于 2024-01-31 10:28:47

文章被收录于专栏：热爱编程的证据热爱编程的证据

知识点：链式二叉树、递归

思路分析

顺便说一下三种遍历的方法

前序遍历：根、左子树、右子树

中序遍历：左子树、根、右子树

后序遍历：左子树、右子树、根

以这棵树为例

以前序遍历为例，根据递归的思想，先打印根节点数据再将自己的左孩子结点和右孩子结点分别为参数调用自己，依次递归到叶子结点，即所传入参数为空时返回。

其实递归就是在自己体内调用自己，相当于有一个人给大家讲故事，故事内容是：一个人在给大家讲故事。即在故事中提到同样的故事，这就是递归。

把思想实现在题中

/**
 * 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().
 */

int BinaryTreeSize(struct TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//求二叉树结点个数
}
void PrevOrder(struct TreeNode* root,int* a,int* pi)
{
	if (root == NULL)
	{
		return;
	}
    a[(*pi)++]=root->val;
	PrevOrder(root->left,a,pi);
	PrevOrder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n=BinaryTreeSize(root);
    *returnSize=n;
    int* a=(int*)malloc(sizeof(int)*n);//动态申请一个数组，题目要求返回一个数组
    int i=0;
    PrevOrder(root,a,&i);
    return a;
   
}