Inky资料

本文主要介绍Inky资料 方法和在新技术下所面对的“挑战”,方便大家深入理解Inky资料 过程。本文也将分享Inky资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

目录
  • 1 二叉树基本算法
    • 1.1 二叉树的遍历
      • 1.1.1 二叉树节点定义
      • 1.1.2 递归实现先序中序后序遍历
      • 1.1.3 非递归实现先序中序后序遍历
      • 1.1.4 二叉树按层遍历
    • 1.2 二叉树的序列化和反序列化
    • 1.3 直观打印一颗二叉树
    • 1.4 题目实战
      • 1.4.1 题目一:返回二叉树的后继节点
      • 1.4.2 题目二:折纸问题

1 二叉树基本算法

1.1 二叉树的遍历

1.1.1 二叉树节点定义

    Class Node{         // 节点的值类型         V value;         // 二叉树的左孩子指针         Node left;         // 二叉树的右孩子指针         Node right;     } 

1.1.2 递归实现先序中序后序遍历

先序:任何子树的处理顺序都是,先头结点,再左子树,再右子树。先处理头结点

中序:任何子树的处理顺序都是,先左子树,再头结点,再右子树。中间处理头结点

后序:任何子树的处理顺序都是,先左子树,再右子树,再头结点。最后处理头结点

对于下面的一棵树:

graph TD 1-->2 1-->3 2-->4 2-->5 3-->6 3-->7 

1、 先序遍历为:1 2 4 5 3 6 7

2、 中序遍历为:4 2 5 1 6 3 7

3、 后序遍历为:4 5 2 6 7 3 1

package class07;  public class Code01_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; 		} 		// 1 此处打印等于先序 		f(head.left); 		// 2 此处打印等于中序 		f(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); 	}  	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);  		pre(head); 		System.out.println("========"); 		in(head); 		System.out.println("========"); 		pos(head); 		System.out.println("========");  	}  } 

结论:对于树的递归,每个节点实质上会到达三次,例如上文的树结构,对于f函数,我们传入头结点,再调用左树再调用右树。实质上经过的路径为1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1。我们在每个节点三次返回的基础上,第一次到达该节点就打印,就是先序,第二次到达该节点打印就是中序,第三次到达该节点就是后序。

所以先序中序后序,只是我们的递归顺序加工出来的结果!

1.1.3 非递归实现先序中序后序遍历

思路:由于任何递归可以改为非递归,我们可以使用压栈来实现。用先序实现的步骤,其他类似:

步骤一,把节点压入栈中,弹出就打印

步骤二,如果有右孩子先压入右孩子

步骤三,如果有左孩子压入左孩子

