当前位置：首页 > news >正文

二叉树——二叉树的前中后序遍历

news 2025/6/18 16:57:52

、

依据本题要求可知，我们需要将二叉树前序遍历出来的结果存放在数组内，并且这个数组是需要malloc出来的。所以首先我们需要求出这个二叉树的节点数，并根据节点数来进行malloc。

根据我们之前所学，调用函数TreeSize()应用递归求出二叉树的节点数。

创建数组之后，由于我们是需要将二叉树存放在数组内，所以我们也应当将数组下标也一并传过去，所以我们调用preOrder()函数来将数据存放在数组内。

在函数中首先我们应当判断该二叉树是否为空树，若为空树则直接返回，若不为空树，则先将该节点的数据存放在数组内，并将下标++。存放后，应用递归的思想继续调用函数。

那么代码实现如下：

int TreeSize(struct TreeNode*root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void preOrder(struct TreeNode*root,int *a,int i)
{if(root==NULL){return ;}a[i++]=root->val;preOrder(root->left,a,i);preOrder(root->right,a,i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize=TreeSize(root);int *a=(int *)malloc(sizeof(int)*(*returnSize));preOrder(root,a,0);return a;
}

提交过后我们会发现是错误的。那么我们现在来分析一下，以该二叉树为例

第一次调用preOrder()函数时，i=0，将1存放到数组下标为0的位置，i++，i=1。接着访问1的左子树，将i=1过去，将2存放到数组下标为1的位置。接着访问2的左右子树，均为空，于是返回。此时我们返回到的是第一次调用的preOrder函数中，也就是i=1 的时候。若此时继续调用preOrder()函数，传递的i值为1，那么存放数据4时将会存放到数组下标为1的位置，就会将2覆盖。

所以原本输出值应当为【1，2，4】，结果输出值为【1，4，随机值】。

由这个例子可以反映出这道题错误的原因是因为i是一个局部变量，每次调用函数时不会保存i的数值，才会导致数据覆盖的情况的出现。

那么解决方法就是，将i改为指针，传递i的地址，这样就可以避免i是局部变量而导致的问题了。

代码如下：

int TreeSize(struct TreeNode*root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void preOrder(struct TreeNode*root,int *a,int *pi)
{if(root==NULL){return ;}a[(*pi)++]=root->val;preOrder(root->left,a,pi);preOrder(root->right,a,pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize=TreeSize(root);int *a=(int *)malloc(sizeof(int)*(*returnSize));int i=0;preOrder(root,a,&i);return a;
}

中序后序遍历与前序遍历的思想一致，下面把代码贴上，大家可自行研究

//中序遍历int TreeSize(struct TreeNode*root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void preOrder(struct TreeNode*root,int*a,int *pi)
{if(root==NULL){return ;}preOrder(root->left,a,pi);a[(*pi)++]=root->val;preOrder(root->right,a,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize=TreeSize(root);int *a=(int *)malloc(sizeof(int)*(*returnSize));int i=0;preOrder(root,a,&i);return a;
}

 //后序遍历
int TreeSize(struct TreeNode*root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void preOrder(struct TreeNode*root,int*a,int *pi)
{if(root==NULL){return ;}preOrder(root->left,a,pi);preOrder(root->right,a,pi);a[(*pi)++]=root->val;}int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize=TreeSize(root);int *a=(int *)malloc(sizeof(int)*(*returnSize));int i=0;preOrder(root,a,&i);return a;
}

感兴趣的可以自行尝试一下哦~