树及树的遍历

程序员文章站 2022-03-14 18:41:39

...

为什么80%的码农都做不了架构师？>>> 树及树的遍历

1 树

树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。

1.1 树的一些概念

树及树的遍历

树还可以表示成下面这种方式：

树及树的遍历

从上图可以看出：树可以用来描述包含关系，但包含关系不得出现交叉重叠区域，否则就不能用树描述。

2 树的遍历

2.1 广度优先遍历

树及树的遍历

对于树的广度优先遍历，可以使用队列来完成。

示例：

树节点类：

public class Node {
	private String name;
	private List<Node> childs;

	public Node(String name) {
		super();
		this.name = name;
	}

	public String getName() {
		return name;
	}

	public List<Node> getChilds() {
		return childs;
	}

	public void setChilds(List<Node> childs) {
		this.childs = childs;
	}
}

测试代码：

public class Test {

	public static void main(String[] args) {
		// 构造节点
		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node j = new Node("J");
		Node k = new Node("K");
		Node l = new Node("L");

		// 构造树
		a.setChilds(Arrays.asList(b, c, d));
		b.setChilds(Arrays.asList(e, f));
		d.setChilds(Arrays.asList(g, h, i));
		f.setChilds(Arrays.asList(j, k));
		h.setChilds(Arrays.asList(l));

		// 创建队列
		Queue<Node> que = new ArrayDeque<Node>();

		que.offer(a);

		// 操作队列
		while (!que.isEmpty()) {
			Node temp = que.poll();
			System.out.print(temp.getName());

			List<Node> childs = temp.getChilds();

			if (childs != null) {
				for (int iter = 0; iter < childs.size(); iter++) {
					que.offer(childs.get(iter));
				}
			}
		}
	}
}

输出结果

ABCDEFGHIJKL

队列的状况如下图：

树及树的遍历

2.2 深度优先遍历

深度有限遍历分为：前序遍历（Preorder Traversal），后序遍历（Postorder Traversal）和中序遍历（Inorder Traversal）。

树及树的遍历

其中中序遍历只有对二叉树才有意义。

树：

树及树的遍历

2.2.1 前序遍历：

package com.demo2;

import java.util.List;

//树节点
public class Node {
	private String name;
	private List<Node> childs;

	public Node(String name) {
		super();
		this.name = name;
	}

	public String getName() {
		return name;
	}

	public List<Node> getChilds() {
		return childs;
	}

	public void setChilds(List<Node> childs) {
		this.childs = childs;
	}

	@Override
	public String toString() {
		return this.name;
	}
}

package com.demo2;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

//测试类
public class Test {
	public static void main(String[] args) {
		// 构造节点
		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node j = new Node("J");
		Node k = new Node("K");
		Node l = new Node("L");

		// 构造树
		a.setChilds(Arrays.asList(b, c, d));
		b.setChilds(Arrays.asList(e, f));
		d.setChilds(Arrays.asList(g, h, i));
		f.setChilds(Arrays.asList(j, k));
		h.setChilds(Arrays.asList(l));

		// 创建栈
		Deque<Node> que = new ArrayDeque<Node>();
		que.push(a);

		// 前序遍历
		System.out.println("前序遍历");
		while (!que.isEmpty()) {
			Node nodeTemp = que.pop();

			System.out.print(nodeTemp.getName());

			List<Node> childs = nodeTemp.getChilds();

			if (childs != null) {
				for (int iter = childs.size() - 1; iter >= 0; iter--) {
					que.push(childs.get(iter));
				}
			}
		}

	}
}

输出结果：

前序遍历
ABEFJKCDGHLI

2.2.2 后序遍历：

后序遍历需要标识“节点是否已经将它的子节点入栈”。因此，在树节点类Node中添加了一个属性boolean mark，mark为true时，表示该节点已经将它的子节点入栈；false表示还没有将该节点的子节点入栈。

