一
由于本人的码云太多太乱了，于是决定一个一个的整合到一个springboot项目里面。
附上自己的github项目地址 https://github.com/247292980/spring-boot
附上汇总博文地址 https://cloud.tencent.com/developer/article/1333123
以整合功能
spring-boot，FusionChart，thymeleaf，vue，ShardingJdbc，mybatis-generator，微信分享授权，drools，spring-security，spring-jpa，webjars，Aspect，drools-drt，rabbitmq，zookeeper，mongodb，mysql存储过程，前端的延迟加载，netty，postgresql
这次就来整合下 树的遍历
没什么难的看了一上午，看完发现，真说出来我的理解，也不是你们的理解方式，所以这篇全代码好了。
递归很好理解就是非递归...debug几次，细心点就好了
ps.
广度遍历叫层次遍历，一层一层的来就简单了。
前序遍历，中序遍历，后序遍历的区别就是根在前（根左右），根在中（左根右），根在后（左右根）
在最后补全所有源码
二 广度优先遍历 层次遍历
代码语言：javascript复制 //广度优先遍历 层次遍历
public void levelIterator(TreeNode n) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(n);
while (!queue.isEmpty()) {
TreeNode t = queue.poll();
if (t != null) {
visted(t);
}
if (t.leftChild != null) {
queue.offer(t.leftChild);
}
if (t.rightChild != null) {
queue.offer(t.rightChild);
}
}
}三 前序遍历
代码语言：javascript复制 //前序遍历
public void preOrder(TreeNode subTree) {
if (subTree != null) {
visted(subTree);
preOrder(subTree.leftChild);
preOrder(subTree.rightChild);
}
}
//前序遍历的非递归实现
public void nonRecPreOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
visted(node);
stack.push(node);
node = node.leftChild;
}
if (stack.size() > 0) {
node = stack.pop();
node = node.rightChild;
}
}
}四 中序遍历
代码语言：javascript复制 //中序遍历
public void inOrder(TreeNode subTree) {
if (subTree != null) {
inOrder(subTree.leftChild);
visted(subTree);
inOrder(subTree.rightChild);
}
}
//中序遍历的非递归实现
public void nonRecInOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
while (node != null || stack.size() > 0) {
//存在左子树
while (node != null) {
stack.push(node);
node = node.leftChild;
}
//栈非空
if (stack.size() > 0) {
node = stack.pop();
visted(node);
node = node.rightChild;
}
}
}五 后序遍历
代码语言：javascript复制//后续遍历
public void postOrder(TreeNode subTree) {
if (subTree != null) {
postOrder(subTree.leftChild);
postOrder(subTree.rightChild);
visted(subTree);
}
}
//后序遍历的非递归实现
public void noRecPostOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
while (p != null) {
//左子树入栈
for (; p.leftChild != null; p = p.leftChild) {
stack.push(p);
}
//当前结点无右子树或右子树已经输出
while (p != null && (p.rightChild == null || p.rightChild == node)) {
visted(p);
//纪录上一个已输出结点
node = p;
if (stack.empty()) {
return;
}
p = stack.pop();
}
//处理右子树
stack.push(p);
p = p.rightChild;
}
}六 源码
代码语言：javascript复制public class TreeNode {
public int key;
public String data;
public TreeNode leftChild;
public TreeNode rightChild;
public boolean isVisted = false;
public TreeNode(int key, String data) {
this.key = key;
this.data = data;
}
public TreeNode(int key, String data, TreeNode leftChild, TreeNode rightChild) {
this.key = key;
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
public class BinaryTree {
private TreeNode root = null;
public BinaryTree() {
root = new TreeNode(1, "rootNode(A)");
}
/**
* 创建一棵二叉树
* A
* B C
* D E F
* X M N
* @param root
*/
public void createBinTree(TreeNode root) {
TreeNode newNodeB = new TreeNode(2, "B");
TreeNode newNodeC = new TreeNode(3, "C");
TreeNode newNodeD = new TreeNode(4, "D");
TreeNode newNodeE = new TreeNode(5, "E");
TreeNode newNodeF = new TreeNode(6, "F");
root.leftChild = newNodeB;
root.rightChild = newNodeC;
root.leftChild.leftChild = newNodeD;
root.leftChild.rightChild = newNodeE;
root.rightChild.rightChild = newNodeF;
root.leftChild.rightChild.leftChild = new TreeNode(7, "M");
root.leftChild.rightChild.rightChild = new TreeNode(8, "N");
root.leftChild.leftChild.rightChild = new TreeNode(9, "X");
}
public boolean isEmpty() {
return root == null;
}
//树的高度
public int height() {
return height(root);
}
//节点个数
public int size() {
return size(root);
}
private int height(TreeNode subTree) {
if (subTree == null) {
//递归结束：空树高度为0
return 0;
} else {
int i = height(subTree.leftChild);
int j = height(subTree.rightChild);
return (i < j) ? (j 1) : (i 1);
}
}
private int size(TreeNode subTree) {
if (subTree == null) {
return 0;
} else {
return 1 size(subTree.leftChild)
size(subTree.rightChild);
}
}
//返回双亲结点
public TreeNode parent(TreeNode element) {
return (root == null || root == element) ? null : parent(root, element);
}
public TreeNode parent(TreeNode subTree, TreeNode element) {
if (subTree == null) {
return null;
}
if (subTree.leftChild == element || subTree.rightChild == element) {
//返回父结点地址
return subTree;
}
TreeNode p;
//现在左子树中找，如果左子树中没有找到，才到右子树去找
if ((p = parent(subTree.leftChild, element)) != null) {
//递归在左子树中搜索
return p;
} else {
//递归在右子树中搜索
return parent(subTree.rightChild, element);
}
}
public TreeNode getLeftChildNode(TreeNode element) {
return (element != null) ? element.leftChild : null;
}
public TreeNode getRightChildNode(TreeNode element) {
return (element != null) ? element.rightChild : null;
}
public TreeNode getRoot() {
return root;
}
//在释放某个结点时，该结点的左右子树都已经释放，
//所以应该采用后续遍历，当访问某个结点时将该结点的存储空间释放
public void destroy(TreeNode subTree) {
//删除根为subTree的子树
if (subTree != null) {
//删除左子树
destroy(subTree.leftChild);
//删除右子树
destroy(subTree.rightChild);
//删除根结点
subTree = null;
}
}
public void visted(TreeNode subTree) {
subTree.isVisted = true;
System.out.println("key:" subTree.key "--name:" subTree.data);
}
//前序遍历
public void preOrder(TreeNode subTree) {
if (subTree != null) {
visted(subTree);
preOrder(subTree.leftChild);
preOrder(subTree.rightChild);
}
}
//中序遍历
public void inOrder(TreeNode subTree) {
if (subTree != null) {
inOrder(subTree.leftChild);
visted(subTree);
inOrder(subTree.rightChild);
}
}
//后续遍历
public void postOrder(TreeNode subTree) {
if (subTree != null) {
postOrder(subTree.leftChild);
postOrder(subTree.rightChild);
visted(subTree);
}
}
//前序遍历的非递归实现 ABDXEMNCF
public void nonRecPreOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
visted(node);
stack.push(node);
node = node.leftChild;
}
if (stack.size() > 0) {
node = stack.pop();
node = node.rightChild;
}
}
}
//中序遍历的非递归实现
public void nonRecInOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
while (node != null || stack.size() > 0) {
//存在左子树
while (node != null) {
stack.push(node);
node = node.leftChild;
}
//栈非空
if (stack.size() > 0) {
node = stack.pop();
visted(node);
node = node.rightChild;
}
}
}
//后序遍历的非递归实现
public void noRecPostOrder(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = p;
while (p != null) {
//左子树入栈
for (; p.leftChild != null; p = p.leftChild) {
stack.push(p);
}
//当前结点无右子树或右子树已经输出
while (p != null && (p.rightChild == null || p.rightChild == node)) {
visted(p);
//纪录上一个已输出结点
node = p;
if (stack.empty()) {
return;
}
p = stack.pop();
}
//处理右子树
stack.push(p);
p = p.rightChild;
}
}
//层次遍历 广度优先遍历
public void levelIterator(TreeNode n) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(n);
while (!queue.isEmpty()) {
TreeNode t = queue.poll();
if (t != null) {
visted(t);
}
if (t.leftChild != null) {
queue.offer(t.leftChild);
}
if (t.rightChild != null) {
queue.offer(t.rightChild);
}
}
}
//测试
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.createBinTree(bt.root);
System.out.println("the size of the tree is " bt.size());
System.out.println("the height of the tree is " bt.height());
System.out.println("*******(前序遍历)遍历*****************");
bt.preOrder(bt.root);
System.out.println("*******(中序遍历)遍历*****************");
bt.inOrder(bt.root);
System.out.println("*******(后序遍历)遍历*****************");
bt.postOrder(bt.root);
System.out.println("层次遍历*****************");
bt.levelIterator(bt.root);
System.out.println("***非递归实现****(前序遍历)遍历*****************");
bt.nonRecPreOrder(bt.root);
System.out.println("***非递归实现****(中序遍历)遍历*****************");
bt.nonRecInOrder(bt.root);
System.out.println("***非递归实现****(后序遍历)遍历*****************");
bt.noRecPostOrder(bt.root);
}
}