package class07;  import java.util.Stack;  public class Code02_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) { 			Stack<Node> stack = new Stack<Node>(); 			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 head) { 		System.out.print("in-order: "); 		if (head != null) { 			Stack<Node> stack = new Stack<Node>(); 			while (!stack.isEmpty() || head != null) { 			        // 整条左边界依次入栈 				if (head != null) { 					stack.push(head); 					head = head.left; 				// 左边界到头弹出一个打印,来到该节点右节点,再把该节点的左树以此进栈 				} else { 					head = stack.pop(); 					System.out.print(head.value + " "); 					head = head.right; 				} 			} 		} 		System.out.println(); 	}          // 非递归后序 	public static void pos1(Node head) { 		System.out.print("pos-order: "); 		if (head != null) { 			Stack<Node> s1 = new Stack<Node>(); 			// 辅助栈 			Stack<Node> s2 = new Stack<Node>(); 			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(); 	}          // 非递归后序2:用一个栈实现后序遍历,比较有技巧 	public static void pos2(Node h) { 		System.out.print("pos-order: "); 		if (h != null) { 			Stack<Node> stack = new Stack<Node>(); 			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(); 	}  	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);  		pre(head); 		System.out.println("========"); 		in(head); 		System.out.println("========"); 		pos1(head); 		System.out.println("========"); 		pos2(head); 		System.out.println("========"); 	}  }  

1.1.4 二叉树按层遍历

1、 其实就是宽度优先遍历,用队列

2、 可以通过设置flag变量的方式,来发现某一层的结束

按层打印输出二叉树

package class07;  import java.util.LinkedList; import java.util.Queue;  public class Code03_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; 		} 		// 准备一个辅助队列 		Queue<Node> 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); 			} 		} 	}  	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);  		level(head); 		System.out.println("========"); 	}  }  

找到二叉树的最大宽度

package class07;  import java.util.HashMap; import java.util.LinkedList; import java.util.Queue;  public class Code06_TreeMaxWidth {  	public static class Node { 		public int value; 		public Node left; 		public Node right;  		public Node(int data) { 			this.value = data; 		} 	}          // 方法1使用map 	public static int maxWidthUseMap(Node head) { 		if (head == null) { 			return 0; 		} 		Queue<Node> queue = new LinkedList<>(); 		queue.add(head); 		// key(节点) 在 哪一层,value 		HashMap<Node, Integer> levelMap = new HashMap<>(); 		// head在第一层 		levelMap.put(head, 1); 		// 当前你正在统计哪一层的宽度 		int curLevel = 1;  		// 当前层curLevel层,宽度目前是多少 		int curLevelNodes = 0;  		// 用来保存所有层的最大值,也就是最大宽度 		int max = 0; 		while (!queue.isEmpty()) { 			Node cur = queue.poll(); 			int curNodeLevel = levelMap.get(cur); 			// 当前节点的左孩子不为空,队列加入左孩子,层数在之前层上加1 			if (cur.left != null) { 				levelMap.put(cur.left, curNodeLevel + 1); 				queue.add(cur.left); 			} 			// 当前节点的右孩子不为空,队列加入右孩子,层数也变为当前节点的层数加1 			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++; 				// 结算后,当前层节点数设置为1 				curLevelNodes = 1; 			} 		} 		// 由于最后一层,没有新的一层去结算,所以这里单独结算最后一层 		max = Math.max(max, curLevelNodes); 		return max; 	}          // 方法2不使用map 	public static int maxWidthNoMap(Node head) { 		if (head == null) { 			return 0; 		} 		Queue<Node> queue = new LinkedList<>(); 		queue.add(head); 		// 当前层,最右节点是谁,初始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进行比较,计算当前最大的max 				max = Math.max(max, curLevelNodes); 				// 即将进入下一层,重置下一层节点为0个节点 				curLevelNodes = 0; 				// 当前层的最右,直接更新为找出来的下一层最右 				curEnd = nextEnd; 			} 		} 		return max; 	}  	// for test 	public static Node generateRandomBST(int maxLevel, int maxValue) { 		return generate(1, maxLevel, maxValue); 	}  	// for test 	public static Node generate(int level, int maxLevel, int maxValue) { 		if (level > maxLevel || Math.random() < 0.5) { 			return null; 		} 		Node head = new Node((int) (Math.random() * maxValue)); 		head.left = generate(level + 1, maxLevel, maxValue); 		head.right = generate(level + 1, maxLevel, maxValue); 		return head; 	}  	public static void main(String[] args) { 		int maxLevel = 10; 		int maxValue = 100; 		int testTimes = 1000000; 		for (int i = 0; i < testTimes; i++) { 			Node head = generateRandomBST(maxLevel, maxValue); 			if (maxWidthUseMap(head) != maxWidthNoMap(head)) { 				System.out.println("Oops!"); 			} 		} 		System.out.println("finish!");  	}  } 

1.2 二叉树的序列化和反序列化

1、 可以用先序或者中序或者后序或者按层遍历,来实现二叉树的序列化

2、 用了什么方式的序列化,就用什么方式的反序列化

由于如果树上的节点值相同,那么序列化看不出来该树的结构,所以我们的序列化要加上空间结构的标识,空节点补全的方式。

package class07;  import java.util.LinkedList; import java.util.Queue; import java.util.Stack;  public class Code04_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 Queue<String> preSerial(Node head) { 		Queue<String> ans = new LinkedList<>(); 		// 先序的序列化结果依次放入队列中去 		pres(head, ans); 		return ans; 	}  	public static void pres(Node head, Queue<String> ans) { 		if (head == null) { 			ans.add(null); 		} else { 			ans.add(String.valueOf(head.value)); 			pres(head.left, ans); 			pres(head.right, ans); 		} 	}          // 中序有问题。见文件开头注释 	public static Queue<String> inSerial(Node head) { 		Queue<String> ans = new LinkedList<>(); 		ins(head, ans); 		return ans; 	}  	public static void ins(Node head, Queue<String> ans) { 		if (head == null) { 			ans.add(null); 		} else { 			ins(head.left, ans); 			ans.add(String.valueOf(head.value)); 			ins(head.right, ans); 		} 	}          // 后序序列化 	public static Queue<String> posSerial(Node head) { 		Queue<String> ans = new LinkedList<>(); 		poss(head, ans); 		return ans; 	}  	public static void poss(Node head, Queue<String> 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(Queue<String> prelist) { 		if (prelist == null || prelist.size() == 0) { 			return null; 		} 		return preb(prelist); 	}  	public static Node preb(Queue<String> 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(Queue<String> poslist) { 		if (poslist == null || poslist.size() == 0) { 			return null; 		} 		// 左右中  ->  stack(中右左) 		Stack<String> stack = new Stack<>(); 		while (!poslist.isEmpty()) { 			stack.push(poslist.poll()); 		} 		return posb(stack); 	}  	public static Node posb(Stack<String> 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; 	}          // 按层序列化,整体上就是宽度优先遍历 	public static Queue<String> levelSerial(Node head) { 	        // 序列化结果 		Queue<String> ans = new LinkedList<>(); 		if (head == null) { 			ans.add(null); 		} else { 		        // 加入一个节点的时候,把该节点的值加入 			ans.add(String.valueOf(head.value)); 			// 辅助队列 			Queue<Node> queue = new LinkedList<Node>(); 			queue.add(head); 			while (!queue.isEmpty()) { 				head = queue.poll(); 				// 左孩子不为空,即序列化,也加入队列 				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(Queue<String> levelList) { 		if (levelList == null || levelList.size() == 0) { 			return null; 		} 		Node head = generateNode(levelList.poll()); 		Queue<Node> queue = new LinkedList<Node>(); 		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)); 	}  	// for test 	public static Node generateRandomBST(int maxLevel, int maxValue) { 		return generate(1, maxLevel, maxValue); 	}  	// for test 	public static Node generate(int level, int maxLevel, int maxValue) { 		if (level > maxLevel || Math.random() < 0.5) { 			return null; 		} 		Node head = new Node((int) (Math.random() * maxValue)); 		head.left = generate(level + 1, maxLevel, maxValue); 		head.right = generate(level + 1, maxLevel, maxValue); 		return head; 	}  	// for test 	public static boolean isSameValueStructure(Node head1, Node head2) { 		if (head1 == null && head2 != null) { 			return false; 		} 		if (head1 != null && head2 == null) { 			return false; 		} 		if (head1 == null && head2 == null) { 			return true; 		} 		if (head1.value != head2.value) { 			return false; 		} 		return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right); 	}  	// for test 	public static void printTree(Node head) { 		System.out.println("Binary Tree:"); 		printInOrder(head, 0, "H", 17); 		System.out.println(); 	}  	public static void printInOrder(Node head, int height, String to, int len) { 		if (head == null) { 			return; 		} 		printInOrder(head.right, height + 1, "v", len); 		String val = to + head.value + to; 		int lenM = val.length(); 		int lenL = (len - lenM) / 2; 		int lenR = len - lenM - lenL; 		val = getSpace(lenL) + val + getSpace(lenR); 		System.out.println(getSpace(height * len) + val); 		printInOrder(head.left, height + 1, "^", len); 	}  	public static String getSpace(int num) { 		String space = " "; 		StringBuffer buf = new StringBuffer(""); 		for (int i = 0; i < num; i++) { 			buf.append(space); 		} 		return buf.toString(); 	}  	public static void main(String[] args) { 		int maxLevel = 5; 		int maxValue = 100; 		int testTimes = 1000000; 		System.out.println("test begin"); 		for (int i = 0; i < testTimes; i++) { 			Node head = generateRandomBST(maxLevel, maxValue); 			Queue<String> pre = preSerial(head); 			Queue<String> pos = posSerial(head); 			Queue<String> level = levelSerial(head); 			Node preBuild = buildByPreQueue(pre); 			Node posBuild = buildByPosQueue(pos); 			Node levelBuild = buildByLevelQueue(level); 			if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) { 				System.out.println("Oops!"); 			} 		} 		System.out.println("test finish!"); 		 	} } 

1.3 直观打印一颗二叉树

如何设计一个打印整颗数的打印函数,简单起见,我们躺着打印,正常的树我们顺时针旋转90°即可

package class07;  public class Code05_PrintBinaryTree {  	public static class Node { 		public int value; 		public Node left; 		public Node right;  		public Node(int data) { 			this.value = data; 		} 	}  	public static void printTree(Node head) { 		System.out.println("Binary Tree:"); 		// 打印函数,先传入头结点 		printInOrder(head, 0, "H", 17); 		System.out.println(); 	}          // head表示当前传入节点         // height当前节点所在的高度         // to表示当前节点的指向信息         // len表示打印当前值填充到多少位当成一个完整的值 	public static void printInOrder(Node head, int height, String to, int len) { 		if (head == null) { 			return; 		} 		// 递归右树,右树向下指 		printInOrder(head.right, height + 1, "v", len); 		/** 		* 打印自己的值 		* val 表示值内容 		**/ 		String val = to + head.value + to; 		int lenM = val.length(); 		// 按照len算该值左侧需要填充多少空格 		int lenL = (len - lenM) / 2; 		// 按照len算该值右侧需要填充多少空格 		int lenR = len - lenM - lenL; 		// 实际值加上左右占位,表示每个值包括占位之后大小 		val = getSpace(lenL) + val + getSpace(lenR); 		System.out.println(getSpace(height * len) + val); 		// 递归左树,左树向上指 		printInOrder(head.left, height + 1, "^", len); 	}          // 根据height*len补空格 	public static String getSpace(int num) { 		String space = " "; 		StringBuffer buf = new StringBuffer(""); 		for (int i = 0; i < num; i++) { 			buf.append(space); 		} 		return buf.toString(); 	}  	public static void main(String[] args) { 		Node head = new Node(1); 		head.left = new Node(-222222222); 		head.right = new Node(3); 		head.left.left = new Node(Integer.MIN_VALUE); 		head.right.left = new Node(55555555); 		head.right.right = new Node(66); 		head.left.left.right = new Node(777); 		printTree(head);  		head = new Node(1); 		head.left = new Node(2); 		head.right = new Node(3); 		head.left.left = new Node(4); 		head.right.left = new Node(5); 		head.right.right = new Node(6); 		head.left.left.right = new Node(7); 		printTree(head);  		head = new Node(1); 		head.left = new Node(1); 		head.right = new Node(1); 		head.left.left = new Node(1); 		head.right.left = new Node(1); 		head.right.right = new Node(1); 		head.left.left.right = new Node(1); 		printTree(head);  	}  }  

1.4 题目实战

1.4.1 题目一:返回二叉树的后继节点

题目描述:二叉树的结构定义如下:

Class Node {     V value;     Node left;     Node right;     // 指向父亲节点     Node parent; } 

给你二叉树中的某个节点,返回该节点的后继节点。后继节点表示一颗二叉树中,在中序遍历的序列中,一个个节点的下一个节点是谁。

方法一,通常解法思路:由于我们的节点有指向父节点的指针,而整颗二叉树的头结点的父节点为null。那么我们可以找到整棵树的头结点,然后中序遍历,再找到给定节点的下一个节点,就是该节点的后续节点。

方法二,考虑一个节点和其后继节点的结构之间的关系:

如果一个节点x有右树,那么其后继节点就是右树最左的节点。

如果x没有右树,往上找父亲节点。如果x是其父亲的右孩子继续往上找,如果某节点是其父亲节点的左孩子,那么该节点的父亲就是x的后继节点

即如果某节点左树的最右节点是x,那么该节点是x的后继

如果找父节点,一直找到null都不满足,那么该节点是整棵树的最右节点,没有后继

package class07;  public class Code07_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 static void main(String[] args) { 		Node head = new Node(6); 		head.parent = null; 		head.left = new Node(3); 		head.left.parent = head; 		head.left.left = new Node(1); 		head.left.left.parent = head.left; 		head.left.left.right = new Node(2); 		head.left.left.right.parent = head.left.left; 		head.left.right = new Node(4); 		head.left.right.parent = head.left; 		head.left.right.right = new Node(5); 		head.left.right.right.parent = head.left.right; 		head.right = new Node(9); 		head.right.parent = head; 		head.right.left = new Node(8); 		head.right.left.parent = head.right; 		head.right.left.left = new Node(7); 		head.right.left.left.parent = head.right.left; 		head.right.right = new Node(10); 		head.right.right.parent = head.right;  		Node test = head.left.left; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.left.left.right; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.left; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.left.right; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.left.right.right; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.right.left.left; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.right.left; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.right; 		System.out.println(test.value + " next: " + getSuccessorNode(test).value); 		test = head.right.right; // 10's next is null 		System.out.println(test.value + " next: " + getSuccessorNode(test)); 	}  } 

后继节点对应的是前驱结点,前驱结点的含义是中序遍历,某节点的前一个节点

1.4.2 题目二:折纸问题

请把一段纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开。

此时折痕是凹下去的,即折痕凸起的方向指向纸条的背面。

如果从纸条的下边向上方对折2次,压出折痕后展开,此时有三条折痕,从上到下依次是下折痕,下折痕和上折痕。

给定一个输入参数N,代表纸条都从下边向上方连续对折N次。请从上到下打印所有的折痕的方向。

例如:N=1时,打印: down 。N=2时,打印:down down up

规律,大于一次后,每次折痕出现的位置都是在上次折痕的上方出现凹折痕,下方出现凸折痕。所以我们没必要构建这颗树,就可以用递归思维解决

对应的树结构按层输出为:             1凹     2凹             2凸 3凹     3凸     3凹     3凸 
package class07;  public class Code08_PaperFolding {  	public static void printAllFolds(int N) { 	        // 先从头结点出发,i初始值为1,切第一次的头结点折痕为凹折痕 		printProcess(1, N, true); 	}  	// 递归过程,来到了某一个节点, 	// i是节点的层数,N一共的层数,down == true  凹    down == false 凸 	public static void printProcess(int i, int N, boolean down) { 		if (i > N) { 			return; 		} 		// 每个当前节点的左子节点是凹 		printProcess(i + 1, N, true); 		System.out.println(down ? "凹 " : "凸 "); 		// 每个当前节点的右子树是凸 		printProcess(i + 1, N, false); 	}  	public static void main(String[] args) { 		int N = 3; 		// 折N次,打印所有凹凸分布情况 		printAllFolds(N); 	} } 

Inky资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » Inky资料

提供最优质的资源集合

立即查看 了解详情