樹與二叉樹與二叉平衡排序樹(上)

二叉樹與二叉平衡樹

樹

簡單介紹一下樹

度

樹的度：找到分支最多的節點，這個節點有多少分支，這棵樹的度就為幾。

分支最多的節點為D，它有三個分支

這棵樹的度為3

深度

樹的深度就是樹的層數

深度為4

根節點與葉子節點

葉子節點：沒有子節點的節點

這棵樹的根節點是A

葉子節點為E,F,G,H

二叉樹

樹的度最高不超過2的樹，稱為二叉樹

滿二叉樹

如果一個節點有子節點，那麼他一定有兩個節點并且葉子節點都在樹的最後一層

完全二叉樹

除了最後一層節點是滿的，最後一層的節點都集中在左側

滿二叉樹是完全二叉樹

二叉樹的周遊

前序周遊：先根次序周遊

根左右

先打根節點，再打左子樹，再打右子樹

1,2,4,5,3,6

中序周遊：中跟次序周遊

左根右

先列印左子樹，在列印根節點在列印右子樹

4,2,5,1,3,6

後序周遊：後根次序周遊

左右根

先列印左子樹，在列印右子樹，在列印根節點

4,5,2,6,3,1

以下是代碼實作

public static void firstRoot(TreeNode root){
        if (root == null)return;
        System.out.println(root.val);
        firstRoot(root.left);
        firstRoot(root.right);
    }
    
  public static void midRoot(TreeNode root){
        if (root == null)return;
        midRoot(root.left);
        System.out.println(root.val);
        midRoot(root.right);
    }

    public static void lastRoot(TreeNode root){
        if (root == null)return;
        lastRoot(root.left);
        lastRoot(root.right);
        System.out.println(root.val);
  	  }
           

建立一個二叉樹

通過前序和中序建立一個二叉樹。

給我們一個前序周遊和中序周遊我們來建立二叉樹，首先我們要先找根節點，通過根節點再找到它的左子樹和右子樹，最後建立二叉樹。

以下是代碼實作

private static int getIndex(int[] arr , int target){
        for (int i = 0 ; i <arr.length ; i++){
            if (arr[i] == target)return i;
        }
        return 0;
    }

    public static TreeNode buildTree(int[] first,int[] mid){
        if (first == null || mid == null || first.length == 0 || mid.length == 0 || first.length != mid.length) return null;
        //從前序周遊中找到根節點
        TreeNode root = new TreeNode(first[0]);
        //在中序周遊中找到根節點位置的索引
        int rootIndex = getIndex(mid,root.val);
        //找到左子樹的前序和中序
        int[] leftMid = Arrays.copyOfRange(mid,0,rootIndex);
        int[] leftFirst = Arrays.copyOfRange(first,1,rootIndex + 1);
        //找到右子樹的前序和中序
        int[] rightMid = Arrays.copyOfRange(mid,rootIndex-1,mid.length);
        int[] rightFirst = Arrays.copyOfRange(first,rootIndex + 1,first.length);
        //遞歸建構左右子樹
        TreeNode left = buildTree(leftFirst,leftMid);
        TreeNode right = buildTree(rightFirst,rightMid);
        //将左右子數添加到目前的根節點
        root.left = left;
        root.right = right;
        return root;
    }
           

通過後序和中序建立二叉樹的做法與前序和中序建立差不多，後序的根結點是在最後一個。

二叉樹的廣度和深度優先搜尋

深度優先搜尋

public static boolean dfs(TreeNode root,int target){
        if (root == null)return false;
        if (root.val == target)return true;
        return dfs(root.left,target) || dfs(root.right,target);
    }
           

廣度優先搜尋

public static boolean bfs(ArrayList<TreeNode> roots,int target){
        if (roots == null || roots.size() == 0)return false;
        ArrayList<TreeNode> childRoots = new ArrayList<>();
        for (TreeNode temp : roots){
            if (temp.val == target)return true;
            if (temp.left != null)childRoots.add(temp.left);
            if (temp.right != null)childRoots.add(temp.right);
        }
        return bfs(childRoots,target);
    }

    public static boolean bfs(TreeNode root,int target){
        ArrayList<TreeNode> roots = new ArrayList<>();
        roots.add(root);
        return bfs(roots,target);
    }
           

二叉樹的比較

比較兩個二叉樹是否相等

public static boolean compareTree(TreeNode root1,TreeNode root2){
        if (root1 == null && root2 != null || root1 != null && root2 == null)return false;
        if (root1 == null && root2 == null)return true;
        if (root1.val != root2.val)return false;
        return compareTree(root1.left,root2.left) && compareTree(root1.right,root2.right);
    }
           

如果左右子樹互換

public static boolean compareTree2(TreeNode root1,TreeNode root2){
        if (root1 == null && root2 != null || root1 != null && root2 == null)return false;
        if (root1 == null && root2 == null)return true;
        if (root1.val != root2.val)return false;
        return compareTree(root1.left,root2.left) && compareTree(root1.right,root2.right)
                || compareTree(root1.left,root2.right) && compareTree(root1.right,root2.left);
    }
           

