二叉树构造类:
public class BinaryTree { int data; // 根节点数据 BinaryTree left; // 左子树 BinaryTree right; // 右子树 public BinaryTree(int data) // 实例化二叉树类 { this.data = data; left = null; right = null; } public void insert(BinaryTree root, int data) { // 向二叉树中插入子节点 if (data > root.data) // 二叉树的左节点都比根节点小 { if (root.right == null) { root.right = new BinaryTree(data); } else { this.insert(root.right, data); } } else { // 二叉树的右节点都比根节点大 if (root.left == null) { root.left = new BinaryTree(data); } else { this.insert(root.left, data); } } } }
二叉树遍历、深度及求和:
public class BinaryTreePreorder { private static StringBuffer current = new StringBuffer(); private static int sum = 0; private static int needSum = 178; public static void preOrder(BinaryTree root) { //前序遍历(递归) if (root != null) { System.out.print(root.data + "-"); preOrder(root.left); preOrder(root.right); } } public static void inOrder(BinaryTree root) { // 中序遍历 if (root != null) { inOrder(root.left); System.out.print(root.data + "--"); inOrder(root.right); } } public static void postOrder(BinaryTree root) { // 后序遍历 if (root != null) { postOrder(root.left); postOrder(root.right); System.out.print(root.data + "---"); } } public static int getDepth(BinaryTree node) { //深度 if (node == null) { return 0; } int leftDepth = 0; int rightDepth = 0; leftDepth = getDepth(node.left); rightDepth = getDepth(node.right); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; } public static void visit(BinaryTree p) { System.out.print(p.data + " "); } protected static void iterativePreorder(BinaryTree p) { //前序遍历(非递归) Stack<BinaryTree> stack = new Stack<BinaryTree>(); if (p != null) { stack.push(p); while (!stack.empty()) { p = stack.pop(); visit(p); if (p.right != null) stack.push(p.right); if (p.left != null) stack.push(p.left); } } } private static void sum(BinaryTree node){ //计算二叉树节点总和数为N的集合,这里N = 178 int val = node.data; current.append(val+","); if(node.left==null && node.right==null){ //leaf here sum = 0; String[] nums = current.toString().split(","); for (int i=0;i<nums.length;i++) { sum += Integer.parseInt(nums[i]); } if (sum == needSum) { for (int i=0;i<nums.length;i++) { System.out.print(nums[i]+"-"); } } } else{ if(node.left!=null){ sum(node.left); current.setLength(current.length()-(node.left.data+"").length()-1); } if(node.right!=null){ sum(node.right); current.setLength(current.length()-(node.right.data+"").length()-1); } } } public static void main(String[] str) { int[] array = { 12, 76, 35, 22, 16, 48, 90, 46, 9, 40 }; BinaryTree root = new BinaryTree(array[0]); // 创建二叉树 for (int i = 1; i < array.length; i++) { root.insert(root, array[i]); // 向二叉树中插入数据 } System.out.println("(递归)前序遍历:"); preOrder(root); System.out.println(); System.out.println("(非递归)前序遍历:"); iterativePreorder(root); System.out.println(); System.out.println("中序遍历:"); inOrder(root); System.out.println(); System.out.println("后序遍历:"); postOrder(root); System.out.println(); System.out.println("深度:"); System.out.println( getDepth(root)); System.out.println("遍历求和,取总和为178的序列:"); sum(root); } }
二叉树图形:
相关推荐
包括了二叉树的各种递归与非递归的遍历算法 还可对二叉树所有结点求和
输入共3行:第一行为满二叉树中结点个数n(n<1024);第二行为n个整数,表示二叉树的先序遍历序列;第三行也有n个整数,表示二叉树的中序遍历序列。整数间以空格分割。
leetcode 338 个人博客: 坚持每天更新一至两篇。...二叉树中序遍历 Easy 二叉树是否相等 Easy 二叉树最大深度 Easy 二叉树层序遍历 Easy 二叉树是否平衡 Easy 二叉树的最小深度 Easy 二叉树路径和 Easy Pascal三角求和
目录目录经典算法Manacher算法原始问题进阶问题BFPRT算法morris遍历二叉树遍历规则先序、中序序列后序序列时间复杂度分析求和为aim的最长子数组长度
leetcode买卖股票问题力码 由 Java 实现的 LeetCode。...二叉树的最小深度 路径和 路径求和 II 将二叉树展平到链表 在每个节点中填充下一个右指针 II 二叉树最大路径和 根到叶数求和 按算法 动态规划
二叉树中序遍历 二叉树最大路径和 将排序数组转换为二叉搜索树 将排序列表转换为二叉搜索树 将二叉树展平到链表 二叉树的最大深度 二叉树的最小深度 路径和 排列 排列二 在每个节点中填充下一个右指针 Pow(x, n) 同...
第6章到第9章分别给出了4个领域的算法,如序列和集合的算法、图算法、几何算法、代数和数值算法;第10章涉及归约,也是第11章的序幕,而后者涉及NP完全问题;第12章则介绍了并行算法;最后是部分习题的答案及参考...
Algorithm_Note :bookmark_tabs:目录 :white_medium_star: Leetcode刷题笔记 已解决译文列表: ID 译文 语言 题解链接 1个 ...Java ...Java ...二叉树的层次遍历 Python 105 根据前序和中序重建二叉
二叉树有序遍历 验证二进制搜索树 恢复二进制搜索树 同一棵树 路径总和 路径总和II 买卖股票的最佳时间 买卖股票的最佳时间II 单号 链表周期 链表周期II 两个链表的交集 两个和II-输入数组已排序 反向链表 使用...
leetcode中国 leet-code-note LeetCode (中国) 笔记 ...二叉树的层次遍历 II 108. 将有序数组转换为二叉搜索树 110. 平衡二叉树 111. 二叉树的最小深度 112. 路径总和 118. 杨辉三角 1
对于字母中的每个符号,请执行以下操作使用二分查找算法从根目录遍历树,其中树的一半在每次迭代中均被忽略,并在每个步骤中连接权重。 编码符号流循环浏览符号流,并将每个符号映射到其对应的代码。 解码编码的符号...
144.二叉树的前序遍历 146.LRU缓存机制 155.最小栈 31.栈的压入、弹出序列 32.从上到下打印二叉树 有效的括号 面试题59 - I. 滑动窗口的最大值 71.简化路径 150.逆波兰表达式求值 环形链表 环形链表 II 删除中间节点...
实例111 二叉树的遍历 162 实例112 线索二叉树的创建 164 实例113 二叉排序树 166 实例114 哈夫曼编码 167 3.6 图及图的应用 169 实例115 图的邻接表存储 170 实例116 图的深度优先搜索 172 实例117 ...