## 二叉树——BinaryTree 非递归遍历算法（Java） 原

Jagery

1. 结点类BinaryNode

``````public class BinaryNode<T> {
public T data;
public BinaryNode<T> left ,right;

public BinaryNode(T data, BinaryNode<T> left,BinaryNode<T> right){
this.data = data;
this.left = left;
this.right = right;
}
public BinaryNode(T data){
this(data,null,null);
}
public BinaryNode(){this(null,null,null);};

@Override
public String toString() {
return data.toString();
}
}``````

2. 二叉树实现类BinaryTree

``````import java.util.Deque;

/**
* Created by jagery on 7/5/16.
*/
public class BinaryTree<T> implements BinaryTTree<T> {

public BinaryNode<T> root;
public BinaryTree(){this.root = null;}
//递归前根
public void preOrder() {

System.out.print("pre order:");
preOrder(root);
System.out.println();
}
//非递归前根
public void preOrderTraverse(BinaryNode<T> p){
BinaryNode<T> q = p;
System.out.print("pre Order Traverse: ");
while(q!=null || !stack.isEmpty()){
if(q!=null){
System.out.print(q.data.toString()+" ");
if(q.right!=null){
stack.push(q.right);
}
q = q.left;
}else{
q = stack.pop();
}
}
System.out.println();
}
private void preOrder(BinaryNode<T> p){
if(p!=null){
System.out.print(p.data.toString()+" ");
preOrder(p.left);
preOrder(p.right);
}
}
//递归中根
public void inOrder() {

System.out.print("in order:");
inOrder(root);
System.out.println();
}
private void inOrder(BinaryNode<T> p){
if(p!=null){
inOrder(p.left);
System.out.print(p.data.toString()+" ");
inOrder(p.right);
}
}
//非递归中根
public void inOrderTraverse(BinaryNode<T> p){
BinaryNode<T> q = p;
System.out.print("in Order Traverse: ");
while(q!=null || !stack.isEmpty()){
if(q!=null){
stack.push(q);
q = q.left;
}else{
q = stack.pop();
System.out.print(q.data.toString()+" ");
q = q.right;
}
}
System.out.println();
}
//递归后根
public void postOrder() {

System.out.print("post order:");
postOrder(root);
System.out.println();
}
//非递归后根
public void postOrderTraverse(BinaryNode<T> p) {
BinaryNode<T> q = p;
BinaryNode<T> s = null;
System.out.print("post Order Traverse: ");
while(q!=null || !stack.isEmpty()){
if(q!=null){
stack.push(q);
q = q.left;
}else{
q = stack.peek();
if(q.right!=null && q.right!=s ){
q = q.right;
}else{
q = stack.pop();
System.out.print(q.data.toString()+" ");
s = q;
q = null;
}
}
}
System.out.println();
}
private void postOrder(BinaryNode<T> p){
if(p!=null){
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data.toString()+" ");
}
}
}
``````

3. 测试类

``````public class BinaryTree_make {
public static BinaryTree<String> make(){
BinaryTree<String> bitree = new BinaryTree<String>();
BinaryNode<String> child_f,child_d,child_b,child_c;
child_d = new BinaryNode<String>("D",new BinaryNode<String>("J"),new BinaryNode<String>("G"));
child_b = new BinaryNode<String>("B",child_d,new BinaryNode<String>("K"));
child_f = new BinaryNode<String>("F",new BinaryNode<String>("H"),null);
child_c = new BinaryNode<String>("C",new BinaryNode<String>("E"),child_f);
bitree.root = new BinaryNode<String>("A",child_b,child_c);
return bitree;
}
public static void main(String args[]){
BinaryTree<String> bitree = make();
bitree.preOrder();
bitree.inOrder();
bitree.postOrder();

bitree.inOrderTraverse(bitree.root);
bitree.preOrderTraverse(bitree.root);
bitree.postOrderTraverse(bitree.root);

}
}
``````

### Jagery

0
0
Java学习资料-Java常用算法-二叉树算法

2015/01/28
0
0

03/14
0
0
【面试必备】手撕代码，你怕不怕？

Part 1.生产者-消费者问题 这绝对是属于重点了，不管是考察对于该重要模型的理解还是考察代码能力，这都是一道很好的考题，所以很有必要的，我们先来回顾一下什么是生产者-消费者问题； 问题...

01/10
0
0

AI科技大本营
2018/09/27
0
0

Feign Retryer的默认重试策略测试

1、Feign配置 @Configurationpublic class FeignConfig { @Value("\${coupon_service.url:http://localhost:8081}") private String couponServiceUrl; @Bean publ......

moon888
14分钟前
1
0

dragon_tech
16分钟前
1
0
iOS 中文拼音互转（好东西记录一下）

PinYin4Objc

_____1____
24分钟前
1
0
fabric private data实战

Hyperledger Fabric private data是1.2版本引入的新特性，fabric private data是利用旁支数据库（SideDB）来保存若干个通道成员之间的私有数据，从而在通道之上又提供了一层更灵活的数据保护...

24分钟前
1
0
es之聚合查询汇总

25分钟前
1
0