数据结构算法 (树的基本算法)

一、树的序列化和反序列化

1) 将二叉树进行序列化和反序列化; 使用的是前序.

 1 package com.tree;
 2 
 3 import java.util.LinkedList;
 4 import java.util.Queue;
 5 
 6 // 将一个两叉树 序列化成 字符串 ; 
 7 // 和将一字符串 反序列为一个树.
 8 public class TreeNode_Serialization {
 9     public static void main(String[] args) {
10         TreeNode_Serialization s = new TreeNode_Serialization();
11         String str = "2!3!10!#!#!12!123!#!#!#!18!100!#!#!#!"; // 前序
12         TreeNode node = s.pre_deserializationTreeNode(str);
13         s.test(node);
14         System.out.println();
15         System.out.println(s.pre_serializTreeNode(node));
16     }
17     // 将一个两叉树 序列化成 字符串
18     public String pre_serializTreeNode(TreeNode tree) {
19         if (tree == null) {
20             return "#!";
21         }
22         String str = tree.val + "!";
23         str += pre_serializTreeNode(tree.left);
24         str += pre_serializTreeNode(tree.right);
25         return str;
26     }
27     // 将一个 字符串 反序列为一个树;// 前序遍历反序列化
28     public TreeNode pre_deserializationTreeNode(String str) {
29         String[] arrStr = str.split("!");
30         Queue<String> qu = new LinkedList<String>();
31         for (String s : arrStr) {
32             qu.add(s);
33         }
34         return pre_deserializationTreeNodeCore(qu);
35     }
36     // 前序遍历反序列化。
37     private TreeNode pre_deserializationTreeNodeCore(Queue<String> qu) {
38         String str = qu.poll();
39         TreeNode tree = new TreeNode();
40         if ("#".equals(str)) {
41             return null;
42         }
43         tree.left = pre_deserializationTreeNodeCore(qu);
44         tree.val = Integer.valueOf(str);
45         tree.right = pre_deserializationTreeNodeCore(qu);
46         return tree;
47     }
48     public void test(TreeNode tree) {
49         if (tree != null) {
50             test(tree.left);
51             System.out.print(tree.val + " ");
52             test(tree.right);
53         }
54     }
55 }

View Code

2) 将二叉树进行序列化和反序列化; 使用的是层次遍历.

二、树的遍历（前中后【递归与非递归】，层次，显示结构的层次遍历）

