专注Java教育14年 全国咨询/投诉热线:400-8080-105
动力节点LOGO图
始于2009,口口相传的Java黄埔军校
首页 hot资讯 二叉树递归遍历算法

二叉树递归遍历算法

更新时间:2022-12-30 10:51:04 来源:动力节点 浏览641次

二叉树递归遍历算法是什么?动力节点小编来告诉大家。由于树遍历规则是递归的,因此二叉树的递归遍历非常流行和方便。因此,根据二叉树的子节点优先遍历规则,递归遍历顺序有以下三种:

1.前序:访问根节点,遍历左子树,遍历右子树

2.中序:遍历左子树,访问根节点,遍历右子树

3.后序:遍历左子树,遍历右子树,访问根节点

可以概括为一些规则。首先前序遍历第一个根节点为根节点,后序遍历最后一个根节点为根节点。

其次,前序遍历的最后一个根节点是右子树的最右子节点,中序遍历的最后一个节点是根节点右子树的最右节点。三、最左根节点中序遍历第一个节点到左子树的根,后序遍历是将第一个节点作为左子树的左子节点。

从以上规律,我们可以得出以下推论。整树排序可以通过前序遍历和后序遍历推导出来。中序遍历和后序遍历可以确定一棵二叉树。前序遍历和后序遍历不能单独确定一棵二叉树。

先来写一棵二叉树的前序遍历、中序遍历和后序遍历

公共类 BinaryTree 实现 BinaryTTree {
公共二进制节点 根;
公共二叉树(){this.root=null;}
Public Boolean isEmpty(){return this.root==null;}
}
public void preOrder(){ // 前序遍历
PreOrder(root);// 调用递归方法进行预序遍历
}
公共无效预购(BinaryNode p){
如果(p!=空)
{
System.out.print(p.data.toString()+” ”);//获取根节点
preOrder(p.left);// 根据前序遍历左子树,然后递归调用
preorder(p.right);// 根据前序遍历右子树,然后递归调用
}
public void inOrder(){//中序遍历
按顺序(根);
}
公共 void inOrder(BinaryNode p)
{
如果(p!=空)
{
按顺序(p.left);
System.out.print(p.data.toString()+””);
按顺序(p.right);
}
}
public void postOrder(){//后序遍历
后订单(根);
}
public void postOrder(BinaryNode p)
{
如果(p!=空)
{
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data.toString()+””);
}
}

上面的算法是根据根节点p的定义来确定整个递归的方法,每次递归都会细化根节点p,然后找到子节点p,子节点优先。如果有子节点,则继续查找,直到没有子节点,就可以依次输出之前查找过的节点。

提交申请后,顾问老师会电话与您沟通安排学习

免费课程推荐 >>
技术文档推荐 >>