前序遍历

编辑:敬礼网互动百科 时间:2020-04-04 01:49:30
编辑 锁定
本词条缺少名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
前序遍历(DLR)是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。
中文名
前序遍历
外文名
DLR
领    域
程序设计
别    称
先根遍历、先序遍历、前序周游

前序遍历简介

编辑
前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。
二叉树为空则结束返回,否则:
(1)访问根结点。
(2)前序遍历左子树
(3)前序遍历右子树 。
前序遍历 前序遍历
需要注意的是:遍历左右子树时仍然采用前序遍历方法。
如右图所示二叉树
前序遍历结果:ABDECF
已知后序遍历和中序遍历,就能确定前序遍历。

前序遍历程序实现

编辑

前序遍历C语言版本

树中节点结构为:
typedef struct TreeNode
{
int data;
TreeNode * left;
TreeNode * right;
TreeNode * parent;
}TreeNode;
void pre_order(TreeNode * Node)
{
if(Node != NULL)
{
printf("%d ", Node->data);
pre_order(Node->left);
pre_order(Node->right);
}
}
调用时: pre_order(Root); //Root为树的根

前序遍历Pascal版本

核心代码:
procedure first(i:longint);
begin
write(a[i]);
if a[i*2]<>0 then first(i*2);
if a[i*2+1]<>0 then first(i*2+1);
end;

前序遍历Java版本

二叉树定义
publicclassTreeNode{
intval;
TreeNodeleft;
TreeNoderight;
TreeNode(intx){
val=x;
}
}
递归实现
publicvoidpreOrder(TreeNodebiTree){
System.out.printf(biTree.val+"");
TreeNodeleftTree=biTree.left;
if(leftTree!=null){
preOrder(leftTree);
}
TreeNoderightTree=biTree.right;
if(rightTree!=null){
preOrder(rightTree);
}
}
非递归实现
publicvoidpreOrder(TreeNodebiTree){
Stack<TreeNode>stack=newStack<TreeNode>();
while(biTree!=null||!stack.isEmpty()){
while(node!=null){
    System.out.print(biTree.value+",");
    stack.push(biTree);
    biTree=biTree.left;
    }
    if(!stack.isEmpty()){
    biTree=stack.pop();
    biTree=biTree.right;
    }
}
}
词条标签:
计算机学