1）树的非递归遍历（前中后）

  1 package tree;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Arrays;
  5 import java.util.LinkedList;
  6 import java.util.List;
  7 import java.util.Queue;
  8 import java.util.Stack;
  9 
 10 public class BinaryTreeTraversal_Preorder_Inorder_Postorder {
 11     public static void main(String[] args) {
 12         BinaryTreeTraversal_Preorder_Inorder_Postorder d = new BinaryTreeTraversal_Preorder_Inorder_Postorder();
 13         String[] pre_arrs = { "2", "1", "4", "#", "#", "6", "#", "#", "3","99","#", "#",
 14                 "#" };
 15         Queue<String> queue = new LinkedList<String>();
 16         for (String s : pre_arrs) {
 17             queue.add(s);
 18         }
 19         TreeNode root = preCreateTreeNode(queue);
 20         List<Integer> list1 = d.preorderTraversal(root);
 21          List<Integer> list2 = d.inorderTraversal(root);
 22         List<Integer> list3 = d.postorderTraversal(root);
 23         System.out.println(Arrays.toString(list1.toArray()));
 24         System.out.println(Arrays.toString(list2.toArray()));
 25         System.out.println(Arrays.toString(list3.toArray()));
 26     }
 27 
 28     private static TreeNode preCreateTreeNode(Queue<String> queue) {
 29         String value = queue.poll();
 30         if ("#".equals(value)) {
 31             return null;
 32         }
 33         TreeNode node = new TreeNode();
 34         node.val = Integer.valueOf(value);
 35         node.left = preCreateTreeNode(queue);
 36         node.right = preCreateTreeNode(queue);
 37         return node;
 38     }
 39 
 40     private class Command {
 41         String s;
 42         TreeNode node;
 43 
 44         Command(String s, TreeNode node) {
 45             this.s = s;
 46             this.node = node;
 47         }
 48     }
 49     public List<Integer> preorderTraversal(TreeNode root) {
 50         List<Integer> result = new ArrayList<Integer>();
 51         Stack<Command> stack = new Stack<Command>();
 52         if (root == null)
 53             return result;
 54         stack.push(new Command("go", root)); // 访问每一个结点时，使用“go”
 55         while (!stack.isEmpty()) {
 56             Command command = stack.pop();
 57             if (command.s.equals("print")) { // 打印的命令
 58                 result.add(command.node.val);
 59             } else { // / 即命令是 "go"
 60                 assert command.s.equals("go");
 61                 if (command.node.right != null) {
 62                     stack.push(new Command("go", command.node.right));
 63                 }
 64                 if (command.node.left != null) {
 65                     stack.push(new Command("go", command.node.left));
 66                 }
 67                 stack.push(new Command("print", command.node));
 68             }
 69         }
 70         return result;
 71     }
 72     public List<Integer> inorderTraversal(TreeNode root) {
 73         List<Integer> result = new ArrayList<Integer>();
 74         Stack<Command> stack = new Stack<Command>();
 75         if (root == null)
 76             return result;
 77         stack.push(new Command("go", root)); // 访问每一个结点时，使用“go”
 78         while (!stack.isEmpty()) {
 79             Command command = stack.pop();
 80             if (command.s.equals("print")) { // 打印的命令
 81                 result.add(command.node.val);
 82             } else { // / 即命令是 "go"
 83                 assert command.s.equals("go");
 84                 if (command.node.right != null) {
 85                     stack.push(new Command("go", command.node.right));
 86                 }
 87                 stack.push(new Command("print", command.node));
 88                 if (command.node.left != null) {
 89                     stack.push(new Command("go", command.node.left));
 90                 }
 91             }
 92         }
 93         return result;
 94     }
 95 
 96     public List<Integer> postorderTraversal(TreeNode root) {
 97         List<Integer> result = new ArrayList<Integer>();
 98         Stack<Command> stack = new Stack<Command>();
 99         if (root == null)
100             return result;
101         stack.push(new Command("go", root)); // 访问每一个结点时，使用“go”
102         while (!stack.isEmpty()) {
103             Command command = stack.pop();
104             if (command.s.equals("print")) { // 打印的命令
105                 result.add(command.node.val);
106             } else { // / 即命令是 "go"
107                 assert command.s.equals("go");
108                 stack.push(new Command("print", command.node));
109                 if (command.node.right != null) {
110                     stack.push(new Command("go", command.node.right));
111                 }
112                 if (command.node.left != null) {
113                     stack.push(new Command("go", command.node.left));
114                 }
115             }
116         }
117         return result;
118     }
119 
120 }

View Code

2）树的层次遍历，并显示树的层次

 1  public List<List<Integer>> hierarch(TreeNode root) {
 2         List<List<Integer>> result = new ArrayList<List<Integer>>();
 3         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 4         if (root == null)
 5             return result;
 6         queue.add(root);
 7         while (!queue.isEmpty()) {
 8             int size = queue.size();
 9             List<Integer> line = new ArrayList<Integer>();
10             for (int i = 0; i < size; i++) {
11                 TreeNode node = queue.poll();
12                 line.add(node.val);
13                 if (node.left != null) {
14                     queue.add(node.left);
15                 }
16                 if (node.right != null) {
17                     queue.add(node.right);
18                 }
19             }
20             result.add(line);
21             
22         }
23         return result;
24     }

View Code

数据结构算法 (树 的基本算法)

数据结构算法 (树的基本算法)