要构建二叉树及对二叉树进行操作首先得构建节点,节点包括节点的值还有它的左右孩子
public class BiTreeNode { public Object data; public BiTreeNode leftchild,rightchild; //空节点构造 public BiTreeNode(){ this(null); } //构造左右子节点为空的节点 public BiTreeNode(Object data){ this(data,null,null); } //构造有左右子节点的节点 public BiTreeNode(Object data,BiTreeNode leftchild,BiTreeNode rightchild){ this.data = data; this.leftchild = leftchild; this.rightchild = rightchild; }
对二叉树的操作有构建,遍历(递归,非递归,层次遍历)。栈的特点是先进先出,用栈能保留二叉树的访问路径,所以二叉树的非递归遍历应该用栈来操作,队列是先进后出,用来层次打印二叉树。
import java.util.Stack; import java.util.concurrent.LinkedBlockingQueue; public class BiTree { private BiTreeNode root; //树的根节点 public BiTree(){ //构造空树 this.root = null; } public BiTree(BiTreeNode root){ //构造树 this.root = root; } //根据先序中序建树 public BiTree(String preOrder, String inOrder ,int preIndex,int inIndex,int count){ if(count>0){ char data = preOrder.charAt(preIndex); int i = 0; for( ; i<count; i++){ if(data == inOrder.charAt(i+inIndex)) break; } root = new BiTreeNode(data); root.leftchild = new BiTree(preOrder,inOrder,preIndex +1,inIndex,i).root; root.rightchild = new BiTree(preOrder,inOrder,preIndex + i + 1,inIndex + i + 1,count - i - 1).root; } } //先序遍历递归 public void preRootTraverse(BiTreeNode T){ if(T != null){ System.out.print(T.data); preRootTraverse(T.leftchild); preRootTraverse(T.rightchild); } } //中序遍历递归 public void inRootTraverse(BiTreeNode T){ if(T != null){ inRootTraverse(T.leftchild); System.out.print(T.data); inRootTraverse(T.rightchild); } } //后序遍历递归 public void postRootTraverse(BiTreeNode T){ if(T != null){ postRootTraverse(T.leftchild); postRootTraverse(T.rightchild); System.out.print(T.data); } } //先序遍历非递归 public void preRootTraverse(){ BiTreeNode root = this.root; if(root != null){ Stack<BiTreeNode> stack = new Stack<BiTreeNode>(); stack.push(root); while(!stack.isEmpty()){ root = (BiTreeNode)stack.pop(); System.out.print(root.data); while(root != null){ if(root.leftchild != null){ System.out.print(root.leftchild.data); } if(root.rightchild != null){ stack.push(root.rightchild); } root = root.leftchild; } } } } //中序遍历非递归 public void inRootTraverse(){ BiTreeNode root = this.root; if(root != null){ Stack<BiTreeNode> stack = new Stack<BiTreeNode>(); stack.push(root); while(!stack.isEmpty()){ while(stack.peek() != null){ stack.push(stack.peek().leftchild); } stack.pop(); if(!stack.isEmpty()){ root = stack.pop(); System.out.print(root.data); stack.push(root.rightchild); } } } } //后序遍历非递归 public void postRootTraverse(){ BiTreeNode root = this.root; if(root != null){ Stack<BiTreeNode> stack = new Stack<BiTreeNode>(); stack.push(root); Boolean flag; BiTreeNode p = null; while(!stack.isEmpty()){ while(stack.peek() != null){ stack.push(stack.peek().leftchild); } stack.pop(); while(!stack.isEmpty()){ root = stack.peek(); if(root.rightchild == null || root.rightchild == p){ System.out.print(root.data); stack.pop(); p = root; flag = true; }else{ stack.push(root.rightchild); flag = false; } if(!flag){ break; } } } } } //层次遍历 public void LevelTraverse(){ BiTreeNode T = root; if(T != null){ LinkedBlockingQueue<BiTreeNode> queue = new LinkedBlockingQueue<BiTreeNode>(); queue.offer(T); while(!queue.isEmpty()){ T = queue.poll(); System.out.print(T.data); if(T.leftchild != null){ queue.offer(T.leftchild); } if(T.rightchild != null){ queue.offer(T.rightchild); } } } } }