import java.util.ArrayDeque; public class Tree{ //定义一个根节点 Node root; //创建结点 public static class Node{ //数值 Object item; //左右子结点 Node left; Node right; //判断当前左右指针是否线索化 boolean isLeftLine=false; boolean isRightLine=false; public Node(Object item){ this.item=item; } } //创建一棵树 public void CreateTree() { //创建根节点 root=new Node(1); //第二层 //创建左子结点 Node Left=new Node(2); //创建右子结点 Node Right=new Node(3); //进行关联 root.left=Left; root.right=Right; //第三层 Node Left2=new Node(4); //创建右子结点 Node Right2=new Node(5); //进行关联 root.left.left=Left2; root.left.right=Right2; //第三层 Node Left3=new Node(6); //创建右子结点 Node Right3=new Node(7); //进行关联 root.right.left=Left3; root.right.right=Right3; } //前序遍历 public void ShowTree(Node node){ if(node==null){ return; } //遍历根节点 System.out.print(node.item+" "); //遍历左子树 ShowTree(node.left); //遍历右子树 ShowTree(node.right); } //中序 public void MidShowTree(Node node){ if(node==null){ return; } //遍历左子树 MidShowTree(node.left); //遍历根节点 System.out.print(node.item+" "); //遍历右子树 MidShowTree(node.right); } //后序遍历 public void FinShowTree(Node node){ if(node==null){ return; } //遍历左子树 FinShowTree(node.left); //遍历右子树 FinShowTree(node.right); //遍历根节点 System.out.print(node.item+" "); } //层次遍历: public void LeveTree(Node node){ //创建队列; ArrayDeque <Node> ad=new ArrayDeque<>(10); if(node==null){ System.out.println("树里面已经没有结点了"); return; } //加入根节点 ad.add(node); while (!ad.isEmpty()) { Node n=ad.poll(); System.out.print(n.item+" "); //左子树放到队列 if(n.left!=null){ ad.add(n.left); } //将右子树放到队列中去 if(n.right!=null){ ad.add(n.right); } } } //查找元素: public Node Select(Node node,Object t){ Node target=null; if(node==null){ return null; }else{ if(node.item==t){ return node; }else{ //从左子树进行遍历 target=Select(node.left,t); //判断是否找到了结果 if(target!=null){ return target; } //从右子树进行遍历 target=Select(node.right,t); //判断是否找到了结果 if(target!=null){ return target; } return null; } } } //删除元素: public void Delete(Node node,Object t){ if(node==null){ return; } //判断根节点 if(node==root&&root.item==t){ this.root=null; } //判断子结点是否为null if(node.left!=null){ if(node.left.item==t){ //删除左子结点 node.left=null; return; }else{ Delete(node.left,t); } } //判断右子结点 if(node.right!=null){ if(node.right.item==t){ //删除右子结点 node.right=null; return; }else{ Delete(node.right,t); } } } //二叉树的深度 public int MaxDelth(Node node){ if(node==null){ return 0; } int leftDeth=0; int rightDeth=0; //获取左子树的高度 if(node.left!=null){ leftDeth=MaxDelth(node.left); } //获取右子树的高度 if(node.right!=null){ rightDeth=MaxDelth(node.right); } //判断最大层次关系 if(leftDeth>rightDeth){ return leftDeth+1; } else{ return rightDeth+1; } } }
2.二叉树的遍历规则：
前序遍历: 根结点-左子树-右子树；
中序遍历:左子树-根结点-右子树;
后序遍历:左子树-右子树-根节点；
前序遍历:
前序遍历的遍历顺序是根左右。 我们首先从根节点U出发，由于它是根节点因此U排在首位，得到顺序U。 然后去找U的左节点，发现U没有左节点，于是去找U的右分支，得到顺序UI。 发现I有左节点I，得到顺序UII。 发现I有左节点N，得到顺序UIIN。 发现I有右节点S，得到顺序UIINS。 发现S有左节点R，得到顺序UIINSR。 发现R有左节点V，得到顺序UIINSRV。 发现R有右节点E，得到顺序UIINSRVE。 发现I有右节点T，得到顺序UIINSRVET。 发现I有右节点Y，得到顺序UIINSRVETY。 前序遍历从根节点出发，然后去找他的左节点，再找右节点，深度优先。
（三）、数组实现二叉树
n是下标不是数字哈
1.必须是完全二叉树.
2.左子节点是2n+1;
3.右子节点是2n+2;
4.父类子结点是(n-1)/2;
5.n代表从第几个(n初始化为0)；
1.数组二叉树数组的遍历
public class array { int []elem; public array(int []s){ this.elem=s; } //实现先序遍历 public void preT(int idex){ if(idex>=elem.length){ return; } //遍历当前结点 System.out.print(elem[idex]+" "); //遍历左节点 preT(2*idex+1); //遍历右节点 preT(2*idex+2); } //遍历中序 public void midT(int idex){ if(idex>=elem.length){ return; } //遍历左节点 midT(2*idex+1); //遍历当前结点 System.out.print(elem[idex]+" "); //遍历右节点 midT(2*idex+2); } //遍历后序 public void laterT(int idex){ if(idex>=elem.length){ return; } //遍历左节点 laterT(2*idex+1); //遍历右节点 laterT(2*idex+2); //遍历当前结点 System.out.print(elem[idex]+" "); } }
import java.awt.event.KeyEvent; import java.awt.event.KeyListener; import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs){ array s1=new array(new int[]{1,2,3,4,5,6,7}); s1.preT(0); System.out.println("==========="); s1.midT(0); System.out.println("==========="); s1.laterT(0); } }
2.大堆顶的实现及其排序
import org.jetbrains.annotations.NotNull; import java.awt.event.KeyEvent; import java.awt.event.KeyListener; import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs){ int []arr=new int[]{9,19,3,2,18,7,8,25,29,4,20}; //构造二叉树的guize //左结点 2*n+1; //右节点 2*n+2; //最后一个非叶子结点 :(arr.length-1)/2 //展现大顶堆 for (int i = (arr.length-1)/2; i >=0; i--) { Dui(arr,i); } for (int i = 0; i <arr.length; i++) { System.out.print(arr[i]+" "); } //实现大顶堆的排序 错错错 // for (int i = (arr.length-1)/2; i >=0; i--) { // PaiDui(arr,i,arr.length); // } // //从数组的最后元素开始排序遍历 // // for (int last=arr.length-1; last >=0 ; last--) { // int temp=arr[0]; // arr[0]=arr[last]; // arr[last]=temp; // //调用大堆顶排序的方法 // PaiDui(arr,0,last); // } // for (int i = 0; i <arr.length; i++) { // System.out.print(arr[i]+" "); // } } //构造大顶堆 public static void Dui(int @NotNull []arr, int idex){ //计算左子树的位置 int left=2*idex+1; //计算右子树的位置 int right=2*idex+2; //假如说子结点超过数组的位置，那么就退出 if(left>arr.length||right>arr.length){ return; } //比较大小 int max=idex; if(arr[left]>arr[max]){ max=left; } if(arr[right]>arr[max]){ max=right; } if(max!=idex){ int temp; temp=arr[idex]; arr[idex]=arr[max]; arr[max]=temp; //还要向下进行比较 Dui(arr,max); } } //构造大顶堆且进行排序 public static void PaiDui(int []arr,int idex,int size){ //计算左子树的位置 int left=2*idex+1; //计算右子树的位置 int right=2*idex+2; //假如说子结点超过数组的位置，那么就退出 if(left>size||right>size){ return; } //比较大小 int max=idex; if(arr[left]>arr[max]){ max=left; } if(arr[right]>arr[max]){ max=right; } if(max!=idex){ int temp; temp=arr[idex]; arr[idex]=arr[max]; arr[max]=temp; //还要向下进行比较 PaiDui(arr,max,size); } } }
