数据结构

数据结构

树:

1.二叉树概念

如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1 , n为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

image-20201024112114759

2.前中序查找

//中序查找
public Node infixSearch(int no){
System.out.println(“当前位置为”+this.value);
Node result=null;
if(this.left!=null){
result =this.left.infixSearch(no);
}
if(result!=null){
return result;
}
if(this.value==no){
return this;
}
if(this.right!=null){
result=this.right.infixSearch(no);
}
return result;
}
//前序查找
public Node preSearch(int no){
System.out.println(“当前所在结点”+this.value);
if(this.value==no){
return this;
}
Node result=null;
if(this.left!=null){
result = this.left.preSearch(no);
}
if(result!=null){
return result;
}
if(this.right!=null){
result = this.right.preSearch(no);
}
return result;
}

3.结点的删除

//递归删除结点
//1.如果删除结点是叶子结点则删除该结点
//2.如果删除结点是非叶子结点，则删除该子树
//3.因为是单向的所以只能判断当前结点的子结点是否符合，而不能判断此结点是否符合
//4.自己思考 删除结点而不删除树，让其左子结点代替本身 右字几点顺序添加到左子节点的右子树
public void delNode(int no){

if(this.value>no){<br />        if(this.left!=null && this.left.value==no){<br />            this.left=null;<br />            return;<br />        }<br />        if (this.left!=null){<br />            this.left.delNode(no);<br />        }<br />    }else {<br />        if(this.right!=null && this.right.value==no){<br />            this.right=null;<br />            return;<br />        }<br />        if (this.right!=null){<br />            this.right.delNode(no);<br />        }<br />    }

}

4.顺序存储二叉树

基本说明：
从数据存储来看，数组存储方法和树的存储方法可以互相转换，即数组可以转换成树，树也可以转换成数组。
要求:
在遍历数组arr时，仍然可以以二叉树的前序，中序，后序遍历。

