二叉树结构：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int key){
val=key;
left=null;
right=null;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
import java.util.Stack;
public class InsertBtree {
//插入(二叉排序树)
public static void insert(TreeNode T,int key){
if(T.getVal()>key){
if(T.getLeft()==null){
T.setLeft(new TreeNode(key));
}else{
insert(T.getLeft(),key);
}
}else if(T.getVal()<key){
if(T.getRight()==null){
T.setRight(new TreeNode(key));
}else{
insert(T.getRight(),key);
}
}
}
//删除
public static void delete(TreeNode T,int key){
TreeNode p=T;
TreeNode f=null;
TreeNode q=null;
while(p!=null){
if(p.getVal()==key){
break;
}
f=p;
if(p.getVal()>key)
p=p.getLeft();
else p=p.getRight();
}
if(p==null)return;
//左右子树同时存在
if(p.getRight()!=null&&p.getLeft()!=null){
q=p;
TreeNode s=p.getLeft();
while(s.getRight()!=null){
q=s;
s=s.getRight();
}
p.setVal(s.getVal());
if(q==p){
q.setLeft(s.getLeft());
}else{
q.setRight(s.getLeft());
}
}
//只有左子树存在
else if(p.getLeft()!=null){
q=p;
p=p.getLeft();
}
//只有右子数存在
else if(p.getRight()!=null){
q=p;
p=p.getRight();
}
//左右子数都不存在
else
p=null;
if(f==null)T=p;
else if(q.getVal()<f.getVal())
{
f.setLeft(p);
}
else{
f.setRight(p);
}
}
//前序遍历
public static void preorder(TreeNode T){
TreeNode p=T;
TreeNode q=null;
Stack stack=new Stack();
System.out.println("**********前序遍历************");
while(p!=null||!stack.empty()){
if(p!=null){
stack.push(p);
System.out.print(p.getVal()+" ");
p=p.getLeft();
}else{
q=(TreeNode) stack.peek();
stack.pop();
p=q.getRight();
}
}
System.out.println();
}
//中序遍历
public static void Inorder(TreeNode T){
TreeNode p=T;
TreeNode q=null;
Stack stack=new Stack();
System.out.println("*********中序遍历***************");
while(p!=null||!stack.empty()){
if(p!=null){
stack.push(p);
p=p.getLeft();
}else{
q=(TreeNode) stack.peek();
stack.pop();
System.out.print(q.getVal()+" ");
p=q.getRight();
}
}
System.out.println();
}
//后序遍历
public static void postorder(TreeNode T){
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=T;
TreeNode pre=null;
System.out.println("**********后序遍历*********");
while(p!=null||!stack.empty()){
while(p!=null){
stack.push(p);
p=p.getLeft();
}
p=stack.peek();
if(p.getRight()==null||p.getRight()==pre){
System.out.print(p.getVal()+" ");
pre=p;
stack.pop();
p=null;
}else{
p=p.getRight();
}
}
System.out.println();
}
public static void main(String[] args) {
int[] a={8,23,12,3,6,9,7,3,2,5,14,56};
TreeNode T=new TreeNode(a[0]);
for(int i=1;i<a.length;i++){
insert(T,a[i]);
}
Inorder(T);
preorder(T);
postorder(T);
}
}
最后结果：
*********中序遍历***************
2 3 5 6 7 8 9 12 14 23 56
**********前序遍历************
8 3 2 6 5 7 23 12 9 14 56
**********后序遍历*********
2 5 7 6 3 9 14 12 56 23 8