您的位置: 首页  >  文章  >  树的遍历

树的遍历

分类: 文章 • 2024-11-30 16:30:10

1、树的遍历方式
二叉树的定义是递归的，一棵非空的二叉树是由根节点、左子树、右子树3个基本部分组成的，因此遍历一棵非空的二叉树的问题可分解为3个子问题：访问根节点、遍历左子树和遍历右子树。
遍历分为3种：
树的遍历
遍历结果：
（1）前序遍历二叉树: A B D E H J K M C F G
（2）中序遍历二叉树: D B H E K J M A F C G
（3）后续遍历二叉树: D H K M J E B F G C A
2、树的递归遍历
2.1、先序遍历
思路：若二叉树为空树，则空操作；否则，（1）访问根结点（或输出当前节点的值）；（2）先序遍历左子树；（3）先序遍历右子树。
代码：

// 递归先序遍历
	public static void preOrder(Node node) {
		if (node != null) {
			System.out.print(node.getData() + " ");
			preOrder(node.left);
			preOrder(node.right);
		}
	}

2.2、中序遍历
思路：若二叉树为空树，则空操作；否则，（1）先序遍历左子树；（2）访问根结点（或输出当前节点的值）；（3）先序遍历右子树。
代码：

	// 递归中序遍历
	public static void inOrder(Node node) {
		if (node!= null) {
			inOrder(node.getLeft());
			System.out.print(node.getData() + " ");
			inOrder(node.getRight());
		}
	}

2.3、后序遍历
思路：若二叉树为空树，则空操作；否则，（1）先序遍历左子树；（2）先序遍历右子树；（3）访问根结点（或输出当前节点的值）；
代码：

	// 递归后序遍历
	public static void postOrder(Node node) {
		if (node != null) {
			postOrder(node.left);
			postOrder(node.right);
			System.out.print(node.getData() + " ");
		}
	}

3、树的非递归遍历
3.1、先序遍历非递归算法
思路：
1.若根结点不为空，则将根节点放入栈

2.取出根结点，输出其值

3.若右儿子非空，将右儿子放入栈之后，若左儿子非空再将左儿子放入栈

4.若栈不为空，则获取栈顶的结点，输出该结点的值

5.若右儿子非空，将右儿子放入栈之后，若左儿子非空再将左儿子放入栈

6.步骤4和5不断重复，直到结束条件:栈空，也就是树遍历完成;

注意：因为栈是先进后出的，所以我们要先把右儿子放入栈之后，在放入左儿子，这样就保证了，先遍历左子树，在遍历有子树
代码：

// 非递归先序遍历
	public static void preOrder2(Node root) {
		Stack<Node> s = new Stack<Node>();
		if (root != null)
			s.push(root);
		// 因为栈是先进后出的，所以先放右儿子在放左儿子
		while (!s.isEmpty()) {
			root = s.pop();
			System.out.print(root.getData() + " ");
			// 将右儿子放入栈
			if (root.right != null) {
				s.push(root.right);
			}
			// 将左儿子放入栈
			if (root.left != null) {
				s.push(root.left);
			}
		}
	}

3.2、中序遍历非递归算法
代码：

// 非递归中序遍历
	public static void inOrder2(Node root) {
		Stack<Node> s = new Stack<Node>();
		Node curNode = root;
		while (curNode != null || s.size() > 0) {
			while (curNode != null) {
				s.push(curNode);
				curNode = curNode.left;
			}
			if (s.size() > 0) {
				curNode = s.pop();
				System.out.print(curNode.getData() + " ");
				curNode = curNode.right;
			}
		}
	}

3.3、后序遍历非递归算法
代码：

// 非递归后序遍历
	public static void postOrder2(Node root) {
		Stack<Node> s = new Stack<Node>();
		Node curNode = root;
		Node preNode = root;
		while (curNode != null || s.size() > 0) {
			while (curNode != null) {
				s.push(curNode);
				curNode = curNode.left;
			}
			if (s.size() > 0) {
				Node tmpNode = s.peek().right;
				if (tmpNode == null || tmpNode == preNode) {
					curNode = s.pop();
					System.out.print(curNode.getData() + " ");
					preNode = curNode;
					curNode = null;
				} else {
					curNode = tmpNode;
				}
			}
		}
	}

4、二叉树的构造代码
二叉树的构造在我以前的博客里有的，有兴趣的可以看看，附上链接：
树的构造相关知识链接
下面是我写的一个关于树的遍历的一个完整代码，欢迎各位大佬指出错误！

package com.wd.digui;

import java.util.Stack;

public class Wd_27 {