public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int arr[]= {1,2,3,4,5,6,7};
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);

    arrBinaryTree.preOrder(0);<br />    }<br />}<br />class ArrBinaryTree{<br />    private int[] arr;  //存储数据结点的数组
public ArrBinaryTree(int[] arr){<br />        this.arr=arr;<br />    }
public void preOrder(int index){<br />        //如果数组为空，或者arr.length= 0<br />        if(arr==null||arr.length==0){<br />            System.out.println("数组为空，不能按照二叉树的前序遍历");<br />        }<br />        //输出当前元素<br />        if(index>=arr.length){<br />            return;<br />        }<br />        System.out.println(arr[index]);<br />        preOrder(index*2+1);<br />        preOrder(index*2+2);<br />    }<br />}

5.线索二叉树

二叉树中结点个数2，1，0 n2，n1，n0
n0=n2+1
n1=1 n2 = (n-2)/2 空指针域：n=2n-(n-2)/2-1=n+1
n1=0 n2 = (n-1)/2 空指针域：n=2n-(n-1)/2 =n+1
除去根结点 每个结点都会被指针引用 一个n-1个结点 所以剩下2n-n+1=n+1个空指针域

基本介绍：

中序遍历二叉树


image-20201025215643501

1.二叉排序

创建和遍历

package tree.binaryTree;

/*
@Author CQ
@Date 2020/10/21 19:31
@Version 1.0
*/

public class BinaryTreeDemo {

public static void main(String[] args) {<br />        int[] arr= {7,3,10,12,5,1,9};
    BinarySortTree binarySortTree = new BinarySortTree();<br />        for(int i =0;i<arr.length;i++) {<br />            binarySortTree.add(new Node(arr[i]));<br />        }<br />        binarySortTree.infixOrder();<br />    }<br />}<br />//创建二叉排序树<br />class BinarySortTree{<br />    private Node root;<br />    public void add(Node node){<br />        if(root==null){<br />            root=node;<br />        }else {<br />            root.add(node);<br />        }<br />    }<br />    //中序遍历<br />    public void infixOrder(){<br />        if(root!=null){<br />            root.infixOrder();<br />        }else {<br />            System.out.println("为空不能遍历");<br />        }<br />    }<br />}

//创建node节点
class Node{
int value;
Node left;
Node right;

@Override<br />    public String toString() {<br />        return "Node{" +<br />                "value=" + value +<br />                '}';<br />    }
public Node(int value) {<br />        this.value = value;<br />    }<br />    //添加节点的方法<br />    //递归的形式添加节点<br />    public void add(Node node){<br />        if(node==null){<br />            return;<br />        }<br />        //判断传入节点的值和当前子树的根节点的关系。<br />        if(node.value<this.value){<br />            if(this.left==null){<br />                left=node;<br />            }else {<br />                this.left.add(node);<br />            }<br />        }else {<br />            if(this.right==null){<br />                right=node;<br />            }else{<br />                this.right.add(node);<br />            }<br />        }<br />    }<br />    //中序遍历<br />    public void infixOrder(){<br />        if(this.left!=null){<br />            this.left.infixOrder();<br />        }<br />        System.out.println(this.toString());<br />        if(this.right!=null){<br />            this.right.infixOrder();<br />        }<br />    }<br />}

2.平衡二叉树(AVL)树

1. 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。
2. 具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方有红黑树、AVL、替罪羊树、Treap、伸展树等。
3. 举例说明,看看下面哪些AVL树，为什么?

image-20201022214759496

image-20201022220524393
public class AVLTreeDemo {

public static void main(String[] args) {<br />//        int[] arr= {10,12,8,9,7,6};<br />        int[] arr= {10,11,7,6,8,9};
    AVLSortTree avlSortTree = new AVLSortTree();<br />        for(int i= 0;i<arr.length;i++)<br />        {<br />            avlSortTree.add(new Node(arr[i]));<br />        }<br />        //遍历<br />        avlSortTree.infixOrder();
    System.out.println("在没有平衡处理前====");
    System.out.println(avlSortTree.getRoot().height());<br />        System.out.println("没有平衡处理前左子树的高度");<br />        System.out.println(avlSortTree.getRoot().leftHeight());<br />        System.out.println("没有平衡处理前右子树的高度");<br />        System.out.println(avlSortTree.getRoot().rightHeight());<br />        System.out.println(avlSortTree.getRoot());<br />        System.out.println(avlSortTree.getRoot().left.value);<br />        System.out.println(avlSortTree.getRoot().right.value);
}<br />}

//创建AVL树
class AVLSortTree{
private Node root;

public Node getRoot() {<br />        return root;<br />    }
public void add(Node node){<br />        if(root==null){<br />            root=node;<br />        }else {<br />            root.add(node);<br />        }<br />    }<br />    //中序遍历<br />    public void infixOrder(){<br />        if(root!=null){<br />            root.infixOrder();<br />        }else {<br />            System.out.println("为空不能遍历");<br />        }<br />    }<br />}

//创建node结点
class Node{
int value;
Node left;
Node right;

@Override<br />    public String toString() {<br />        return "Node{" +<br />                "value=" + value +<br />                '}';<br />    }
public Node(int value) {<br />        this.value = value;<br />    }
//返回左子树的高度<br />    public int leftHeight(){<br />        if(left==null){<br />            return 0;<br />        }<br />        return left.height();<br />    }<br />    //返回右子树的高度<br />    public int rightHeight(){<br />        if(right==null){<br />            return 0;<br />        }<br />        return right.height();<br />    }
// 返回当前结点的高度，以该节点为根结点的树的高度<br />    public int height(){<br />        return Math.max(left == null ? 0:left.height(),right ==null ?0: right.height())+1;<br />    }
//左旋转的方法<br />    private void leftRotate(){<br />        //创建新的结点，以当前根结点的<br />        Node newNode = new Node(value);<br />        //把新的结点的左子树设置成当前结点的左子树<br />        newNode.left=left;<br />        //把新的结点的右子树设置为当前结点的右子树的左子树<br />        newNode.right=right.left;<br />        //把当前结点的值替换成右子结点的值<br />        value=right.value;<br />        //把当前结点的右子树设置成当前节点右子树的右子树<br />        right=right.right;<br />        //当前结点的左子树为新结点<br />        left=newNode;<br />    }<br />    private void rightRotate(){<br />        Node newNode = new Node(value);<br />        newNode.right=right;<br />        newNode.right=left.right;
    value=left.value;<br />        left=left.left;<br />        right=newNode;<br />    }
//添加节点的方法<br />    //递归的形式添加节点<br />    public void add(Node node){<br />        if(node==null){<br />            return;<br />        }<br />        //判断传入节点的值和当前子树的根节点的关系。<br />        if(node.value<this.value){<br />            if(this.left==null){<br />                left=node;<br />            }else {<br />                this.left.add(node);<br />            }<br />        }else {<br />            if(this.right==null){<br />                right=node;<br />            }else{<br />                this.right.add(node);<br />            }<br />        }
    //当添加完一个结点后，如果右子树的高度比左子树高度高超过1 左旋转<br />        if(rightHeight()-leftHeight()>1){<br />            if(right!=null && right.leftHeight()>right.rightHeight()){<br />                right.rightRotate();<br />            }<br />            leftRotate();<br />            return; //关键<br />        }
    //当添加完一个结点后，左子树比右子树高超过1<br />        if(leftHeight()-rightHeight()>1){<br />            if(left!=null && left.rightHeight()>left.leftHeight()){<br />                left.leftRotate();<br />            }<br />            rightRotate();<br />            return;  //关键<br />        }
}<br />    //中序遍历<br />    public void infixOrder(){<br />        if(this.left!=null){<br />            this.left.infixOrder();<br />        }<br />        System.out.println(this.toString());<br />        if(this.right!=null){<br />            this.right.infixOrder();<br />        }<br />    }<br />}<br />![](https://cdn.nlark.com/yuque/0/2021/png/21994224/1627020159630-ad405377-cfae-403a-a40f-d2597e4db051.png#align=left&display=inline&height=444&margin=%5Bobject%20Object%5D&originHeight=444&originWidth=1485&status=done&style=none&width=1485)<br />image-20201023143634747

二叉树问题分析

image-20201023192701190

3.多路查找树

多叉树

1. 在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树(multiway tree)
2. 后面我们讲解的2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。

3. .举例说明(下面2-3树就是一颗多叉树)
   

   B树

   
   image-20201023153252870

   3.1 2-3树基本介绍

   2-3树是最简单的B-树结构,具有如下特点:

4. 2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)

5. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
6. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点.
7. 2-3树是由二节点和三节点构成的树。

image-20201023160517053
自己画图试试

3.2 B树

B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上，B-tree就是指的B树.

image-20201023185122918

3.3 B+树 B树的变种

3.4 B*树 B+树的变体，在B+树的非根非叶子节点加入指向兄弟的指针

B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B树分配新结点的概率比B+树要低，空间使用率更高；

图：

1. 前面我们学了线性表和树
2. 线性表局限于一个直接前驱和一个直接后继的关系
3. 树也只能有一个直接前驱也就是父节点

4. 当我们需要表示多对多的关系时，这里我们就用到了图。

   1.图的常用概念

   顶点 vertex 边edge 路径 无向图 有向图 带权图(网)

   邻接矩阵

   
   image-20201023194612665

   邻接表

   
   image-20201023194638121

   实例

   
   image-20201024093926325

   代码

   public class Graph {
   private ArrayList vertexList;
   private int[][] edges;
   private int numOfEdges;

   public Graph(int n){
   edges = new int[n][n];
   vertexList = new ArrayList<>(n);
   numOfEdges=0;
   }

   public static void main(String[] args) {
   //测试图
   int n = 5; //结点的个数
   String[] VertexValue ={“A”,”B”,”C”,”D”,”E”};
   Graph graph = new Graph(n);
   for(String value:VertexValue){
   graph.insertVertex(value);
   }
   //添加边
   Scanner sc = new Scanner(System.in);
   for (int i =0;i {
   for (int j =0;j<=i;j++)
   {
   graph.insertEdge(i,j,sc.nextInt());
   }
   }
   graph.printGraph();

   }

   //获得边的权重
   public int getEdgeWeight(int v1,int v2){
   return edges[v1][v2];
   }
   //获得结点
   public String getVertex(int index){
   return vertexList.get(index);

   }
   /*
   
   @param v1 表示点的下标即使第二几个顶点
   @param v2 第二个顶点对应的下标
   @param weight 表示
   /
   //添加边
   public void insertEdge(int v1,int v2,int weight){
   edges[v1][v2] = weight;
   edges[v2][v1] = weight;
   numOfEdges++;
   }
   //插入结点
   public void insertVertex(String vertex){
   vertexList.add(vertex);
   }
   public void printGraph(){
   /for (int i =0;i for(int j =0 ;j System.out.print(edges[i][j]);
   }
   System.out.println();
   }/
   for (int[] arr:edges)
   System.out.println(Arrays.toString(arr));
   }

}

2.图深度优先遍历DFS

深度优先遍历基本思想

图的深度优先搜索(Depth First Search)。

1. 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
2. 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的
   所有邻接结点进行横向访问。
3. 显然，深度优先搜索是一个递归的过程

   3.广度优先遍历BFS

   图的广度优先搜索(Broad First Search)。
   类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点