普利姆算法

我們要将所有點連通，并且讓他們之間的距離最小

我們首先

1.任選一個點作為起點

2.找到與已連接配接部分路徑最短的的點。

3.不能形成回路

如何用程式表示一個圖

1.點集合

set集合 Set

2.邊集合

二維數組· int[][] distance

準備工作

public class MapNode {
    public int val;
    public int index;
    public List<MapNode> neighbor;
    public MapNode(int val,int index){
        this.val = val;
        this.index = index;
        neighbor = new ArrayList<>();
    }
}

           

普利姆算法具體實作

public static MapNode getMapNodeByIndex(Set<MapNode> pointSet,int index){
        for (MapNode node : pointSet){
            if (node.index == index )return node;
        }
        return null;
    }
    public static void getMinDis(Set<MapNode> pointSet,int[][] distance,Set<MapNode> linkedPoint){
        MapNode start = null;
        MapNode end = null;
        int minDis = Integer.MAX_VALUE;
        //找到距離已有的點最近的點
        for (MapNode myPoint : pointSet){
            for (int i = 0 ; i < distance[myPoint.index].length ; i++){
                if (distance[myPoint.index][i] < minDis//找到比最小距離要小的點
                        && myPoint.index != i//除去自己到自己的距離
                        && !linkedPoint.contains(getMapNodeByIndex(pointSet,i))){
                        //已連接配接的點不能有序号為i的點
                    start = myPoint;
                    end = getMapNodeByIndex(pointSet,i);
                    minDis = distance[myPoint.index][i];
                }
            }
        }
        //将距離最近的點連接配接在一起
        start.neighbor.add(end);
        end.neighbor.add(start);
        linkedPoint.add(end);
    }
    public static void prim(Set<MapNode> pointSet,int[][] distance,MapNode begin){
        Set<MapNode> linkedPoint = new HashSet<>();
        linkedPoint.add(begin);
        while(linkedPoint.size() < pointSet.size()){
            getMinDis(pointSet,distance,linkedPoint);
        }
    }
           

克魯斯卡爾算法

克魯斯卡爾算法也叫加邊法

1.找到最短的邊

2.邊不能重複

3.邊的兩個點不能出自同一連通區域（不能形成環）

以下是代碼實作

public static List<MapNode> getMapNodeList( List<List<MapNode>> linkedMapNode, MapNode 	node){
        for (List<MapNode> mapNodes : linkedMapNode){
            if (mapNodes.contains(node))return mapNodes;
        }
        return null;
    }


    public static void getMinDis(Set<MapNode> pointSet,int[][] distance, List<List<MapNode>> linkedMapNode){
        //找到最短的邊

        int minDis = Integer.MAX_VALUE;
        MapNode begin = null;
        MapNode end = null;
        List<MapNode> beginList = null;
        List<MapNode> endList = null;
        for (int i = 0 ; i < distance.length ; i++){
            for (int j = 0 ; j < distance[i].length ; j++){
                if (distance[i][j] < minDis && i != j){
                    MapNode a = getMapNodeByIndex(pointSet,i);
                    MapNode b = getMapNodeByIndex(pointSet,j);
                    List<MapNode> alist = getMapNodeList(linkedMapNode,a);
                    List<MapNode> blist = getMapNodeList(linkedMapNode,b);
                    if (alist != null && blist != null && alist == blist){
                        //判斷是否出自同一部落
                        minDis = distance[i][j];
                        begin = a;
                        end = a;
                        beginList = alist;
                        endList = blist;
                    }
                }
            }
        }

        begin.neighbor.add(end);
        end.neighbor.add(begin);
        //看看這兩個部落是否需要合并
        if (beginList == null && endList == null){
            //兩個都是新的點
            List<MapNode> mapNodes = new ArrayList<>();
            mapNodes.add(begin);
            mapNodes.add(end);
            linkedMapNode.add(mapNodes);
        }else if (beginList != null && endList == null){
            //兩個點其中一個是新的
            beginList.add(end);
        }else if (endList != null && beginList == null){
            endList.add(begin);
        }else if (beginList != null && endList != null){
            beginList.addAll(endList);
            linkedMapNode.remove(endList);
        }

        //判斷這個邊能不能連接配接
        //1.兩個點都是新的
        //2.兩個點其中一個是新的(其中一個點沒有部落)
        //3.兩個點出自不同的連通區域(兩個點來自不同的部落)
        //同以上三點等效 ==== 兩個點不能出自同一個部落

    }
    public static void kruskar(Set<MapNode> pointSet,int[][] distance){

        List<List<MapNode>> linkedMapNode = new ArrayList<>();//部落的集合
        while (linkedMapNode.size() == 1 && linkedMapNode.get(0).size() == pointSet.size()){
            //隻能有一個部落，并且唯一的一個部落大小是和所有的點的集合大小一樣
            getMinDis(pointSet,distance,linkedMapNode);

        }

    }