栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【数据结构与算法】【11】树的遍历算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【数据结构与算法】【11】树的遍历算法

为什么要学习树的遍历算法

二叉树的遍历方式有多种,根据每种遍历方式的不同特性,在现实中有着不同的应用价值

随着我们学得越深入越底层,就会发现二叉树的应用无处不在,很多基础技术,底层都是通过二叉树实现的

比如数据库系统、文件系统、编译系统、组织架构展示等等

我们先掌握每种遍历算法,以后再学习其具体应用时,就很容易理解了

广度优先遍历和深度优先遍历

二叉树遍历方式整体分为两大类

  • 广度优先遍历,Breadth First Search,简称BFS遍历
    这种方式先访问父节点,再访问父节点所有的直接子节点,再按此方式,对每个直接子节点下面的子树进行递归遍历
  • 深度优先遍历,Depth First Search,简称DFS遍历
    深度遍历分为好几种方式,它们的共同特征是,先遍历完一个节点下面的整个子树,再遍历下个同级节点的子树
  • 广度遍历和深度遍历的区别,可以简单概括为,广度遍历是先遍历同级节点,深度遍历是先遍历当前节点子树



深度优先遍历的几种方式

上面已经提到,深度优先遍历是先遍历当前子树,再遍历同级节点

而子树如何遍历,根据父节点的访问顺序,可分为三种方式

  • 先序遍历,Preorder Traversal
    按父节点-左子树-右子树的顺序,遍历每个节点所在的树
  • 中序遍历,Inorder Traversal
    按左子树-父节点-右子树的顺序,遍历每个节点所在的树
  • 后序遍历,Postorder Traversal
    按左子树-右子树-父节点的顺序,遍历每个节点所在的树




定义树和测试数据

我们先构建这样的一颗树,作为测试数据,然后再分别以不同的遍历算法,来遍历该树

	import java.util.LinkedList;
	import java.util.List;
	import java.util.Objects;
	
	@SuppressWarnings("all")
	public class TreeNode {
	
	    //树深度
	    public Integer depth = 0;
	
	    //数值
	    public T data = null;
	
	    //添加transient关键字,是告诉JSON等序列化功能,在序列化时忽略此字段
	    //父节点包含子节点,字节点也包含父节点,对象之间相互循环引用,会导致序列化时产生死循环
	    //可以通过transient来忽略parentNode字段,通过parentId来查找
	    public transient TreeNode parent;
	    public final LinkedList> children = new LinkedList();
	
	    //添加子节点
	    public void add(TreeNode child) {
	        child.parent = this;
	        child.depth = depth + 1;
	        children.addLast(child);
	    }
	
	    //移除子节点
	    public void remove(TreeNode child) {
	        child.parent = null;
	        child.depth = null;
	        children.remove(child);
	    }
	
	    //添加子节点
	    public void add(T data) {
	        TreeNode child = new TreeNode();
	        child.data = data;
	        child.parent = this;
	        child.depth = depth + 1;
	        children.addLast(child);
	    }
	
	    //移除子节点
	    public void remove(T data) {
	        List deleteNodes = new LinkedList();
	        for (TreeNode child : children)
	            if (Objects.equals(child.data, data)) {
	                child.parent = null;
	                child.depth = null;
	                deleteNodes.add(child);
	            }
	        children.removeAll(deleteNodes);
	    }
	
	    //打印当前子树
	    @Override
	    public String toString() {
	        String childDescription = "";
	        if (!children.isEmpty()) {
	            childDescription = childDescription + "(";
	            for (TreeNode child : children)
	                childDescription = childDescription + child.data;
	            childDescription = childDescription + ")";
	        }
	        return data + childDescription;
	    }
	}

	import java.util.List;
	
	//遍历parentNode,将其所有节点按遍历顺序存到resultList当中
	public interface ITreeTraverser {
	
	    void traverse(TreeNode parentNode, List resultList);
	}

	import java.util.LinkedList;
	import java.util.List;
	
	public class Demo {
	
	    public static TreeNode createTree() {
	        TreeNode a = new TreeNode();
	        a.data = "A";
	        TreeNode b = new TreeNode();
	        b.data = "B";
	        TreeNode c = new TreeNode();
	        c.data = "C";
	        TreeNode d = new TreeNode();
	        d.data = "D";
	        TreeNode e = new TreeNode();
	        e.data = "E";
	        TreeNode f = new TreeNode();
	        f.data = "F";
	        TreeNode g = new TreeNode();
	        g.data = "G";
	        a.add(b);
	        a.add(c);
	        b.add(d);
	        b.add(e);
	        c.add(f);
	        c.add(g);
	        return a;
	    }
	
	    public static void main(String[] args) {
	        TreeNode tree = createTree();
	        List list = new LinkedList();
	        ITreeTraverser traverser = new XXXTraverserImpl();
	        traverser.traverse(tree, list);
	        for (TreeNode node : list)
	            System.out.println(node);
	    }
	}

