共计 2194 个字符,预计需要花费 6 分钟才能阅读完成。
「算法」树和图的遍历
树
class TreeNode {
int val;
// 左子树
TreeNode left;
// 右子树
TreeNode right;
// 构造方法
TreeNode(int x) {val = x;}
}
先序遍历
递归先序遍历:
// 递归先序遍历
void recursionPreOrderTraversal(TreeNode root) {if (root != null) {
// 先序
System.out.print(root.val + " ");
recursionPreOrderTraversal(root.left);
recursionPreOrderTraversal(root.right);
}
}
在遍历完节点的左子树后接着遍历节点的右子树,为了能找到该节点,须要应用 栈来进行 暂存。
非递归先序遍历:
// 非递归先序遍历
void preOrderTraversal(TreeNode root) {
// 该栈用于暂存节点
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
// 游标
TreeNode node = root;
// 最初一个节点时,左右子树为空,并且栈也为空
while (node != null || !treeNodeStack.isEmpty()) {while (node != null) {
// 先序拜访
System.out.print(node.val + " ");
treeNodeStack.push(node);
node = node.left;
}
// 此时左子树为空,思考右子树
// 如果栈已空,无需思考
if (!treeNodeStack.isEmpty()) {
// 弹出栈顶元素
node = treeNodeStack.pop();
node = node.right;
}
}
}
中序遍历
递归中序遍历:
// 递归中序遍历
void recursionInOrderTraversal(TreeNode root) {if (root != null) {recursionInOrderTraversal(root.left);
// 中序
System.out.print(root.val + " ");
recursionInOrderTraversal(root.right);
}
}
在遍历完节点的左子树后接着遍历节点的右子树,为了能找到该节点,须要应用 栈来进行 暂存。
非递归中序遍历:
// 非递归中序遍历
void inOrderTraversal(TreeNode root) {
// 该栈用于暂存节点
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
// 游标
TreeNode node = root;
// 最初一个节点时,左右子树为空,并且栈也为空
while (node != null || !treeNodeStack.isEmpty()) {while (node != null) {treeNodeStack.push(node);
node = node.left;
}
// 此时左子树为空,思考右子树
// 如果栈已空,无需思考
if (!treeNodeStack.isEmpty()) {
// 弹出栈顶元素
node = treeNodeStack.pop();
// 中序拜访
System.out.print(node.val + " ");
node = node.right;
}
}
}
后序遍历
递归后序遍历
// 递归后序遍历
void recursionPostOrderTraversal(TreeNode root) {if (root != null) {recursionPostOrderTraversal(root.left);
recursionPostOrderTraversal(root.right);
// 后序
System.out.print(root.val + " ");
}
}
非递归后序遍历:
// 非递归后序遍历
void postOrderTraversal(TreeNode root) {
// 该栈用于暂存节点
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
// 游标
TreeNode node = root;
// 保留最初拜访节点
TreeNode lastVisit = root;
// 最初一个节点时,左右子树为空,并且栈也为空
while (node != null || !treeNodeStack.isEmpty()) {while (node != null) {treeNodeStack.push(node);
node = node.left;
}
// 查看以后栈顶元素
node = treeNodeStack.peek();
// 如果其右子树也为空,或者右子树曾经拜访
// 则能够间接输入以后节点的值
if (node.right == null || node.right == lastVisit) {
// 后序拜访
System.out.print(node.val + " ");
treeNodeStack.pop();
lastVisit = node;
node = null;
} else {
// 否则,持续遍历右子树
node = node.right;
}
}
}
图
参考
https://www.jianshu.com/p/456…
https://zhuanlan.zhihu.com/p/…
https://segmentfault.com/a/11…
正文完