总结了二叉树的一些基本操作，包括
- 1）判断给定两个序列，一个作为前序，一个作为中序，是否可以构成一棵二叉树，测试用例：前序：{1,2,4,7,3,10,6,8}中序： {4,7,2,1,10,3,8,6} —-public BinaryTreeNode ConstructCore(int[] Preorder,int[] Inorder,int startPreorder,int endPreorder,int startInorder,int endInorder)；
- 2）树的前序递归遍历—public void printfBinaryTree(BinaryTreeNode node)；
- 3）树的非递归前序遍历—public void printfBinaryTreeNotRecurision(BinaryTreeNode node)；
- 4）树的中序递归遍历—printfBinaryTreeByInOrder(BinaryTreeNode node)；
- 5）树的非递归中序遍历—public void printfBinaryTreeInOrderNotRecurision(BinaryTreeNode node)；
- 6）树的后序递归遍历—public void printfBinaryTreeLastOrder(BinaryTreeNode node)；
- 7）树的非递归后序遍历—public void printfBinaryTreeLastOrderNotRecurision(BinaryTreeNode node)；
- 8）树的层次遍历—-public void printfBinaryFromTopToBottom(BinaryTreeNode node)
- 9）查找树的子结构—boolean HasSubTree(BinaryTreeNode treeA,BinaryTreeNode treeB)；
- 10）打印树的镜像—public void MirrorRecursively(BinaryTreeNode tree)
- 11）判断指定序列是否是一个二叉排序树的后序遍历—public boolean verfiySequenceOfBST(int[] sequence)；
- 12）查找二叉树的路径和与给定值相等的路径—FindPath(BinaryTreeNode pRoot,int expectedSum)；
package findKeyInArray;
import java.util.Arrays;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
class BinaryTreeNode{
int m_value;
BinaryTreeNode m_pLeft;
BinaryTreeNode m_pRight;
public BinaryTreeNode(int value){
m_value = value;
}
}
public class ConstructBinaryTree {
BinaryTreeNode root = null;
final int FILE_QUEUE_SIZE = 100;// 阻塞队列大小
//前序遍历打印树节点；采用递归算法
public void printfBinaryTree(BinaryTreeNode node){
System.out.print(node.m_value+" ");
if(node.m_pLeft != null){
printfBinaryTree(node.m_pLeft);
}
if(node.m_pRight != null){
printfBinaryTree(node.m_pRight);
}
}
//前序遍历采用非递归树
public void printfBinaryTreeNotRecurision(BinaryTreeNode node){
if(node==null) return;
//System.out.print(node.m_value+" ");
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();//建立一个栈
BinaryTreeNode p = node;
while(!s.isEmpty() || p!=null ){
if(p!=null){
System.out.print(p.m_value+" ");
s.push(p);
p = p.m_pLeft;
}else{
p = s.peek();
s.pop();
p = p.m_pRight;
}
}
}
//中序遍历打印树节点；
public void printfBinaryTreeByInOrder(BinaryTreeNode node){
if(node.m_pLeft != null){
printfBinaryTreeByInOrder(node.m_pLeft);
}
System.out.print(node.m_value+" ");
if(node.m_pRight != null){
printfBinaryTreeByInOrder(node.m_pRight);
}
}
//中序遍历采用非递归树
public void printfBinaryTreeInOrderNotRecurision(BinaryTreeNode node){
if(node==null) return;
//System.out.print(node.m_value+" ");
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();//建立一个栈
BinaryTreeNode p = node;
while(!s.isEmpty() || p!=null ){
if(p!=null){
s.push(p);
p = p.m_pLeft;
}else{
p = s.peek();
System.out.print(p.m_value+" ");
s.pop();
p = p.m_pRight;
}
}
}
//后序遍历，采用递归
public void printfBinaryTreeLastOrder(BinaryTreeNode node){
if(node==null) return;
if(node.m_pLeft!=null){
printfBinaryTreeLastOrder(node.m_pLeft);
}
if(node.m_pRight!=null){
printfBinaryTreeLastOrder(node.m_pRight);
}
System.out.print(node.m_value+" ");
}
//后序遍历采用非递归树
public void printfBinaryTreeLastOrderNotRecurision(BinaryTreeNode node){
if(node==null) return;
//System.out.print(node.m_value+" ");
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();//建立一个栈
BinaryTreeNode p = node;
BinaryTreeNode r=null;
while(!s.isEmpty() || p!=null ){
if(p!=null){
//System.out.print(p.m_value+" ");
s.push(p);
p = p.m_pLeft;
}else{
//当左子树为空的时候，查看当前节点有没有右子树
//左子树为空，并且右子树为空，则当前是叶子节点；
//如果左子树为空，右子树不为空，则当前节点是有右子树的根节点，此时应该打印当前节点的右子树节点。
p = s.peek();
if(p.m_pRight!=null && p.m_pRight!=r){
//如果p有右子树
p = p.m_pRight;
//System.out.println(p);
}else{
//当前节点就是叶子节点
System.out.print(p.m_value+" ");
s.pop();
r=p;
p = null;
}
}
}
}
//层次遍历树节点
public void printfBinaryFromTopToBottom(BinaryTreeNode node){
if(node==null){
return;
}
BlockingQueue<BinaryTreeNode> queue = new ArrayBlockingQueue<BinaryTreeNode>(FILE_QUEUE_SIZE);
queue.add(node);
while(queue.size()!=0){
BinaryTreeNode pNode = queue.peek();
queue.remove();
System.out.print(pNode.m_value+" ");
if(pNode.m_pLeft!=null){
queue.add(pNode.m_pLeft);
}
if(pNode.m_pRight!=null){
queue.add(pNode.m_pRight);
}
}
}
//递归构建树
public BinaryTreeNode ConstructCore(int[] Preorder,int[] Inorder,int startPreorder,int endPreorder,int startInorder,int endInorder){
int rootValue = Preorder[startPreorder];
BinaryTreeNode root = new BinaryTreeNode(rootValue);
root.m_pRight = root.m_pLeft = null;
if(startPreorder == endPreorder){
if(startInorder == endInorder) return root;
else {
System.out.println("无效的输入");
return null;
}
}
//在中序中找到根节点
int rootInorder = startInorder;
while(rootInorder <= endInorder && Inorder[rootInorder] != rootValue){
++rootInorder;
}
if(rootInorder == endInorder && Inorder[rootInorder] != rootValue){
System.out.println("无效的输入");
return null;
}
int leftLength = rootInorder-startInorder;
int leftPreorderEnd = startPreorder+leftLength;
if(leftLength>0){
//构建左子树
root.m_pLeft = ConstructCore(Preorder,Inorder,startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
}
if(leftLength<endPreorder-startPreorder){
root.m_pRight = ConstructCore(Preorder,Inorder,leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
}
return root;
}
//查找树的子结构
boolean HasSubTree(BinaryTreeNode treeA,BinaryTreeNode treeB){
boolean result = false;
if(treeA!=null &&treeB!=null){
if(treeA.m_value == treeB.m_value){
result = DoesTree1HaveTree2(treeA,treeB);
}
if(!result){
result = HasSubTree(treeA.m_pLeft,treeB);
}
if(!result){
result = HasSubTree(treeA.m_pRight,treeB);
}
}
return result;
}
//打印树的镜像
public void MirrorRecursively(BinaryTreeNode tree){
if(tree == null ) return;
if(tree.m_pLeft ==null|| tree.m_pRight ==null) return;
BinaryTreeNode temp = new BinaryTreeNode(0);
int tempNode = tree.m_pLeft.m_value;
tree.m_pLeft.m_value = tree.m_pRight.m_value;
tree.m_pRight.m_value = tempNode;
if(tree.m_pLeft!=null){
MirrorRecursively(tree.m_pLeft);
}
if(tree.m_pRight!=null){
MirrorRecursively(tree.m_pRight);
}
}
boolean DoesTree1HaveTree2(BinaryTreeNode treeA,BinaryTreeNode treeB){
if(treeB ==null){
return true;
}
if(treeA ==null){
return false;
}
if(treeA.m_value !=treeB.m_value){
return false;
}
return DoesTree1HaveTree2(treeA.m_pLeft,treeB.m_pLeft) &&DoesTree1HaveTree2(treeA.m_pRight,treeB.m_pRight);
}
//面试题24 二叉搜索树的后序遍历序列
public boolean verfiySequenceOfBST(int[] sequence){
if(sequence==null||sequence.length==0)
return false;
int length=sequence.length;
int root=sequence[length-1];
int cut=0;
for(int i=0;i<length-1;i++){
if(sequence[i]>root){
cut=i;
break;
}
}
if(cut==0){
verfiySequenceOfBST(Arrays.copyOfRange(sequence, 0,length-1));
}else{
for(int j=cut;j<length-1;j++){
if(sequence[j]<root)
return false;
}
}
boolean left=true;
if(cut>0)
left= verfiySequenceOfBST(Arrays.copyOfRange(sequence,0, cut));
boolean right=true;
if(cut<length-1)
right=verfiySequenceOfBST(Arrays.copyOfRange(sequence,cut,length-1));
return (right&&left);
}
//求二叉树中和为某一值的路径
void FindPath(BinaryTreeNode pRoot,int expectedSum){
if(pRoot==null) return;
Vector<Integer> path = new Vector<Integer>();
int currentSum = 0;
FindPath(pRoot,expectedSum,path,currentSum);
}
void FindPath(BinaryTreeNode pRoot,int expectedSum,Vector<Integer> path,int currentSum){
currentSum+=pRoot.m_value;
path.add(pRoot.m_value);
//若为叶结点，并且路劲上结点的和等于输入的值
//打印出这条路劲
boolean isLeft = pRoot.m_pLeft == null && pRoot.m_pRight == null;
if(currentSum == expectedSum && isLeft){
System.out.println("A Path is found：");
//Integer value = null;
int size = path.size();
for (int i=0; i<size; i++) {
System.out.print((Integer)path.get(i)+" ");
}
System.out.println();
}
//如果不是叶子节点，则遍历它的子节点
if(pRoot.m_pLeft!=null)
FindPath(pRoot.m_pLeft,expectedSum,path,currentSum);
if(pRoot.m_pRight!=null){
FindPath(pRoot.m_pRight,expectedSum,path,currentSum);
}
//在返回父结点之前，在路径上删除当前结点
path.remove(path.size()-1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ConstructBinaryTree binaryTree = new ConstructBinaryTree();
ConstructBinaryTree binaryTree2 = new ConstructBinaryTree();
//根据前序和中序构建树，注意：序列中不能有重复的数据，如果不能构成，则输出无效输入
int[] Preorder1={1,2,4,7,3,10,6,8};//给定树的前序
int[] Inorder1 = {4,7,2,1,10,3,8,6};//给定树的中序
int[] Preorder2={3,5,6,8};
int[] Inorder2 = {5,3,8,6};
binaryTree.root = binaryTree.ConstructCore(Preorder1,Inorder1,0,7,0,7);
binaryTree2.root = binaryTree.ConstructCore(Preorder2,Inorder2,0,3,0,3);
System.out.println("层次遍历");
binaryTree.printfBinaryFromTopToBottom(binaryTree.root);
System.out.println();
System.out.println("前序遍历");
binaryTree.printfBinaryTree(binaryTree.root);
System.out.println();
System.out.println("中序遍历");
binaryTree.printfBinaryTreeByInOrder(binaryTree.root);
System.out.println();
System.out.println("树的非递归前序遍历");
binaryTree.printfBinaryTreeNotRecurision(binaryTree.root);
System.out.println();
System.out.println("树的非递归中序遍历");
binaryTree.printfBinaryTreeInOrderNotRecurision(binaryTree.root);
System.out.println();
System.out.println("树的递归后序遍历");
binaryTree.printfBinaryTreeLastOrder(binaryTree.root);
System.out.println();
System.out.println("树的非递归后序遍历");
binaryTree.printfBinaryTreeLastOrderNotRecurision(binaryTree.root);
System.out.println();
System.out.println("----------------------------------");
System.out.println("判断二叉树是否有子结构");
binaryTree.printfBinaryTree(binaryTree2.root);
boolean result = false;
result=binaryTree.HasSubTree(binaryTree.root, binaryTree2.root);
System.out.println("result:"+result);
System.out.println("二叉树的镜像");
binaryTree2.MirrorRecursively(binaryTree2.root);
System.out.println("二叉树的镜像后的前序输出");
binaryTree2.printfBinaryTree(binaryTree2.root);
System.out.println();
System.out.println("判断指定序列是否是一个二叉排序树的后序遍历");
int[] array={5,7,6,9,11,10,8};
result = binaryTree.verfiySequenceOfBST(array);
System.out.println("result"+result);
System.out.println("查找二叉树的路径和与给定值相等的路径");
binaryTree.FindPath(binaryTree.root, 14);
}
}