a5网站建设,植物网站设计方案,国外优秀ps网站,做网站市场报价步登顶文章目录递归方式 先序、中序、后序 遍历非递归方式 先序、中序、后序 遍历实现二叉树的按层遍历求二叉树的最大宽度二叉树的序列化和反序列化二叉树有 left、right、parent #xff0c;给这样二叉树的某个结点#xff0c;返回该节点的后继节点折纸条递归方式 先序、中序、后…
文章目录递归方式 先序、中序、后序 遍历非递归方式 先序、中序、后序 遍历实现二叉树的按层遍历求二叉树的最大宽度二叉树的序列化和反序列化二叉树有 left、right、parent 给这样二叉树的某个结点返回该节点的后继节点折纸条递归方式 先序、中序、后序 遍历
public class RecursiveTraversalBT {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value v;}}public static void f(Node head) {if (head null) {return;}// 1f(head.left);// 2f(head.right);// 3}// 先序打印所有节点public static void pre(Node head) {if (head null) {return;}System.out.println(head.value);pre(head.left);pre(head.right);}public static void in(Node head) {if (head null) {return;}in(head.left);System.out.println(head.value);in(head.right);}public static void pos(Node head) {if (head null) {return;}pos(head.left);pos(head.right);System.out.println(head.value);}}非递归方式 先序、中序、后序 遍历
使用栈
import java.util.Stack;public class UnRecursiveTraversalBT {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value v;}}//先序遍历public static void pre(Node head) {System.out.print(pre-order: );if (head ! null) {StackNode stack new StackNode();stack.add(head);while (!stack.isEmpty()) {head stack.pop();System.out.print(head.value );if (head.right ! null) {stack.push(head.right);}if (head.left ! null) {stack.push(head.left);}}}System.out.println();}//中序遍历public static void in(Node cur) {System.out.print(in-order: );if (cur ! null) {StackNode stack new StackNode();while (!stack.isEmpty() || cur ! null) {if (cur ! null) {stack.push(cur);cur cur.left;} else {cur stack.pop();System.out.print(cur.value );cur cur.right;}}}System.out.println();}//使用了两个栈实现后序遍历public static void pos1(Node head) {System.out.print(pos-order: );if (head ! null) {StackNode s1 new StackNode();StackNode s2 new StackNode();s1.push(head);while (!s1.isEmpty()) {head s1.pop(); // 头 右 左s2.push(head);if (head.left ! null) {s1.push(head.left);}if (head.right ! null) {s1.push(head.right);}}// 左 右 头while (!s2.isEmpty()) {System.out.print(s2.pop().value );}}System.out.println();}//使用一个栈实现后序遍历public static void pos2(Node h) {System.out.print(pos-order: );if (h ! null) {StackNode stack new StackNode();stack.push(h);Node c null;while (!stack.isEmpty()) {c stack.peek();if (c.left ! null h ! c.left h ! c.right) {stack.push(c.left);} else if (c.right ! null h ! c.right) {stack.push(c.right);} else {System.out.print(stack.pop().value );h c;}}}System.out.println();}}实现二叉树的按层遍历
1宽度优先遍历用队列
import java.util.LinkedList;
import java.util.Queue;public class LevelTraversalBT {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value v;}}public static void level(Node head) {if (head null) {return;}QueueNode queue new LinkedList();queue.add(head);while (!queue.isEmpty()) {Node cur queue.poll();System.out.println(cur.value);if (cur.left ! null) {queue.add(cur.left);}if (cur.right ! null) {queue.add(cur.right);}}}}2通过设置flag变量的方式来发现某一层的结束
参考 求二叉树的最大宽度 这个题
求二叉树的最大宽度
1使用map 2不使用map
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;public class TreeMaxWidth {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static int maxWidthUseMap(Node head) {if (head null) {return 0;}QueueNode queue new LinkedList();queue.add(head);// key 在 哪一层valueHashMapNode, Integer levelMap new HashMap();levelMap.put(head, 1);int curLevel 1; // 当前你正在统计哪一层的宽度int curLevelNodes 0; // 当前层curLevel层宽度目前是多少int max 0;while (!queue.isEmpty()) {Node cur queue.poll();int curNodeLevel levelMap.get(cur);if (cur.left ! null) {levelMap.put(cur.left, curNodeLevel 1);queue.add(cur.left);}if (cur.right ! null) {levelMap.put(cur.right, curNodeLevel 1);queue.add(cur.right);}if (curNodeLevel curLevel) {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;}
}二叉树的序列化和反序列化
1可以用 先序或者中序或者后序来实现二叉树的序列化
用了什么方式序列化就用什么方式反序列化
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class SerializeAndReconstructTree {/** 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化* 以下代码全部实现了。* 但是二叉树无法通过中序遍历的方式实现序列化和反序列化* 因为不同的两棵树可能得到同样的中序序列即便补了空位置也可能一样。* 比如如下两棵树* __2* /* 1* 和* 1__* \* 2* 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}* * */public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static QueueString preSerial(Node head) {QueueString ans new LinkedList();pres(head, ans);return ans;}public static void pres(Node head, QueueString ans) {if (head null) {ans.add(null);} else {ans.add(String.valueOf(head.value));pres(head.left, ans);pres(head.right, ans);}}public static QueueString inSerial(Node head) {QueueString ans new LinkedList();ins(head, ans);return ans;}public static void ins(Node head, QueueString ans) {if (head null) {ans.add(null);} else {ins(head.left, ans);ans.add(String.valueOf(head.value));ins(head.right, ans);}}public static QueueString posSerial(Node head) {QueueString ans new LinkedList();poss(head, ans);return ans;}public static void poss(Node head, QueueString ans) {if (head null) {ans.add(null);} else {poss(head.left, ans);poss(head.right, ans);ans.add(String.valueOf(head.value));}}public static Node buildByPreQueue(QueueString prelist) {if (prelist null || prelist.size() 0) {return null;}return preb(prelist);}public static Node preb(QueueString prelist) {String value prelist.poll();if (value null) {return null;}Node head new Node(Integer.valueOf(value));head.left preb(prelist);head.right preb(prelist);return head;}public static Node buildByPosQueue(QueueString poslist) {if (poslist null || poslist.size() 0) {return null;}// 左右中 - stack(中右左)StackString stack new Stack();while (!poslist.isEmpty()) {stack.push(poslist.poll());}return posb(stack);}public static Node posb(StackString posstack) {String value posstack.pop();if (value null) {return null;}Node head new Node(Integer.valueOf(value));head.right posb(posstack);head.left posb(posstack);return head;}
}2按层遍历
public class SerializeAndReconstructTree {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static QueueString levelSerial(Node head) {QueueString ans new LinkedList();if (head null) {ans.add(null);} else {ans.add(String.valueOf(head.value));QueueNode queue new LinkedListNode();queue.add(head);while (!queue.isEmpty()) {head queue.poll(); // head 父 子if (head.left ! null) {ans.add(String.valueOf(head.left.value));queue.add(head.left);} else {ans.add(null);}if (head.right ! null) {ans.add(String.valueOf(head.right.value));queue.add(head.right);} else {ans.add(null);}}}return ans;}public static Node buildByLevelQueue(QueueString levelList) {if (levelList null || levelList.size() 0) {return null;}Node head generateNode(levelList.poll());QueueNode queue new LinkedListNode();if (head ! null) {queue.add(head);}Node node null;while (!queue.isEmpty()) {node queue.poll();node.left generateNode(levelList.poll());node.right generateNode(levelList.poll());if (node.left ! null) {queue.add(node.left);}if (node.right ! null) {queue.add(node.right);}}return head;}public static Node generateNode(String val) {if (val null) {return null;}return new Node(Integer.valueOf(val));}
}二叉树有 left、right、parent 给这样二叉树的某个结点返回该节点的后继节点
public class SuccessorNode {public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value data;}}public static Node getSuccessorNode(Node node) {if (node null) {return node;}if (node.right ! null) {return getLeftMost(node.right);} else { // 无右子树Node parent node.parent;while (parent ! null parent.right node) { // 当前节点是其父亲节点右孩子node parent;parent node.parent;}return parent;}}public static Node getLeftMost(Node node) {if (node null) {return node;}while (node.left ! null) {node node.left;}return node;}
}折纸条 public class PaperFolding {public static void printAllFolds(int N) {process(1, N, true);System.out.println();}// 当前你来了一个节点脑海中想象的// 这个节点在第i层一共有N层N固定不变的// 这个节点如果是凹的话down T// 这个节点如果是凸的话down F// 函数的功能中序打印以你想象的节点为头的整棵树public static void process(int i, int N, boolean down) {if (i N) {return;}process(i 1, N, true);System.out.print(down ? 凹 : 凸 );process(i 1, N, false);}public static void main(String[] args) {int N 4;printAllFolds(N);}
}
