首页 > 代码库 > Java中树和树的几种常规遍历方法
Java中树和树的几种常规遍历方法
其中包含有先序遍历、中序遍历、后序遍历以及广度优先遍历四种遍历树的方法：
1 package com.ietree.basic.datastructure.tree.binarytree; 2 3 import java.util.ArrayDeque; 4 import java.util.ArrayList; 5 import java.util.List; 6 import java.util.Queue; 7 8 /** 9 * Created by ietree 10 * 2017/5/1 11 */ 12 public class ThreeLinkBinTree<E> { 13 14 public static class TreeNode { 15 16 Object data; 17 TreeNode left; 18 TreeNode right; 19 TreeNode parent; 20 21 public TreeNode() { 22 23 } 24 25 public TreeNode(Object data) { 26 this.data =http://www.mamicode.com/ data; 27 } 28 29 public TreeNode(Object data, TreeNode left, TreeNode right, TreeNode parent) { 30 this.data =http://www.mamicode.com/ data; 31 this.left = left; 32 this.right = right; 33 this.parent = parent; 34 } 35 36 } 37 38 private TreeNode root; 39 40 // 以默认的构造器创建二叉树 41 public ThreeLinkBinTree() { 42 this.root = new TreeNode(); 43 } 44 45 // 以指定根元素创建二叉树 46 public ThreeLinkBinTree(E data) { 47 this.root = new TreeNode(data); 48 } 49 50 /** 51 * 为指定节点添加子节点 52 * 53 * @param parent 需要添加子节点的父节点的索引 54 * @param data 新子节点的数据 55 * @param isLeft 是否为左节点 56 * @return 新增的节点 57 */ 58 public TreeNode addNode(TreeNode parent, E data, boolean isLeft) { 59 60 if (parent == null) { 61 throw new RuntimeException(parent + "节点为null， 无法添加子节点"); 62 } 63 if (isLeft && parent.left != null) { 64 throw new RuntimeException(parent + "节点已有左子节点，无法添加左子节点"); 65 } 66 if (!isLeft && parent.right != null) { 67 throw new RuntimeException(parent + "节点已有右子节点，无法添加右子节点"); 68 } 69 70 TreeNode newNode = new TreeNode(data); 71 if (isLeft) { 72 // 让父节点的left引用指向新节点 73 parent.left = newNode; 74 } else { 75 // 让父节点的left引用指向新节点 76 parent.right = newNode; 77 } 78 // 让新节点的parent引用到parent节点 79 newNode.parent = parent; 80 return newNode; 81 } 82 83 // 判断二叉树是否为空 84 public boolean empty() { 85 // 根据元素判断二叉树是否为空 86 return root.data =http://www.mamicode.com/= null; 87 } 88 89 // 返回根节点 90 public TreeNode root() { 91 if (empty()) { 92 throw new RuntimeException("树为空，无法访问根节点"); 93 } 94 return root; 95 } 96 97 // 返回指定节点（非根节点）的父节点 98 public E parent(TreeNode node) { 99 if (node == null) { 100 throw new RuntimeException("节点为null，无法访问其父节点"); 101 } 102 return (E) node.parent.data; 103 } 104 105 // 返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null 106 public E leftChild(TreeNode parent) { 107 if (parent == null) { 108 throw new RuntimeException(parent + "节点为null，无法添加子节点"); 109 } 110 return parent.left == null ? null : (E) parent.left.data; 111 } 112 113 // 返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null 114 public E rightChild(TreeNode parent) { 115 if (parent == null) { 116 throw new RuntimeException(parent + "节点为null，无法添加子节点"); 117 } 118 return parent.right == null ? null : (E) parent.right.data; 119 } 120 121 // 返回该二叉树的深度 122 public int deep() { 123 // 获取该树的深度 124 return deep(root); 125 } 126 127 // 这是一个递归方法：每一棵子树的深度为其所有子树的最大深度 + 1 128 private int deep(TreeNode node) { 129 if (node == null) { 130 return 0; 131 } 132 // 没有子树 133 if (node.left == null && node.right == null) { 134 return 1; 135 } else { 136 int leftDeep = deep(node.left); 137 int rightDeep = deep(node.right); 138 // 记录其所有左、右子树中较大的深度 139 int max = leftDeep > rightDeep ? leftDeep : rightDeep; 140 // 返回其左右子树中较大的深度 + 1 141 return max + 1; 142 } 143 } 144 145 // 实现先序遍历 146 // 1、访问根节点 147 // 2、递归遍历左子树 148 // 3、递归遍历右子树 149 public List<TreeNode> preIterator() { 150 return preIterator(root); 151 } 152 153 private List<TreeNode> preIterator(TreeNode node) { 154 155 List<TreeNode> list = new ArrayList<TreeNode>(); 156 // 处理根节点 157 list.add(node); 158 159 // 递归处理左子树 160 if (node.left != null) { 161 list.addAll(preIterator(node.left)); 162 } 163 164 // 递归处理右子树 165 if (node.right != null) { 166 list.addAll(preIterator(node.right)); 167 } 168 169 return list; 170 171 } 172 173 // 实现中序遍历 174 // 1、递归遍历左子树 175 // 2、访问根节点 176 // 3、递归遍历右子树 177 public List<TreeNode> inIterator() { 178 return inIterator(root); 179 } 180 181 private List<TreeNode> inIterator(TreeNode node) { 182 183 List<TreeNode> list = new ArrayList<TreeNode>(); 184 185 // 递归处理左子树 186 if (node.left != null) { 187 list.addAll(inIterator(node.left)); 188 } 189 190 // 处理根节点 191 list.add(node); 192 193 // 递归处理右子树 194 if (node.right != null) { 195 list.addAll(inIterator(node.right)); 196 } 197 198 return list; 199 200 } 201 202 // 实现后序遍历 203 // 1、递归遍历左子树 204 // 2、递归遍历右子树 205 // 3、访问根节点 206 public List<TreeNode> postIterator() { 207 return postIterator(root); 208 } 209 210 private List<TreeNode> postIterator(TreeNode node) { 211 212 List<TreeNode> list = new ArrayList<TreeNode>(); 213 214 // 递归处理左子树 215 if (node.left != null) { 216 list.addAll(postIterator(node.left)); 217 } 218 219 // 递归处理右子树 220 if (node.right != null) { 221 list.addAll(postIterator(node.right)); 222 } 223 224 // 处理根节点 225 list.add(node); 226 227 return list; 228 229 } 230 231 // 实现广度优先遍历 232 // 广度优先遍历又称为按层遍历，整个遍历算法先遍历二叉树的第一层（根节点），再遍历根节点的两个子节点（第二层），以此类推 233 public List<TreeNode> breadthFirst() { 234 235 Queue<TreeNode> queue = new ArrayDeque<TreeNode>(); 236 List<TreeNode> list = new ArrayList<TreeNode>(); 237 if (root != null) { 238 // 将根元素加入“队列” 239 queue.offer(root); 240 } 241 while (!queue.isEmpty()) { 242 // 将该队列的“队尾”的元素添加到List中 243 list.add(queue.peek()); 244 TreeNode p = queue.poll(); 245 // 如果左子节点不为null，将它加入“队列” 246 if (p.left != null) { 247 queue.offer(p.left); 248 } 249 // 如果右子节点不为null，将它加入“队列” 250 if (p.right != null) { 251 queue.offer(p.right); 252 } 253 } 254 return list; 255 } 256 257 }
Java中树和树的几种常规遍历方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。