同样是大伙面试时碰上几率比较高的一套类型题，跟数据结构相关的东西永远是核心... 废话不多说 直接上代码
/**
* @author luochengcheng
* 定义二叉树
*/
class Node {
private char key;
private Node left, right;
public Node(char key) {
this(key, null, null);
}
public Node(char key, Node left, Node right) {
this.key = key;
this.left = left;
this.right = right;
}
public char getKey() {
return key;
}
public void setKey(char key) {
this.key = key;
}
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;
}
}
public class BinaryTree {
protected Node root;
public BinaryTree(Node root) {
this.root = root;
}
public Node getRoot() {
return root;
}
/** 构造树 */
public static Node init() {
Node a = new Node('A');
Node b = new Node('B', null, a);
Node c = new Node('C');
Node d = new Node('D', b, c);
Node e = new Node('E');
Node f = new Node('F', e, null);
Node g = new Node('G', null, f);
Node h = new Node('H', d, g);
return h;// root
}
/** 访问节点 */
public static void visit(Node p) {
System.out.print(p.getKey() + " ");
}
/** 递归实现前序遍历 */
protected static void preorder(Node p) {
if (p != null) {
visit(p);
preorder(p.getLeft());
preorder(p.getRight());
}
}
/** 递归实现中序遍历 */
protected static void inorder(Node p) {
if (p != null) {
inorder(p.getLeft());
visit(p);
inorder(p.getRight());
}
}
/** 递归实现后序遍历 */
protected static void postorder(Node p) {
if (p != null) {
postorder(p.getLeft());
postorder(p.getRight());
visit(p);
}
}
/** 非递归实现前序遍历 */
protected static void iterativePreorder(Node p) {
Stack<Node> stack = new Stack<Node>();
if (p != null) {
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.getRight() != null)
stack.push(p.getRight());
if (p.getLeft() != null)
stack.push(p.getLeft());
}
}
}
/** 非递归实现前序遍历2 */
protected static void iterativePreorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {//压入所有的左节点，压入前访问它
visit(node);
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
node = node.getRight();
}
}
}
/** 非递归实现后序遍历 */
protected static void iterativePostorder(Node p) {
Node q = p;
Stack<Node> stack = new Stack<Node>();
while (p != null) {
// 左子树入栈
for (; p.getLeft() != null; p = p.getLeft())
stack.push(p);
// 当前节点无右子或右子已经输出
while (p != null && (p.getRight() == null || p.getRight() == q)) {
visit(p);
q = p;// 记录上一个已输出节点
if (stack.empty())
return;
p = stack.pop();
}
// 处理右子
stack.push(p);
p = p.getRight();
}
}
/** 非递归实现后序遍历 双栈法 */
protected static void iterativePostorder2(Node p) {
Stack<Node> lstack = new Stack<Node>();
Stack<Node> rstack = new Stack<Node>();
Node node = p, right;
do {
while (node != null) {
right = node.getRight();
lstack.push(node);
rstack.push(right);
node = node.getLeft();
}
node = lstack.pop();
right = rstack.pop();
if (right == null) {
visit(node);
} else {
lstack.push(node);
rstack.push(null);
}
node = right;
} while (lstack.size() > 0 || rstack.size() > 0);
}
/** 非递归实现后序遍历 单栈法*/
protected static void iterativePostorder3(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p, prev = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
Node temp = stack.peek().getRight();
if (temp == null || temp == prev) {
node = stack.pop();
visit(node);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
/** 非递归实现后序遍历4 双栈法*/
protected static void iterativePostorder4(Node p) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> temp = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
temp.push(node);
stack.push(node);
node = node.getRight();
}
if (stack.size() > 0) {
node = stack.pop();
node = node.getLeft();
}
}
while (temp.size() > 0) {
node = temp.pop();
visit(node);
}
}
/** 非递归实现中序遍历 */
protected static void iterativeInorder(Node p) {
Stack<Node> stack = new Stack<Node>();
while (p != null) {
while (p != null) {
if (p.getRight() != null)
stack.push(p.getRight());// 当前节点右子入栈
stack.push(p);// 当前节点入栈
p = p.getLeft();
}
p = stack.pop();
while (!stack.empty() && p.getRight() == null) {
visit(p);
p = stack.pop();
}
visit(p);
if (!stack.empty())
p = stack.pop();
else
p = null;
}
}
/** 非递归实现中序遍历2 */
protected static void iterativeInorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
visit(node);
node = node.getRight();
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
BinaryTree tree = new BinaryTree(init());
System.out.print(" Pre-Order:");
preorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
inorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order:");
postorder(tree.getRoot());
System.out.println();
System.out.print(" Pre-Order:");
iterativePreorder(tree.getRoot());
System.out.println();
System.out.print("Pre-Order2:");
iterativePreorder2(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
iterativeInorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order2:");
iterativeInorder2(tree.getRoot());
System.out.println();
System.out.print(" Post-Order:");
iterativePostorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order2:");
iterativePostorder2(tree.getRoot());
System.out.println();
System.out.print("Post-Order3:");
iterativePostorder3(tree.getRoot());
System.out.println();
System.out.print("Post-Order4:");
iterativePostorder4(tree.getRoot());
System.out.println();
}
}
分享到：
相关推荐
这可能意味着这个压缩包是一个学习资源，提供丰富的Java数据结构实现，帮助开发者深入理解和实践各种数据结构。 【标签】：“java”确认了这些代码与Java编程语言相关，因此我们可以期待看到如何在Java环境中实现和...
哈夫曼编码在Java中的应用不仅限于文本压缩，例如在`huffmancode_java sms_compression`标签中提及，它还可以应用于短信压缩，节省通信资源。在现代信息技术中，数据压缩技术扮演着至关重要的角色，哈夫曼编码作为一...
为了解决二叉树路径和代码示例问题，我们可以使用深度优先搜索（Depth-First Search）算法，递归遍历二叉树，查找所有路径中各节点相加总和等于给定目标值的路径。 下面是一个 Java 代码示例，用于解决二叉树路径和...
在Java编程领域，树（Tree）是一种非常重要的数据结构，广泛应用于各种算法和软件系统设计中。本资源“Java_Programming_classic_tree_parameter_code.rar”包含了一个名为“Java编程开发树参数经典代码.java”的...
在Java中实现哈夫曼编码，可以创建一个`Node`类表示二叉树节点，包含字符、频率和左右子节点。使用`PriorityQueue`来构建哈夫曼树，然后遍历树生成编码。例如，`Exam7_4.java`可能是实现这个过程的源代码文件。 ...
这个名为"Java各种排序算法代码.zip"的压缩包包含了一系列实现不同排序算法的Java源代码。排序算法是计算机科学中的基本概念，用于对一组数据进行排列。下面将详细讨论这些算法及其在Java中的实现。 1. 冒泡排序...
这种编码方式是基于频率的，通过构建一棵特殊的二叉树——哈夫曼树，为每个字符或符号分配不同的二进制编码，频率高的字符编码长度短，频率低的字符编码长度长，从而在整体上实现平均码长的最小化，达到压缩数据的...
3. `generateCodes()`方法：遍历哈夫曼树生成每个字符的哈夫曼编码。 4. `encode()`方法：将字符序列编码为二进制字符串。 5. `decode()`方法：将哈夫曼编码解码回原始字符序列。 在`HuffmanCode`这个项目中，我们...
- `code()`方法用于递归地遍历哈夫曼树，为每个叶节点（表示字符的节点）分配二进制前缀码。从根节点开始，向左走添加'0'，向右走添加'1'。当到达叶子节点时，将当前路径（即编码）保存在该节点的`code`属性中。 3...
综上所述，通过理解哈夫曼树和完全二叉树的概念，以及Java提供的数据压缩工具，开发者可以在Java项目中实现高效的数据压缩功能。这不仅可以优化存储资源，还能提升数据传输速度，特别是在处理大量文本或图像数据时，...
这个算法基于一种特殊的二叉树——哈夫曼树，通过构建这棵树来为每个字符生成唯一的前缀编码，从而达到高效的数据压缩效果。在Java编程中实现哈夫曼编码，需要理解以下几个关键概念： 1. **频率统计**：首先，我们...
`HuffmanCode.java`则负责生成Huffman编码，这通常通过遍历Huffman树并跟踪从根节点到每个叶子节点的路径来完成。每条路径可以被映射到一个唯一的二进制码，形成字符与编码的对应关系。 `CompressFrame.java`和`...
"Code for binary tree"这个压缩包可能包含了用不同编程语言实现的二叉树操作代码，比如插入、删除、搜索和遍历等操作。常见的编程语言如C++、Java、Python等都有相应的二叉树数据结构实现。通过阅读和理解这些代码...
- **深度优先遍历（Depth-First Traversal）**: 在构建哈夫曼树后，使用深度优先遍历的方式来遍历树并记录每个字符的哈夫曼编码。在示例代码中，通过 `preorder()` 方法实现了深度优先遍历的过程。 ### 4. 具体实现...
它通过创建一棵特殊的二叉树——哈夫曼树（也称为最优二叉树），来为每个字符分配一个唯一的二进制编码。在哈夫曼树中，频率较高的字符其编码通常较短，而频率较低的字符编码较长，这样可以确保高频字符在编码后占用...
8. **BitUtils.java**：这是一个工具类，包含各种位操作相关的静态方法，如将整数转换为位数组，或将位数组转换回整数等。这些方法对于在位流中编码和解码字符非常有用。 9. **HZIPOutputStream.java**：这个名字...
leetcode手册JAVA CGADS ChenGuang Algorithm and Data Structure library :sun: Keys 线性表 链表 二叉树 遍历 前序遍历 中序遍历 后序遍历 层序遍历 二叉树的序列化和反序列化 二叉树两结点的最近共同祖先结点...
Java版的赫夫曼编码计算程序是一个用于数据压缩的实用工具，它基于赫夫曼树（也称为最优二叉树）的理论。赫夫曼编码是数据压缩领域的一个基础算法，由David A. Huffman在1952年提出。这个程序可以帮助我们将文本或...
在Java编程中，"构建数组的最大MaxTree"是一个有趣且具有挑战性的算法问题。这个问题的目标是根据给定的整数数组构建一棵特殊的二叉树，称为MaxTree。在这棵树中，每个节点的值是其左子树和右子树对应节点的最大值。...
4. **遍历二叉搜索树**：主要有三种遍历方式：前序遍历、中序遍历和后序遍历。 - **前序遍历**：先访问根节点，再遍历左子树，最后遍历右子树。 ```java void preOrder(Node node) { if (node != null) { ...