其中包含有先序遍历、中序遍历、后序遍历以及广度优先遍历四种遍历树的方法：
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{ 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 = data; 27 } 28 29 public TreeNode(Object data, TreeNode left, TreeNode right, TreeNode parent) { 30 this.data = 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 == 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 // 返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null106 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 // 返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null114 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 // 这是一个递归方法：每一棵子树的深度为其所有子树的最大深度 + 1128 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 // 返回其左右子树中较大的深度 + 1141 return max + 1;142 }143 }144 145 // 实现先序遍历146 // 1、访问根节点147 // 2、递归遍历左子树148 // 3、递归遍历右子树149 public List preIterator() {150 return preIterator(root);151 }152 153 private List preIterator(TreeNode node) {154 155 List list = new ArrayList ();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 inIterator() {178 return inIterator(root);179 }180 181 private List inIterator(TreeNode node) {182 183 List list = new ArrayList ();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 postIterator() {207 return postIterator(root);208 }209 210 private List postIterator(TreeNode node) {211 212 List list = new ArrayList ();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 breadthFirst() {234 235 Queue queue = new ArrayDeque ();236 List list = new ArrayList ();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 }