先序遍历二叉树的递归实现与非递归实现深入解析
时间：2021-05-15 09:06:11|栏目：C代码|点击： 次
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);
}
}
上一篇：C与C++ 无参函数的区别解析
栏 目：C代码
下一篇：VC++中HTControl控制类使用之CHTDlgBase对话框基类实例
本文地址：http://www.codeinn.net/misctech/121859.html
