据说面试中树考到的概率很高
package com.gengu.树; import java.util.Queue; import java.util.Stack; import java.util.concurrent.ConcurrentLinkedQueue; import org.junit.Test; /** * 这里测试树的相关算法 * 1:构造一个树 * 2:先序遍历 * 3:中序遍历 * 4:后序遍历 * 5:层次遍历 * 6:打印某一层二叉树的所有节点 * 7:求高度 * 8:求最远的节点 * 9:判断一个树是不是平衡二叉树 * */ class Node{ public int value; public Node left; public Node right; public Node(int value){ this.value = value; } } public class TestTree { public static Node root = new Node(9); public static Node value1 ; public static Node value2 ; /** * 创建一颗二叉树 * */ public static void createTree(){ Node node1 = new Node(8); Node node2 = new Node(7); Node node3 = new Node(6); Node node4 = new Node(5); Node node5 = new Node(4); Node node6 = new Node(3); Node node7 = new Node(2); Node node8 = new Node(1); Node node9 = new Node(0); Node node10 = new Node(11); Node node11 = new Node(12); value1 = node3; value2 = node9; root.left = node1; root.right = node2; node1.left = node3; node1.right = node4; node2.left = node5; node2.right = node6; node3.left = node7; node3.right = node8; node6.left = node10; node10.right = node11; node8.right = node9; } /** * 先序遍历 * */ public static void rootFirst(Node node){ System.out.println(node.value); if(node.left != null){ rootFirst(node.left); } if(node.right != null){ rootFirst(node.right); } } /** * 后序遍历 * */ public static void rootLast(Node node){ if(node.left != null){ rootLast(node.left); } if(node.right != null){ rootLast(node.right); } System.out.println(node.value); } /** * 中序 */ public static void rootMid(Node node){ if(node.left != null){ rootMid(node.left); } System.out.println(node.value); if(node.right != null){ rootMid(node.right); } } /** * 层次第n层的节点 * */ public static void layer(Node node,int n){ if(node == null){ return ; } if(1 == n){ System.out.println(node.value); } else { layer(node.left,n-1); layer(node.right, n-1); } } /** * 求出树的高度 * */ public static int getHeight(Node root){ if(null == root){ return 0; }else{ int lh = getHeight(root.left); int rh = getHeight(root.right); return lh>rh?lh+1:rh+1; } } /** * 层次序遍历 * */ public static void layer1(Node root){ Queue<Node> nodes = new ConcurrentLinkedQueue<Node>(); //加入第一个节点 nodes.add(root); while(true){ if(nodes.isEmpty()){ break; } Node node2 = nodes.poll(); if(node2.left!=null){ nodes.add(node2.left); } if(node2.right!=null){ nodes.add(node2.right); } System.out.println(node2.value); } } /** * 判断一颗树是不是平衡二叉树 * */ public static boolean isAVL(Node root){ if(root==null){ return true; }else { //求左树的高度 int left_depth = getHeight(root.left); //右子树的高度 int right_depth = getHeight(root.right); System.out.println(left_depth); System.out.println(right_depth); //如果从这个点可以看出它不平衡那么就返回false if(left_depth-right_depth>1||right_depth-left_depth>1){ return false; } //如果从这个节点往下看是平衡的不能就说它是平衡 //还要看它的左右子树 else { return isAVL(root.right)&&isAVL(root.right); } } } /** * 中序遍历的非递归算法 * 要注意的是所有节点都要入栈 * */ public static void inorder(Node root){ Stack<Node> stack1 = new Stack<Node>(); Node node = root; //stack1.push(root); //第一个节点的路径 while(node!=null||!stack1.isEmpty()){ if(node!=null){ stack1.push(node); node = node.left; }else { node = stack1.pop(); System.out.print(node.value); node = node.right; } } System.out.println(); } /** * 先序遍历 * 非递归算法 * */ public static void preorder(Node root){ Stack<Node> stack = new Stack<Node>(); Node node = root; stack.push(root); while(!stack.isEmpty()){ node = stack.pop(); System.out.print(node.value); if(node.right!=null){ stack.push(node.right); } if(node.left!=null){ stack.push(node.left); } } System.out.println(); } /** * 寻找最近公共父节点 * */ public static Node commanNode(Node root,Node value1,Node value2){ if(root == null){ return null; } else if(root==value1){ //这里表示的是如果在其它地方没有找到value2 //而找到了value1 那么表示value2在value1下面 //所以返回value1 return value1; } //同上 else if(root==value2){ return value2; } /** * 这里是一个分治的思想 * 从它的左右子树分别去找两个节点 * 如果找到那么当前节点就是最近父节点 * 想不通的可以画图 */ Node leftNode = commanNode(root.left, value1, value2); Node rightNode = commanNode(root.right, value1, value2); //如果在左右子树种分别找到就返回当前节点 if(leftNode!=null&&rightNode!=null){ return root; } /** * 如果只有在左边找到这个节点 那么返回 * 因为在右边没找到所以另外那个顶点一定是这个节点的子节点 * 画个图就能看懂 */ else if(leftNode!=null){ return leftNode; } /** * 如果只有在右边找到这个节点 那么返回 * 因为在左边没找到所以另外那个顶点一定是这个节点的子节点 * 画个图就能看懂 */ else if(rightNode!=null){ return rightNode; } else return null; } @Test public void test(){ createTree(); System.out.println(commanNode(root, value1, value2).value); } }
您还没有登录,请您登录后再发表评论
实验五二叉树的常见操作.docx实验五二叉树的常见操作.docx
实验五二叉树的常见操作.pdf实验五二叉树的常见操作.pdf
二叉搜索树(BST)是一种常见的二叉树结构,它具有有序性质,使得在插入、删除和搜索操作上非常高效。本教程将向您展示如何使用Java编写代码来执行二叉搜索树的插入操作。我们将提供一个简单而清晰的示例,以帮助您...
问题描述:采用二叉链表作为存储结构,完成图1的二叉树的建立和遍历操作。 基本要求: (1)基于先序遍历的构造算法。输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符...
java常用操作工具类封装,包括文件操作,xls,xlsx,pdf,txt文件的解析和生成,字符操作,集合操作,压缩包操作,...,内附api
Jquery-easyui-tree常见操作,加载树,获取所有选中节点,展开和折叠所有节点,展开和展开指定的节点等操作
vs2013上的MFC树控件操作2(编辑框显示实例),在一个树形控件中显示鸡啄米网站的简单结构分层,共有三层,分别为鸡啄米网站、各个分类和文章。用鼠标左键单击改变选中节点后,将选中节点的文本显示到编辑框中。另外...
1.文件列表区域,列出文件目录,及常见的操作。 2.提示框,用拖动DIV模拟的模态对话框。 3.目录树部分,外观同Windows资源管理器形似。 4.支持在线压缩解压,Ajax上传下载,新建、编辑文本文件,移动、复制、重命名...
主要介绍了javascript数据结构之多叉树经典操作,简单描述了多叉树的概念,并结合实例形式分析了javascript多叉树的创建、添加、遍历、移除等常见操作方法,需要的朋友可以参考下
1.(必做题) 常见排序算法的实现与性能比较 问题描述:实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法 实验要求: A. 在随机产生的空间大小分别为 N = 10, 1000,10000,100000 的...
将一个升序数组转化为平衡二叉搜索树是一种常见的算法问题。平衡二叉搜索树是一种特殊的二叉搜索树,它的左子树和右子树的高度差不超过1,以确保树的查找效率。 要将升序数组转化为平衡二叉搜索树,我们可以使用...
通过分析综采工作面主要产尘源、机械设备常见故障、粉尘防治技术措施以及人为操作失误等因素,演绎推理综采工作面采煤机司机可能患尘肺病等疾病的触发事件、间接原因和直接原因,确定了导致采煤机司机患尘肺病等疾病的...
插入操作:对于二叉搜索树(一种特殊的二叉树,其左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值),插入操作需要维护这一性质。当插入新节点时,需要将其与树中的现有节
为了减少电牵引采煤机辅助液压系统故障的发生,保证煤矿生产的持续高效进行和操作人员的劳动安全,将可能引发电牵引采煤机辅助液压系统故障的故障事件进行汇总,利用矿山安全工程中的故障树分析手段对其进行相应的故障...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
讲解数据结构的常见算法及其代码,以及整个程序原代码,适合广大初级以及入门朋友学习 参考!数据结构与算法基本程序目录 一、 线性表及其操作 1、 尾插法建立一个单链表,并按顺序输出 2、 单链表的元素查找,按...
在计算机科学中,树是一种很常见的数据结构,它是一种非线性的数据结构。我们可以按照等级模式将数据存储起来。在基本的数据结构中,如有序数组,无序数组,链表等,都有些不足,如:无序数组查找慢,有序数组虽然...
本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历),二叉搜索树的构造等。 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵...
由于分形图形的种类有很多种,但大多数是采用了递归的思想进行绘制,所以本文以较为常见和相对来讲难度不那么大的分形树进行讲解,感兴趣的读者可以尝试去制作更为复杂的分形图形。 详细介绍参考:...
相关推荐
实验五二叉树的常见操作.docx实验五二叉树的常见操作.docx
实验五二叉树的常见操作.pdf实验五二叉树的常见操作.pdf
二叉搜索树(BST)是一种常见的二叉树结构,它具有有序性质,使得在插入、删除和搜索操作上非常高效。本教程将向您展示如何使用Java编写代码来执行二叉搜索树的插入操作。我们将提供一个简单而清晰的示例,以帮助您...
问题描述:采用二叉链表作为存储结构,完成图1的二叉树的建立和遍历操作。 基本要求: (1)基于先序遍历的构造算法。输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符...
java常用操作工具类封装,包括文件操作,xls,xlsx,pdf,txt文件的解析和生成,字符操作,集合操作,压缩包操作,...,内附api
Jquery-easyui-tree常见操作,加载树,获取所有选中节点,展开和折叠所有节点,展开和展开指定的节点等操作
vs2013上的MFC树控件操作2(编辑框显示实例),在一个树形控件中显示鸡啄米网站的简单结构分层,共有三层,分别为鸡啄米网站、各个分类和文章。用鼠标左键单击改变选中节点后,将选中节点的文本显示到编辑框中。另外...
1.文件列表区域,列出文件目录,及常见的操作。 2.提示框,用拖动DIV模拟的模态对话框。 3.目录树部分,外观同Windows资源管理器形似。 4.支持在线压缩解压,Ajax上传下载,新建、编辑文本文件,移动、复制、重命名...
主要介绍了javascript数据结构之多叉树经典操作,简单描述了多叉树的概念,并结合实例形式分析了javascript多叉树的创建、添加、遍历、移除等常见操作方法,需要的朋友可以参考下
1.(必做题) 常见排序算法的实现与性能比较 问题描述:实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法 实验要求: A. 在随机产生的空间大小分别为 N = 10, 1000,10000,100000 的...
将一个升序数组转化为平衡二叉搜索树是一种常见的算法问题。平衡二叉搜索树是一种特殊的二叉搜索树,它的左子树和右子树的高度差不超过1,以确保树的查找效率。 要将升序数组转化为平衡二叉搜索树,我们可以使用...
通过分析综采工作面主要产尘源、机械设备常见故障、粉尘防治技术措施以及人为操作失误等因素,演绎推理综采工作面采煤机司机可能患尘肺病等疾病的触发事件、间接原因和直接原因,确定了导致采煤机司机患尘肺病等疾病的...
插入操作:对于二叉搜索树(一种特殊的二叉树,其左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值),插入操作需要维护这一性质。当插入新节点时,需要将其与树中的现有节
为了减少电牵引采煤机辅助液压系统故障的发生,保证煤矿生产的持续高效进行和操作人员的劳动安全,将可能引发电牵引采煤机辅助液压系统故障的故障事件进行汇总,利用矿山安全工程中的故障树分析手段对其进行相应的故障...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
讲解数据结构的常见算法及其代码,以及整个程序原代码,适合广大初级以及入门朋友学习 参考!数据结构与算法基本程序目录 一、 线性表及其操作 1、 尾插法建立一个单链表,并按顺序输出 2、 单链表的元素查找,按...
在计算机科学中,树是一种很常见的数据结构,它是一种非线性的数据结构。我们可以按照等级模式将数据存储起来。在基本的数据结构中,如有序数组,无序数组,链表等,都有些不足,如:无序数组查找慢,有序数组虽然...
本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历),二叉搜索树的构造等。 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵...
由于分形图形的种类有很多种,但大多数是采用了递归的思想进行绘制,所以本文以较为常见和相对来讲难度不那么大的分形树进行讲解,感兴趣的读者可以尝试去制作更为复杂的分形图形。 详细介绍参考:...