package com.demo3;

import java.util.List;

//树节点类
public class Node {
	private String name;
	private List<Node> childs;
	private boolean mark;

	public Node(String name) {
		super();
		this.name = name;
		this.mark = false;
	}

	public String getName() {
		return name;
	}

	public List<Node> getChilds() {
		return childs;
	}

	public void setChilds(List<Node> childs) {
		this.childs = childs;
	}

	public boolean isMark() {
		return mark;
	}

	public void setMark(boolean mark) {
		this.mark = mark;
	}

	@Override
	public String toString() {
		return this.name;
	}
}

package com.demo3;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

//测试
public class Test {
	public static void main(String[] args) {
		// 构造节点
		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node j = new Node("J");
		Node k = new Node("K");
		Node l = new Node("L");

		// 构造树
		a.setChilds(Arrays.asList(b, c, d));
		b.setChilds(Arrays.asList(e, f));
		d.setChilds(Arrays.asList(g, h, i));
		f.setChilds(Arrays.asList(j, k));
		h.setChilds(Arrays.asList(l));

		// 创建栈
		Deque<Node> que = new ArrayDeque<Node>();
		que.push(a);

		// 后序遍历
		System.out.println("后序遍历");
		while (!que.isEmpty()) {
			Node nodeTemp = que.peek();

			if (nodeTemp.isMark()) {
				Node node = que.pop();
				System.out.print(node.getName());
			} else {
				List<Node> childs = nodeTemp.getChilds();
				if (childs != null) {
					for (int iter = childs.size() - 1; iter >= 0; iter--) {
						que.push(childs.get(iter));
					}
				}

				nodeTemp.setMark(true);
			}
		}

	}
}

输出结果：

后序遍历
EJKFBCGLHIDA

2.2.3 二叉树的中序遍历

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点P，

1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；

2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；

3)直到P为NULL并且栈为空则遍历结束

二叉树

树及树的遍历

//二叉树节点类
public class Node {
	private String name;

	private Node left;
	private Node right;

	public Node(String name) {
		super();
		this.name = name;
	}

	public String getName() {
		return name;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	@Override
	public String toString() {
		return this.name;
	}
}

import java.util.ArrayDeque;
import java.util.Deque;

//测试
public class Test {

	public static void main(String[] args) {
		// 构造节点
		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node j = new Node("J");

		// 构造树
		a.setLeft(b);
		a.setRight(c);
		b.setLeft(d);
		b.setRight(e);
		c.setLeft(f);
		c.setRight(g);
		e.setLeft(h);
		e.setRight(i);
		g.setLeft(j);

		// 创建栈
		Deque<Node> que = new ArrayDeque<Node>();

		Node currNode = a;

		// 中序遍历算法
		System.out.println("中序遍历：");
		while (currNode != null || !que.isEmpty()) {
			while (currNode != null) {
				que.push(currNode);
				currNode = currNode.getLeft();
			}

			currNode = que.pop();
			System.out.print(currNode.getName());

			currNode = currNode.getRight();
		}
	}
}

输出结果：

中序遍历：
DBHEIAFCJG

转载于:https://my.oschina.net/sunchp/blog/384163

上一篇： C++ 优秀图书一览 C#CC++FP编程

下一篇：解析dump的几种方式

树及树的遍历

php可应用于面包屑导航的迭代寻找家谱树实现方法，应用于家谱

PHP遍历数组的三种方法及效率对比分析_PHP

实现基于php和MySQL的动态树型菜单_MySQL

Python实现简单字典树的方法介绍

关于树型结构的表，在hibernate中如何配置。 HibernateJavaAccess

下拉树(下拉页面)的实现 AjaxDWRJavaScript框架脚本

Java实现二叉树的建立、计算高度与递归输出操作示例

浅谈二叉查找树的集合总结分析

Asp.net下拉树的实现过程

Python简单遍历字典及删除元素的方法