import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
public static TreeNode creatBTfromArr(TreeNode node,int[] a,int pos){
if(a.length<1) return null;
if(pos<=a.length&&a[pos-1]>0){
node = new TreeNode(a[pos-1]);
node.left=creatBTfromArr(node.left, a, pos*2);
node.right=creatBTfromArr(node.right, a, pos*2+1);
return node;
}
else
return null;
}
public static void travPreOrder(TreeNode R){
if(R!=null){
System.out.print(R.val);
System.out.print(" ");
travPreOrder(R.left);
travPreOrder(R.right);
}
}
public static void travInOrder(TreeNode R){
if(R!=null){
travInOrder(R.left);
System.out.print(R.val);
System.out.print(" ");
travInOrder(R.right);
}
}
public static void travPostOrder(TreeNode R){
if(R!=null){
travPostOrder(R.left);
travPostOrder(R.right);
System.out.print(R.val);
System.out.print(" ");
}
}
public static void travLevelOrder(TreeNode R){
Queue<TreeNode> tmp = new LinkedList<>();
if(R!=null) tmp.add(R);
while(!tmp.isEmpty()){
TreeNode ttmp=tmp.remove();
System.out.print(ttmp.val);
System.out.print(" ");
if(ttmp.left!=null)
tmp.add(ttmp.left);
if(ttmp.right!=null)
tmp.add(ttmp.right);
}
}
public static class SNode{
public TreeNode R;
public int tag;
public SNode() {
// TODO Auto-generated constructor stub
}
public SNode(TreeNode R, int tag) {
this.R =R;
this.tag = tag;
}
}
public static void travPreOrder_noRec(TreeNode R){
Stack<SNode> stack = new Stack<>();
if(R!=null){
SNode tmp = new SNode(R,1);
stack.push(tmp);
System.out.print(R.val);
System.out.print(" ");
R=R.left;
}
while(!stack.isEmpty()){
while(R!=null){
stack.push(new SNode(R,1));
System.out.print(R.val);
System.out.print(" ");
R=R.left;
}
while(!stack.isEmpty()&&stack.peek().tag==2)
stack.pop();
if(!stack.isEmpty()&&stack.peek().tag==1){
R = stack.peek().R.right;
stack.peek().tag=2;
}
}
}
// 前序遍历-入栈即打印
public static void travPreOrder_noRec2(TreeNode R){
Stack<TreeNode> stack = new Stack<>();
while(!stack.isEmpty()||R!=null){
if(R!=null){
stack.push(R);
System.out.print(R.val + " ");
R=R.left;
}
else
R=stack.pop().right;
}
}
public static void travInOrder_noRec(TreeNode R){
if(R!=null){
Stack<SNode> stack = new Stack<>();
stack.push(new SNode(R,1));
R=R.left;
while(!stack.isEmpty()){
while(R!=null){
stack.push(new SNode(R,1));
R=R.left;
}
while(!stack.isEmpty()&&stack.peek().tag==2)
stack.pop();
if(!stack.isEmpty()&&stack.peek().tag==1){
System.out.print(stack.peek().R.val + " ");
R=stack.peek().R.right;
stack.peek().tag=2;
}
}
}
}
// 中序遍历-出栈即打印
public static void travInOrder_noRec2(TreeNode R){
if(R!=null){
Stack<TreeNode> stack = new Stack<>();
while (R!=null||!stack.isEmpty()) {
if(R!=null){
stack.push(R);
R=R.left;
}
else{
R=stack.peek().right;
System.out.print(stack.pop().val + " ");
}
}
}
}
public static void travPostOrder_noRec(TreeNode R){
if(R!=null){
Stack<SNode> stack = new Stack<>();
stack.push(new SNode(R,1));
R = R.left;
while(!stack.isEmpty()){
while (R!=null) {
stack.push(new SNode(R,1));
R=R.left;
}
while(!stack.isEmpty()&&stack.peek().tag==2){
System.out.print(stack.pop().R.val + " ");
}
if(!stack.isEmpty()&&stack.peek().tag==1){
R=stack.peek().R.right;
stack.peek().tag=2;
}
}
}
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null) return true;
if(p==null || q==null) return false;
if(q.val==q.val){
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
else
return false;
}
public static int treeDepth(TreeNode R){
if(R==null) return 0;
else{
return(Math.max(treeDepth(R.left), treeDepth(R.right))+1);
}
}
public static int nodeNum(TreeNode R){
if(R==null) return 0;
else{
return(nodeNum(R.left)+nodeNum(R.right)+1);
}
}
public static int leafnodeNum(TreeNode R){
if(R==null) return 0;
if(R.left==null && R.right==null) return 1;
return(leafnodeNum(R.left)+leafnodeNum(R.right));
}
public static List<Integer> inOrder094(TreeNode R){
List<Integer> res = new ArrayList<>();
if(R==null) return res;
else{
Stack<TreeNode> tmp = new Stack<>();
tmp.push(R);
R=R.left;
while(!tmp.isEmpty() || R!=null){
if(R!=null){
tmp.push(R);
R=R.left;
}
else{
R=tmp.peek().right;
res.add(tmp.pop().val);
}
}
return res;
}
}
public static int uniqueBSTnum(int n){
if(n<1) return 0;
else{
int[] res = new int[n+1];
res[0] = 1;
res[1] = 1;
for(int i=2;i<=n;i++){
for(int j=0;j<i;j++)
res[i]+=res[j]*res[i-1-j];
}
return res[n];
}
}
public static void main(String[] args){
int[] a={1,2,3,4,5,6,-1,-1,-1,7};
TreeNode node=null;
TreeNode R = creatBTfromArr(node, a, 1);
System.out.println("前序-递归:");
travPreOrder(R);
System.out.println("\n前序-非递归:");
travPreOrder_noRec(R);
System.out.println("\n前序-非递归2:");
travPreOrder_noRec2(R);
System.out.println("\n中序-递归:");
travInOrder(R);
System.out.println("\n中序-非递归:");
travInOrder_noRec(R);
System.out.println("\n中序-非递归2:");
travInOrder_noRec2(R);
System.out.println("\n后序-递归:");
travPostOrder(R);
System.out.println("\n后序-非递归:");
travPostOrder_noRec(R);
System.out.println("\n层序:");
travLevelOrder(R);
System.out.println("\n树深度:");
System.out.println(treeDepth(R));
System.out.println("树节点个数:");
System.out.println(nodeNum(R));
System.out.println("叶子节点个数:");
System.out.println(leafnodeNum(R));
List<Integer> res1 = inOrder094(R);
for(int i : res1){
System.out.println(i);
}
System.out.println("uniqueBSTnum:");
System.out.println(uniqueBSTnum(5));
}
}
网友评论