q:计算下二叉树的节点:
a:可以用递归,
q:递归堆栈利用高,时间复杂度高,不要用递归
a:emmmmmm… 请看下文
package com.gjw.datastruts_Alg.binarytree; import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor; @Data @NoArgsConstructor @AllArgsConstructor public class BiTree { private BiTree lChild, rChild; private int data; public BiTree(int data) { this.data = data; } //先序遍历 public static void PreOrder(BiTree tree) { BiTree[] stack = new BiTree[MAX]; int top = -1; stack[++top] = tree; while (top != -1) { BiTree p = stack[top--]; while (p != null) { print(p); if (p.rChild != null) { stack[++top] = p.rChild; } p = p.lChild; } } } //中序遍历 public static void InOrder(BiTree tree) { BiTree[] stack = new BiTree[MAX]; int top = -1; BiTree p = tree; while (p != null || top != -1) { if (p != null) { stack[++top] = p; p = p.lChild; } else { p = stack[top--]; print(p); p = p.rChild; } } } static class SNode { int flag = 0; //用来记录该节点是否输出 0表示未输出 1表示已经输出 BiTree p; public SNode(BiTree p) { this.p = p; } } //后序遍历 public static void PostOrder(BiTree tree) { SNode[] stack = new SNode[MAX]; int top = -1; BiTree p = tree; while (p != null || top != -1) { while (p != null) { SNode node = new SNode(p); stack[++top] = node; p = p.lChild; } SNode node = stack[top--]; if (node.flag == 0) { node.flag = 1; stack[++top] = node; p = node.p.rChild; } else { print(node.p); } } } //层级遍历 public static void LevelOrder(BiTree tree) { BiTree[] queue = new BiTree[MAX]; int front = 0, rear = 0; queue[rear++] = tree; while (front < rear) { BiTree p = queue[front++]; print(p); if (p.lChild != null) queue[rear++] = p.lChild; if (p.rChild != null) queue[rear++] = p.rChild; } } //统计叶子节点(递归) public static int leafCount(BiTree tree) { int count = 0; if (tree == null) { return count; } else if (tree.lChild == null && tree.rChild == null) { count = 1; } else { count = leafCount(tree.lChild) + leafCount(tree.rChild); } return count; } //统计非叶子节点(递归) public static int noLeafCount(BiTree tree) { int count = 0; if (tree == null) { return count; } else if (tree.lChild != null || tree.rChild != null) { count = 1; if (tree.lChild != null) count += noLeafCount(tree.lChild); if (tree.rChild != null) count += noLeafCount(tree.rChild); } return count; } //统计各种节点(非递归) public static int LeafCount(BiTree tree) { if (tree == null) return 0; int count = 0; int top = -1; BiTree[] stack = new BiTree[MAX]; stack[++top] = tree; while (top != -1) { BiTree p = stack[top--]; //if(p.lChild!=null || p.rChild!=null)//统计非叶子节点 //if(p.lChild!=null && p.rChild!=null)//统计有两个孩子的节点 //if ((p.lChild != null && p.rChild == null) || (p.lChild == null && p.rChild != null)) //统计只有一个孩子的节点 if (p.lChild == null && p.rChild == null)//统计叶子节点 count++; if (p.lChild != null) stack[++top] = p.lChild; if (p.rChild != null) stack[++top] = p.rChild; } return count; } //统计二叉树的高度 public static int TreeHigh(BiTree tree) { int leftHigh, rightHigh, maxHigh; if (tree == null) { return 0; } else { leftHigh = TreeHigh(tree.lChild); rightHigh = TreeHigh(tree.rChild); maxHigh = leftHigh > rightHigh ? leftHigh : rightHigh; return maxHigh + 1; } } public static int treeHigh(BiTree tree) { BiTree[] queue = new BiTree[MAX]; int front = 0, rear = 0; queue[rear++] = tree; int level = 1, high = 0; while (front < rear) { BiTree p = queue[front++]; if (p.lChild != null) queue[rear++] = p.lChild; if (p.rChild != null) queue[rear++] = p.rChild; if (front == level) { high++; level = rear; } } return high; } private static int MAX = 10; public static void main(String[] args) { BiTree biTree = init(); PreOrder(biTree); System.out.println(); InOrder(biTree); System.out.println(); PostOrder(biTree); System.out.println(); LevelOrder(biTree); System.out.println(); System.out.println("叶子节点个数: " + leafCount(biTree)); System.out.println("非叶子节点个数: " + noLeafCount(biTree)); System.out.println("叶子节点个数: " + LeafCount(biTree)); System.out.println("递归树的高度: " + TreeHigh(biTree)); System.out.println("非递归树的高度: " + treeHigh(biTree)); } private static void print(BiTree p) { System.out.print(p.data + " "); } private static BiTree init() { BiTree biTree = new BiTree(); biTree.setData(1); BiTree two = new BiTree(2); BiTree three = new BiTree(3); BiTree four = new BiTree(4); BiTree five = new BiTree(5); BiTree six = new BiTree(6); BiTree seven = new BiTree(7); biTree.setLChild(two); biTree.setRChild(three); two.setLChild(four); two.setRChild(five); three.setLChild(six); three.setRChild(seven); return biTree; } }