	public static void main(String[] args) throws Exception {
		// 构造一颗二叉树
		binaryTree root = new binaryTree('A');
		Node node2 = root.add(root.getRoot(), 'B', true);
		root.add(node2, 'D', true);
		Node node3 = root.add(node2, 'E', false);
		root.add(node3, 'H', true);
		Node node4 = root.add(node3, 'J', false);
		root.add(node4, 'K', true);
		root.add(node4, 'M', false);
		Node node5 = root.add(root.getRoot(), 'C', false);
		root.add(node5, 'F', true);
		root.add(node5, 'G', false);

		System.out.print("前序递归遍历：");
		preOrder(root.getRoot());
		System.out.println();

		System.out.print("中序递归遍历：");
		inOrder(root.getRoot());
		System.out.println();

		System.out.print("后序递归遍历：");
		postOrder(root.getRoot());
		System.out.println();

		System.out.print("前序非递归遍历：");
		preOrder2(root.getRoot());
		System.out.println();

		System.out.print("中序非递归遍历：");
		inOrder2(root.getRoot());
		System.out.println();

		System.out.print("后序非递归遍历：");
		postOrder2(root.getRoot());
	}

	// 递归先序遍历
	public static void preOrder(Node node) {
		if (node != null) {
			System.out.print(node.getData() + " ");
			preOrder(node.left);
			preOrder(node.right);
		}
	}

	// 递归中序遍历
	public static void inOrder(Node node) {
		if (node!= null) {
			inOrder(node.getLeft());
			System.out.print(node.getData() + " ");
			inOrder(node.getRight());
		}
	}

	// 递归后序遍历
	public static void postOrder(Node node) {
		if (node != null) {
			postOrder(node.left);
			postOrder(node.right);
			System.out.print(node.getData() + " ");
		}
	}

	// 非递归先序遍历
	public static void preOrder2(Node root) {
		Stack<Node> s = new Stack<Node>();
		if (root != null)
			s.push(root);
		// 因为栈是先进后出的，所以先放右儿子在放左儿子
		while (!s.isEmpty()) {
			root = s.pop();
			System.out.print(root.getData() + " ");
			// 将右儿子放入栈
			if (root.right != null) {
				s.push(root.right);
			}
			// 将左儿子放入栈
			if (root.left != null) {
				s.push(root.left);
			}
		}
	}

	// 非递归中序遍历
	public static void inOrder2(Node root) {
		Stack<Node> s = new Stack<Node>();
		Node curNode = root;
		while (curNode != null || s.size() > 0) {
			while (curNode != null) {
				s.push(curNode);
				curNode = curNode.left;
			}
			if (s.size() > 0) {
				curNode = s.pop();
				System.out.print(curNode.getData() + " ");
				curNode = curNode.right;
			}
		}
	}

	// 非递归后序遍历
	public static void postOrder2(Node root) {
		Stack<Node> s = new Stack<Node>();
		Node curNode = root;
		Node preNode = root;
		while (curNode != null || s.size() > 0) {
			while (curNode != null) {
				s.push(curNode);
				curNode = curNode.left;
			}
			if (s.size() > 0) {
				Node tmpNode = s.peek().right;
				if (tmpNode == null || tmpNode == preNode) {
					curNode = s.pop();
					System.out.print(curNode.getData() + " ");
					preNode = curNode;
					curNode = null;
				} else {
					curNode = tmpNode;
				}
			}
		}
	}
}

// 二叉树类
class binaryTree {
	// root表示根结点
	private Node root;

	public binaryTree(Object data) {
		root = new Node(data);
	}

	// 为指定的结点添加子节点
	public Node add(Node parent, Object data, boolean isLeft) throws Exception {
		if (parent == null || parent.data == null) {
			throw new Exception("结点为空不能添加子结点！");
		}
		Node node = null;
		if (isLeft) {
			if (parent.left != null) {
				throw new Exception("左结点不为空不能添加结点！");
			} else {
				node = new Node(data);
				parent.left = node;
			}
		} else {
			if (parent.right != null) {
				throw new Exception("右结点不为空不能添加结点！");
			} else {
				node = new Node(data);
				parent.right = node;
			}
		}
		return node;
	}

	// 判断树是否为空
	public boolean isEmpty() {
		return root.data == null;
	}

	// 获取根节点
	public Node getRoot() {
		if (isEmpty()) {
			throw new RuntimeException("树为空，不能获取根节点");
		}
		return root;

	}
}

// 树节点类
class Node {
	Object data;// 数据域
	Node left;// 左儿子
	Node right;// 右儿子

	public Node() {

	}

	public Node(Object data) {
		super();
		this.data = data;
		this.left = null;
		this.right = null;
	}

	public Node(Object data, Node left, Node right) {
		super();
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public Object getData() {
		return data;
	}

	public void setData(Object data) {
		this.data = data;
	}

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

}

运行结果：树的遍历
跟详细的参考：
树的遍历

相关推荐