广州网站制作费用,美颂雅庭装饰公司电话,怎么注册公司名称,优秀企业宣传册样本1 树的序遍历
前序遍历、中序遍历、后序遍历
1.1 遍历方式
都有点抽象#xff0c;需要结合代码和画图来看
递归遍历非递归遍历#xff1a;都是用栈来解决 前序遍历 用一个栈#xff0c;先进右再进左 中序遍历 用一个栈#xff0c;先进左#xff0c;左出#xff0c;再…1 树的序遍历
前序遍历、中序遍历、后序遍历
1.1 遍历方式
都有点抽象需要结合代码和画图来看
递归遍历非递归遍历都是用栈来解决 前序遍历 用一个栈先进右再进左 中序遍历 用一个栈先进左左出再进右 后序遍历 用两个栈一个栈和前序遍历反着来出的元素进另一个栈进完之后全打印用一个栈先解决左边的再解决右边的。
1.2 代码实现
public class RecursiveTraversalBT {public static class Node {public int val;public Node left;public Node right;public Node(int val){this.val val;}}// 递归遍历public static void pre1(Node head) {if (head null) {return;}System.out.print(head.val );pre1(head.left);pre1(head.right);}public static void in1(Node head) {if (head null) {return;}in1(head.left);System.out.print(head.val );in1(head.right);}public static void pos1(Node head) {if (head null) {return;}pos1(head.left);pos1(head.right);System.out.print(head.val );}// 非递归遍历栈public static void pre2(Node head) {if (head ! null) {StackNode stack new Stack();stack.push(head);while (!stack.isEmpty()) {head stack.pop();System.out.print(head.val );if (head.right ! null) {stack.push(head.right);}if (head.left ! null) {stack.push(head.left);}}}}public static void in2(Node head) {if (head ! null) {StackNode stack new Stack();while (!stack.isEmpty() || head ! null) {if (head ! null) {stack.push(head);head head.left;}else {head stack.pop();System.out.print(head.val );head head.right;}}}}public static void pos2(Node head) {if (head ! null) {StackNode stack1 new Stack();StackNode stack2 new Stack();stack1.push(head);while (!stack1.isEmpty()){head stack1.pop();stack2.push(head);if (head .left ! null) {stack1.push(head.left);}if (head .right ! null) {stack1.push(head.right);}}while (!stack2.isEmpty()) {System.out.print(stack2.pop().val );}}}// 后序遍历的第三种写法只用一个栈public static void pos3(Node head) {if (head ! null) {StackNode stack new Stack();stack.push(head);Node help null;while (!stack.isEmpty()) {help stack.peek();if (help.left !null head ! help.left head ! help.right){stack.push(help.left);} else if (help.right ! null head ! help.right) {stack.push(help.right);}else {System.out.print(stack.pop().val );head help;}}}}public static void main(String[] args) {Node head new Node(1);head.left new Node(2);head.right new Node(3);head.left.left new Node(4);head.left.right new Node(5);head.right.left new Node(6);head.right.right new Node(7);pos2(head);System.out.println();pos3(head);System.out.println();}
}2 树的层遍历
2.1 遍历方式
树的最宽层有几个节点
借助Map来查找 定义一个队列和一个HashMap都把头节点放进去其中Map中存放的是当前节点和其对应的层数每次弹出一个节点就把这个节点的左右子节点都放进队列和对应的Map如果还没到下一层那么当前层的节点数就要加一如果到了下一层就把上一层的节点数和之前层的节点数比较返回节点数最多的层的节点数 只用队列 定义一个当前层的最左节点一个下一层的最左节点当弹出的节点等于当前层最左节点时记录当前层节点数并与之前层的最大节点数比较哪个大留哪个这个时候就要进入下一次所以当前层节点数置为0当前层最左节点置为下一层最左节点
4.2.2 代码实现
public class TreeMaxWidth {public static class Node {public int val;public Node left;public Node right;public Node(int val) {this.val val;left null;right null;}}public static int maxWidthUseMap(Node head) {if (head null) {return 0;}QueueNode queue new LinkedList();queue.add(head);HashMapNode, Integer hashMap new HashMap();hashMap.put(head, 1);int curLevelNodes 0;int curLevel 1;int max 0;while (!queue.isEmpty()) {Node cur queue.poll();int curNodeLevel hashMap.get(cur);if (cur.left ! null) {queue.add(cur.left);hashMap.put(cur.left, curNodeLevel 1);}if (cur.right ! null) {queue.add(cur.right);hashMap.put(cur.right, curNodeLevel 1);}if (curLevel curNodeLevel) {curLevelNodes;}else {max Math.max(max, curLevelNodes);curLevel;curLevelNodes 1;}}max Math.max(max, curLevelNodes);return max;}public static int maxWidthNoMap (Node head) {if (head null) {return 0;}QueueNode queue new LinkedList();queue.add(head);Node curEnd head;Node nextEnd null;int max 0;int curLevelNodes 0;while (!queue.isEmpty()) {Node cur queue.poll();if (cur.left ! null) {queue.add(cur.left);nextEnd cur.left;}if (cur.right ! null) {queue.add(cur.right);nextEnd cur.right;}curLevelNodes;if (cur curEnd) {max Math.max(max, curLevelNodes);curLevelNodes 0;curEnd nextEnd;}}return max;}public static void main(String[] args) {Node head new Node(1);head.left new Node(2);head.right new Node(3);head.left.left new Node(4);head.left.right new Node(5);head.right.left new Node(6);head.right.right new Node(7);head.left.right.left new Node(8);head.right.left.right new Node(9);System.out.println(maxWidthNoMap(head));}
}
