图解二叉树的三种遍历方式及java实现代码

图解二叉树的三种遍历方式及java实现代码

二叉树(binary tree)是一颗树，其中每个节点都不能有多于两个的儿子。

1.二叉树节点

作为图的特殊形式，二叉树的基本组成单元是节点与边；作为数据结构，其基本的组成实体是二叉树节点（binary tree node），而边则对应于节点之间的相互引用。

如下，给出了二叉树节点的数据结构图示和相关代码：

// 定义节点类：

private static class BinNode {

private Object element;

private BinNode lChild;// 定义指向左子树的指针

private BinNode rChild;// 定义指向右子树的指针

public BinNode(Objehttp://ct 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 (nodhttp://e.rChild != null) {

postOrder(node.rChild);

}

list.add(node);

}

附：测试相关代码

private static BinNode root;

private static List list = new ArrayList();

public static void main(String[] args) {

init();

// TODO Auto-generated method stub

//preOrder(root);

//inOrder(DllEElTgProot);

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);

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。