服务器之家

服务器之家 > 正文

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

时间:2020-11-29 11:44     来源/作者:Acamy丶

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

1.二叉树节点

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

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

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

java" id="highlighter_858528">
?
1
2
3
4
5
6
7
8
9
10
11
12
// 定义节点类:
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在其中的访问次序,三种策略也相应地分别称作先序遍历、中序遍历和后序遍历,下面将分别介绍。

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

2.1 先序遍历

图示:

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

代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 对该二叉树进行前序遍历 结果存储到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 中序遍历

图示:

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

代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 对该二叉树进行中序遍历 结果存储到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 后序遍历

实例图示:

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

代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 对该二叉树进行后序遍历 结果存储到list中
 */
public static void postorder(binnode node) {
  if (node.lchild != null) {
    postorder(node.lchild);
  }
  if (node.rchild != null) {
    postorder(node.rchild);
  }
  list.add(node);
}

附:测试相关代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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);
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:http://www.jianshu.com/p/f0a6d594711d

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部