二叉树上

写在前面：数据结构存在的意义是什么？ 读书百遍其义自见！

1. 二叉树结点类

package tree;/*** User: ZhangQi* Date: 2019/3/18* Time: 10:22* Desc: 二叉树结点类*/
public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}public int getVal() {return val;}
}

2. 根据前序遍历和中序遍历重建二叉树

package tree;import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;/*** User: ZhangQi* Date: 2019/3/18* Time: 10:22* Desc: 根据前序遍历和中序遍历重建二叉树*/
public class CreateBinaryTree {/*** @param pre {1,2,4,7,3,5,6,8}* @param in  {4,7,2,1,5,3,8,6}* @return*/public TreeNode reCreateBinaryTree(int[] pre, int[] in) {if (pre == null || in == null) return null;List preList = new ArrayList<>(pre.length);for (int i : pre) {preList.add(i);}List inList = new ArrayList<>(in.length);for (int i : in) {inList.add(i);}TreeNode treeNode = createBinaryTree(preList, inList);return treeNode;}private TreeNode createBinaryTree(List preList, List inList) {if (preList == null || preList.size() == 0) return null;int val = preList.get(0);TreeNode root = new TreeNode(val);int index = inList.indexOf(val);List leftInList = inList.subList(0, index);List rightInList = inList.subList(index + 1, inList.size());List leftPreList = preList.subList(1, index + 1);List rigthPreList = preList.subList(index + 1, preList.size());root.left = createBinaryTree(leftPreList, leftInList);root.right = createBinaryTree(rigthPreList, rightInList);return root;}public static void main(String[] args) {BigInteger d = null;long size = d==null ? 0 : d.longValue();System.out.println(size);CreateBinaryTree tree = new CreateBinaryTree();int[] pre = {5, 3, 2, 4, 7, 6, 8};int[] in = {2, 3, 4, 5, 6, 7, 8};TreeNode treeNode = tree.reCreateBinaryTree(pre, in);tree.prTree(treeNode);System.out.println();tree.inTree(treeNode);System.out.println();tree.listTree(treeNode);}/** 中序遍历 */private void inTree(TreeNode treeNode) {if (treeNode == null) return;inTree(treeNode.left);System.out.print(treeNode.getVal());System.out.print(" ");inTree(treeNode.right);}/** 前序遍历 */private void prTree(TreeNode treeNode) {if (treeNode == null) return;System.out.print(treeNode.getVal());System.out.print(" ");prTree(treeNode.left);prTree(treeNode.right);}/** 后序遍历 */private void listTree(TreeNode treeNode) {if (treeNode == null) return;listTree(treeNode.left);listTree(treeNode.right);System.out.print(treeNode.getVal());System.out.print(" ");}
}

3. 操作给定的二叉树，将其变换为源二叉树的镜像

package tree;/*** User: ZhangQi* Date: 2019/3/30* Time: 11:02* Desc: 操作给定的二叉树，将其变换为源二叉树的镜像*/
public class MirrorTree {public void Mirror(TreeNode root) {if(root == null) return;/** 临时结点 */TreeNode node = root.right;/** 左右孩子交换 */root.right = root.left;root.left = node;/** 递归左子树 */Mirror(root.left);/** 递归右子树 */Mirror(root.right);}
}

4. 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

package tree;/*** User: ZhangQi* Date: 2019/3/26* Time: 11:21* Desc: 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）*/
public class SonTree {public static boolean sonTree(TreeNode root1, TreeNode root2) {/** 任何一个为空，返回false */if (root1 == null || root2 == null) {return false;}/** 哨兵 */boolean result = false;/** 情景一：A, B 根结点相同 */if (root1.getVal() == root2.getVal()) {result = ensureSonTree(root1, root2);}/** 情景二：B是A的左子树子树 */if (!result) {result = sonTree(root1.left, root2);}/** 情景二：B是A的右子树子树 */if (!result) {result = sonTree(root1.right, root2);}return result;}public static boolean ensureSonTree(TreeNode t1, TreeNode t2) {/** t2为空说明 B 和 A 相同 */if (t2 == null) {return true;}/** t1为空, 说明B还有多余 */if (t1 == null) {return false;}/** 判断值是否相同 */if (t1.getVal() != t2.getVal()) {return false;}/** 递归左右遍历 */return ensureSonTree(t1.left,t2.left) && ensureSonTree(t1.right ,t2.right);}}

5. 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

package tree;/*** User: ZhangQi* Date: 2019/3/30* Time: 9:49* Desc: 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。* 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。*/
public class NextTreeNode {class TreeLinkNode {int val;TreeLinkNode left = null;TreeLinkNode right = null;TreeLinkNode next = null;TreeLinkNode(int val) {this.val = val;}}public TreeLinkNode getNext(TreeLinkNode node) {if(node == null) return null;/** 结点存在右子树 */if(node.right != null){node = node.right;while (node.left != null){node = node.left;}return node;}/** 结点不是根节点不存在右子树，且为左子树 */if (node.next != null && node.next.left == node) {return node.next;}/** 结点不是根节点不存在右子树，且为右子树 */if (node.next != null && node.next.right == node) {while (node.next.left != node) {node = node.next;}return node.next;}/** 结点是根节点 */return null;}
}

6. 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4

package tree;import java.util.ArrayList;/*** User: ZhangQi* Date: 2019/3/30* Time: 10:29* Desc: 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4*/
public class FindK {ArrayList list = new ArrayList<>();TreeNode KthNode(TreeNode pRoot, int k) {if (k < 1) return null;midQuery(pRoot);return list.size() < k ? null : list.get(k - 1);}void midQuery(TreeNode root) {if (root == null) return;midQuery(root.left);list.add(root);midQuery(root.right);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！