package tree;
import java.util.Stack;
/**
*
*
*/
class Node{
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data=data;
this.left=left;
this.right=right;
}
}
public class Binary_Tree {
public Node root;
public Binary_Tree() {
root=null;
}
//将data插到排序二叉树中
public void insert(int data) {
Node newNode=new Node(data);
if(root==null) {
root=newNode;
}
else {
Node current=root;
Node parent;
while(true) {
parent=current;
if(data<current.data) {
current=current.left;
if(current==null) {
parent.left=newNode;
return;
}
}else {
current=current.right;
if(current==null) {
parent.right=newNode;
return;
}
}
}
}
}
//将数值输入构建二叉树
public void buildTree(int[] data) {
for(int i=0;i<data.length;i++) {
insert(data[i]);
}
}
//先序遍历(递归)
public void preOrder(Node localRoot) {
if(localRoot!=null) {
System.out.print(localRoot.data+"");
if(localRoot.left!=null) {
preOrder(localRoot.left);
}
if(localRoot.right!=null) {
preOrder(localRoot.right);
}
}
}
public void preOrder() {
this.preOrder(this.root);
}
//先序遍历(非递归)
public void preOrder_1(Node localRoot) {
Stack<Node> s=new Stack<Node>();
while(localRoot!=null||!s.empty()){//节点非空或栈非空就遍历
while(localRoot!=null) {
System.out.println(localRoot.data);//压入所有左孩子节点,压入前输出
s.push(localRoot);
localRoot=localRoot.left;
}
if(!s.empty()) {
localRoot=s.pop();
localRoot=localRoot.right;
}
}
System.out.println();
}
//中序遍历(非递归)
public void InOrder_1(Node localRoot) {
Stack<Node> s=new Stack<Node>();
while(localRoot!=null||!s.empty()) {
while(localRoot!=null) {
s.push(localRoot);
localRoot=localRoot.left;
}
while(!s.empty()) {
localRoot=s.pop();
System.out.println(localRoot.data);
localRoot=localRoot.right;
}
}
}
//中序遍历(递归)
public void InOrder(Node localRoot) {
if(localRoot!=null) {
InOrder(localRoot.left);
System.out.print(localRoot.data+"");
InOrder(localRoot.right);
}
}
public void InOrder() {
this.InOrder(this.root);
}
//后序遍历(递归)
public void postOrder(Node localRoot) {
if(localRoot!=null) {
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data+"");
}
}
public void postOrder() {
this.postOrder(this.root);
}
//后序遍历(非递归)
public void postOrder_1(Node localRoot) {
Stack<Node> s=new Stack<Node>();
Stack<Integer> s1=new Stack<Integer>();
Integer i=new Integer(1);
while(localRoot!=null||!s.empty()) {
//将左子树压栈
while(localRoot!=null) {
s.push(localRoot);
s1.push(0);
localRoot=localRoot.left;
}
//检查s不为空并且s1顶端为1就输出
while(!s.empty()&&s1.peek().equals(i)) {
s.pop();
System.out.println(s);
}
//查看右子树
while(!s.empty()) {
s1.pop();
s1.push(1);
localRoot=s.peek();
localRoot=localRoot.right;
}
}
}
}