代码随想录 day14 ||144.二叉树的遍历 ,145.二叉树的后序遍历 , 94.二叉树的中序遍历
144. 二叉树的前序遍历
每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!
-
确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
-
确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
3. **确定单层递归的逻辑**: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
前序遍历
中--左--右
递归实现
void preOrder1(BinTree *root) //递归前序遍历
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
中序排列
中--左--右
递归实现
void inOrder1(BinTree *root) //递归中序遍历
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}
后序遍历
左–右–中
递归实现
void postOrder1(BinTree *root) //递归后序遍历
2 {
3 if(root!=NULL)
4 {
5 postOrder1(root->lchild);
6 postOrder1(root->rchild);
7 cout<<root->data<<" ";
8 }
9 }