先序遍历二叉树的递归实现与非递归实现深入解析
2019/7/10 23:23:57
本文主要是介绍先序遍历二叉树的递归实现与非递归实现深入解析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、先序遍历二叉树 递归实现
思想:若二叉树为空,返回。否则
1)遍历根节点;
2)先序遍历左子树;
3)先序遍历右子树;
代码:
复制代码 代码如下:
template<typename elemType>
void PreOrder(nodeType<elemType> *root)
{
if(root==NULL)
return ;
visit(root->data); // visit the data
PreOrder(root->lchild); //递归调用,先序遍历左子树
PreOrder(root->rchild); //递归调用,先序遍历右子树
}
2、先序遍历二叉树 非递归实现
思想:二叉树的非递归先序遍历,先序遍历思想:先让根进栈,只要栈不为空,就可以做弹出操作, 每次弹出一个结点,记得把它的左右结点都进栈,记得右子树先进栈,这样可以保证右子树在栈中总处于左子树的下面。
前序遍历二叉树的非递归算法思想
建立栈 Stack;
t 指向根;
当 t 不空 或 Stack 不空时反复做:
若 t 不空,访问t,t 入 栈;t 指向左子女;
否则:出栈顶元素到 t 中;
t 指向右子女;
结束
复制代码 代码如下:
void PreOrder_Nonrecursive(BinaryTree T) //先序遍历的非递归
{
if(!T) return ;
stack<BinaryTree> s;
s.push(T);
while(!s.empty())
{
BinaryTree temp = s.top();
visit(temp->data);
s.pop();
if(temp->rchild)
s.push(temp->rchild);
if(temp->lchild)
s.push(temp->lchild);
}
}
这篇关于先序遍历二叉树的递归实现与非递归实现深入解析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享