数据结构算法 (树的基本算法)-白红宇

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

阅读量：5311 次

发布时间：2019-06-14

本文共 6508 字，大约阅读时间需要 21 分钟。

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

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
      
        qu = new LinkedList
       
        ();31         for (String s : arrStr) {32             qu.add(s);33         }34         return pre_deserializationTreeNodeCore(qu);35     }36     // 前序遍历反序列化。37     private TreeNode pre_deserializationTreeNodeCore(Queue
        
          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
      
        queue = new LinkedList
       
        (); 16         for (String s : pre_arrs) { 17             queue.add(s); 18         } 19         TreeNode root = preCreateTreeNode(queue); 20         List
        
          list1 = d.preorderTraversal(root); 21          List
         
           list2 = d.inorderTraversal(root); 22         List
          
            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
           
             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
            
              preorderTraversal(TreeNode root) { 50 List
             
               result = new ArrayList
              
               (); 51 Stack
                stack = new Stack
               (); 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
               
                 inorderTraversal(TreeNode root) { 73 List
                
                  result = new ArrayList
                 
                  (); 74 Stack
                   stack = new Stack
                  (); 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
                  
                    postorderTraversal(TreeNode root) { 97 List
                   
                     result = new ArrayList
                    
                     (); 98 Stack
                      stack = new Stack
                     (); 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
      
       
        > hierarch(TreeNode root) { 2         List
        
         
          > result = new ArrayList
          
           
            >(); 3 Queue
            
              queue = new LinkedList
             
              (); 4 if (root == null) 5 return result; 6 queue.add(root); 7 while (!queue.isEmpty()) { 8 int size = queue.size(); 9 List
              
                line = new ArrayList
               
                ();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 }