时间:2021-05-19
二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子。
1.二叉树节点
作为图的特殊形式,二叉树的基本组成单元是节点与边;作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用。
如下,给出了二叉树节点的数据结构图示和相关代码:
// 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向左子树的指针 private BinNode rChild;// 定义指向右子树的指针 public BinNode(Object element, BinNode lChild, BinNode rChild) { this.element = element; this.lChild = lChild; this.rChild = rChild; } }2.递归遍历
二叉树本身并不具有天然的全局次序,故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序,间接地定义某种全局次序。
按惯例左兄弟优先于右兄弟,故若将节点及其孩子分别记作V、L和R,则下图所示,局部访问的次序可有VLR、LVR和LRV三种选择。根据节点V在其中的访问次序,三种策略也相应地分别称作先序遍历、中序遍历和后序遍历,下面将分别介绍。
2.1 先序遍历
图示:
代码实现:
/** * 对该二叉树进行前序遍历 结果存储到list中 前序遍历 */ public static void preOrder(BinNode node) { list.add(node); // 先将根节点存入list // 如果左子树不为空继续往左找,在递归调用方法的时候一直会将子树的根存入list,这就做到了先遍历根节点 if (node.lChild != null) { preOrder(node.lChild); } // 无论走到哪一层,只要当前节点左子树为空,那么就可以在右子树上遍历,保证了根左右的遍历顺序 if (node.rChild != null) { preOrder(node.rChild); } }2.2 中序遍历
图示:
代码实现:
/** * 对该二叉树进行中序遍历 结果存储到list中 */ public static void inOrder(BinNode node) { if (node.lChild != null) { inOrder(node.lChild); } list.add(node); if (node.rChild != null) { inOrder(node.rChild); } }2.3 后序遍历
实例图示:
代码实现:
/** * 对该二叉树进行后序遍历 结果存储到list中 */ public static void postOrder(BinNode node) { if (node.lChild != null) { postOrder(node.lChild); } if (node.rChild != null) { postOrder(node.rChild); } list.add(node); }附:测试相关代码
private static BinNode root; private static List<BinNode> list = new ArrayList<BinNode>(); public static void main(String[] args) { init(); // TODO Auto-generated method stub //preOrder(root); //inOrder(root); postOrder(root); for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i).element + " "); } } // 树的初始化:先从叶节点开始,由叶到根 public static void init() { BinNode b = new BinNode("b", null, null); BinNode a = new BinNode("a", null, b); BinNode c = new BinNode("c", a, null); BinNode e = new BinNode("e", null, null); BinNode g = new BinNode("g", null, null); BinNode f = new BinNode("f", e, g); BinNode h = new BinNode("h", f, null); BinNode d = new BinNode("d", c, h); BinNode j = new BinNode("j", null, null); BinNode k = new BinNode("k", j, null); BinNode m = new BinNode("m", null, null); BinNode o = new BinNode("o", null, null); BinNode p = new BinNode("p", o, null); BinNode n = new BinNode("n", m, p); BinNode l = new BinNode("l", k, n); root = new BinNode("i", d, l); }以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例为大家分享了java实现二叉树遍历的具体代码,供大家参考,具体内容如下二叉树如下:遍历结果如下:以下是实现代码:packagebinTree;impor
1、二叉树的三种遍历方式二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历即:先中后指的是访问根节点的顺序eg:先序根左右中序左根右后序左右根遍历总体思路:将树
问题如何遍历一个二叉树遍历二叉树就是访问二叉树的每一个节点二叉树父结点下先左访问,先序遍历(根左右)例如:遍历以下的二叉树遍历结果:ABDECFPython代码
0.前言前文【二叉树的概念和原理】主要介绍了树的相关概念和原理,本文主要内容为二叉树的创建及遍历的代码实现,其中包括递归遍历和栈遍历。1.二叉树的实现思路1.0
二叉树是一种非常重要的数据结构。本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历),二叉搜索树的构