编码技巧之数据结构【笔记】
数据结构回顾
列表中的数组，链表，队列，栈
树中的二叉树，搜索树，堆/优先队列
图中的无向图，有向图，有向无环图
图的算法中的深度优先遍历，广度优先遍历，拓扑排序和最短路径/最小生成树
树的遍历
二叉树的遍历方法：
前序遍历
先遍历树根，然后前序遍历左子树，然后再前序遍历右子树
中序遍历
先中序遍历左子树，然后遍历树根，然后再中序遍历右子树
后序遍历
先后序遍历左子树，然后后序遍历右子树，然后遍历树根
层次遍历
一层一层的遍历下去，自左向右，自上而下
树的基础代码：
package interview.tree;
public class TreeNode {
private final char value;
private TreeNode left;
private TreeNode right;
private TreeNode parent;
public TreeNode(char value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
}
public char getValue() {
return value;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
if (this.left != null) {
this.left.setParent(this);
}
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
if (this.right != null) {
this.right.setParent(this);
}
}
public TreeNode getParent() {
return parent;
}
private void setParent(TreeNode parent) {
this.parent = parent;
}
}
例题一：根据前序中序构造二叉树
我们可以发现左子树前序为BDEG，左子树中序为DBGE
具体代码如下：
package interview.tree;
public class TreeCreator {
public TreeNode createSampleTree() {
TreeNode root = new TreeNode('A');
root.setLeft(new TreeNode('B'));
root.getLeft().setLeft(new TreeNode('D'));
root.getLeft().setRight(new TreeNode('E'));
root.getLeft().getRight().setLeft(new TreeNode('G'));
root.setRight(new TreeNode('C'));
root.getRight().setRight(new TreeNode('F'));
return root;
}
public TreeNode createTree(String preOrder, String inOrder) {
if (preOrder.isEmpty()) {
return null;
}
char rootValue = preOrder.charAt(0);
int rootIndex = inOrder.indexOf(rootValue);
TreeNode root = new TreeNode(rootValue);
root.setLeft(
createTree(
preOrder.substring(1, 1 + rootIndex),
inOrder.substring(0, rootIndex)));
root.setRight(
createTree(
preOrder.substring(1 + rootIndex),
inOrder.substring(1 + rootIndex)));
return root;
}
}
TreeTraversal.java
package interview.tree;
public class TreeTraversal {
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.getValue());
preOrder(root.getLeft());
preOrder(root.getRight());
}
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.getLeft());
System.out.print(root.getValue());
inOrder(root.getRight());
}
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.print(root.getValue());
}
public String postOrder(String preOrder, String inOrder) {
if (preOrder.isEmpty()) {
return "";
}
char rootValue = preOrder.charAt(0);
int rootIndex = inOrder.indexOf(rootValue);
return
postOrder(
preOrder.substring(1, 1 + rootIndex),
inOrder.substring(0, rootIndex)) +
postOrder(
preOrder.substring(1 + rootIndex),
inOrder.substring(1 + rootIndex)) +
rootValue;
}
public static void main(String[] args) {
TreeCreator creator = new TreeCreator();
TreeTraversal traversal = new TreeTraversal();
System.out.println("Sample tree traversal");
System.out.println("=====");
TreeNode sampleTree = creator.createSampleTree();
traversal.preOrder(sampleTree);
System.out.println();
traversal.inOrder(sampleTree);
System.out.println();
traversal.postOrder(sampleTree);
System.out.println();
System.out.println("=====");
System.out.println("Creating tree from preOrder and inOrder");
System.out.println("=====");
TreeNode tree = creator.createTree("ABDEGCF", "DBGEACF");
traversal.postOrder(tree);
System.out.println();
traversal.postOrder(creator.createTree("", ""));
System.out.println();
traversal.postOrder(creator.createTree("A", "A"));
System.out.println();
traversal.postOrder(creator.createTree("AB", "BA"));
System.out.println();
System.out.println("=====");
System.out.println("Generating postOrder directly");
System.out.println("=====");
System.out.println(
traversal.postOrder("ABDEGCF", "DBGEACF"));
System.out.println(
traversal.postOrder("", ""));
System.out.println(
traversal.postOrder("A", "A"));
System.out.println(
traversal.postOrder("AB", "BA"));
}
}
总结：
在思考算法的时候，只要减小问题的规模即可
对于初始值的确定，需要严格地根据递归函数的定义
例题二：寻找中序遍历的时候的下一个结点
具体代码如下：
package interview.tree;
public class InOrder {
public TreeNode next(TreeNode node) {
if (node == null) {
return null;
}
if (node.getRight() != null) {
return first(node.getRight());
} else {
while(node.getParent() != null
&& node.getParent().getRight() == node) {
node = node.getParent();
}
// now we have:
// node.getParent() == null
// || node is left child of its parent
return node.getParent();
}
}
public TreeNode first(TreeNode root) {
if (root == null) {
return null;
}
TreeNode curNode = root;
while(curNode.getLeft() != null) {
curNode = curNode.getLeft();
}
return curNode;
}
public void traverse(TreeNode root) {
for (TreeNode node = first(root);
node != null;
node = next(node)) {
System.out.print(node.getValue());
}
System.out.println();
}
public static void main(String[] args) {
TreeCreator creator = new TreeCreator();
InOrder inOrder = new InOrder();
TreeNode sampleTree = creator.createSampleTree();
inOrder.traverse(sampleTree);
inOrder.traverse(creator.createTree("", ""));
inOrder.traverse(creator.createTree("A", "A"));
inOrder.traverse(creator.createTree("AB", "BA"));
inOrder.traverse(creator.createTree("ABCD", "DCBA"));
inOrder.traverse(creator.createTree("ABCD", "ABCD"));
}
}
总结：
需要注意的是分情况讨论
注意null指针
使用private函数来维护复杂数据结构