广度优先遍历代码实现

	import java.util.List;
	
	public class BreadthTraversal implements ITreeTraverser {
	
	    public void traverse(TreeNode parentNode, List resultList) {
	        resultList.add(parentNode);
	        for (TreeNode childNode : parentNode.children)
	            resultList.add(childNode);
	        for (TreeNode childNode : parentNode.children)
	            for (TreeNode childChildNode : childNode.children)
	                traverse(childChildNode, resultList);
	    }
	}

打印结果

A(BC)
B(DE)
C(FG)
D
E
F
G

先序遍历代码实现

	import java.util.List;
	
	public class PreorderTraversal implements ITreeTraverser {
	
	    public void traverse(TreeNode parentNode, List resultList) {
	        resultList.add(parentNode);
	        if (parentNode.children.size() >= 1) {
	            TreeNode leftChild = parentNode.children.get(0);
	            traverse(leftChild, resultList);
	        }
	        if (parentNode.children.size() >= 2) {
	            TreeNode rightChild = parentNode.children.get(1);
	            traverse(rightChild, resultList);
	        }
	    }
	}

打印结果

A(BC)
B(DE)
D
E
C(FG)
F
G

中序遍历代码实现

	import java.util.List;
	
	public class InorderTraversal implements ITreeTraverser {
	
	    public void traverse(TreeNode parentNode, List resultList) {
	        if (parentNode.children.size() >= 1) {
	            TreeNode leftChild = parentNode.children.get(0);
	            traverse(leftChild, resultList);
	        }
	        resultList.add(parentNode);
	        if (parentNode.children.size() >= 2) {
	            TreeNode rightChild = parentNode.children.get(1);
	            traverse(rightChild, resultList);
	        }
	    }
	}

打印结果

D
B(DE)
E
A(BC)
F
C(FG)
G

后序遍历代码实现

	import java.util.List;
	
	public class PostorderTraversal implements ITreeTraverser {
	
	    public void traverse(TreeNode parentNode, List resultList) {
	        if (parentNode.children.size() >= 1) {
	            TreeNode leftChild = parentNode.children.get(0);
	            traverse(leftChild, resultList);
	        }
	        if (parentNode.children.size() >= 2) {
	            TreeNode rightChild = parentNode.children.get(1);
	            traverse(rightChild, resultList);
	        }
	        resultList.add(parentNode);
	    }
	}

打印结果

D
E
B(DE)
F
G
C(FG)
A(BC)

遍历算法的基本应用

  • 广度优先遍历:如果我们想遍历整个树,找到每一层的的最大值,这种方法是最简单直观的
    比如大家开年会的时候,想要在每个级别分别选出若干个优秀员工,就可以采用这种算法
  • 深度优先遍历:可用来解析数学公式或代码语句
    比如我们要表达出a+b这种运算,就可以通过树来实现,a作为左节点,b作为右节点,+为父节点
    这样+所在的子树,就可以代表a+b的运算结果,然后再与其它子树,继续进行运算,就实现了一个数学公式解释器

下一章,我们就要专门来讲解,如何通过树来存储和计算表达式

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948724.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号