자바 데이터 구조 학습 트 리

나무
1.1 개념
선형 표 가 나타 내 는 일일이 대응 하 는 선형 관계 와 달리 나 무 는 데이터 요소 간 에 더욱 복잡 한 비 선형 관 계 를 나타 낸다.
직관 적 으로 볼 때 나 무 는 분기 관계 로 정 의 된 차원 구조 이다.나 무 는 객관 적 인 세계 에서 광범 위 하 게 존재 한다.예 를 들 어 인류 사회의 족보 와 각종 사회 조직 기 구 는 나무의 이미지 로 표시 할 수 있다.
쉽게 말 하면 나 무 는 1 대 다 의 관 계 를 나타 낸다.
정의(논리 구조):
나무(Tree)는 n(n>=0)개의 결점 에 대한 유한 한 집합 입 니 다.결점 이 없 는 나 무 를 빈 나무 라 고 합 니 다.임의의 비 빈 나무 에 있 습 니 다.뿌리(root)라 고 불 리 는 특정한 결점 만 있 습 니 다.
n>1 의 경우 나머지 결점 은 m(m>0)개의 서로 교차 하지 않 는 유한 집합 T1,T2,...........................................................
메모:나무의 정 의 는 나무의 정의 에 나무의 개념 을 사용 하 는 재 귀적 인 정의 입 니 다.
在这里插入图片描述
1.2 용어
(1)한 결점 의 자나무 뿌리 를 이 결점 의 아이(아들)라 고 부 르 고 그 에 상응하는 결점 을 자나무 뿌리 의 아버지 라 고 부른다.
(2)아이 가 없 는 결점 을 나뭇잎 이 라 고도 부 르 고 잎 결점 이 라 고도 부른다.외국 에 서 는 닐 을 잎 이 라 고 부른다)같은 아버지의 결점 을 가지 고 서로 형제(동포,자매)가 된다.
(3)결점 n1 에서 nk 까지 의 경 로 는 노드 n1 n2...nk 의 한 서열 로 정의 되 어 1<=i(4)결점 의 등급 은 뿌리 부터 정의 하고 뿌리 는 1 층 이 며 뿌리의 아 이 는 2 층 이다.만약 어떤 결점 이 i 층 에 있다 면 그 아 이 는 i+1 층 에 있다.트 리 에 등급 정의 가 있 음)
在这里插入图片描述
(5)임의의 결점 니,니 의 깊이 는 뿌리 에서 니 까지 의 유일한 경로 의 길이 이다.따라서 뿌리의 깊이 는 0 이다.깊이
在这里插入图片描述
(6)나무의 높이 는 그 뿌리의 높이 와 같다.나무의 깊이 는 가장 깊 은 나뭇잎 의 깊이 와 같다.그 깊이 는 항상 이 나무의 높이 와 같다.
(7)성질:나무 한 그루 에 n 개의 결점 이 있다 면 n-1 개의 변 이 있다.(왜 일 까?)
모든 결점 은 한 변 이 그것 을 가리킨다(뿌리 노드 제외)
모든 변 이 하나의 결점 을 가리킨다.
(8)개념:도(그림 과 같은 데이터 구조)는 그림 과 같은 데이터 구 조 를 말한다.모든 노드 의 도:보통 몇 개의 노드 가 나의 이 노드 와 관련 이 있다 는 것 을 말한다.
나무 라 는 데이터 구조:도:보통 몇 명의 아이들 이 있 는 것 을 말한다.
1.3 나무의 실현
어떻게 코드 를 통 해 나 무 를 시 뮬 레이 션 합 니까?
집합 클래스:데이터 용기
배열 링크,배열+링크
데이터 구조 표현 형식:트 리
1.3.1 배열 로 나무 한 그루?
굳이 나무 한 그루 를 배열 로 저장 해 야 한다 면 괜 찮 지만 여러 가지 문제 가 있 을 수 있다.
1.3.2 링크 로 나무 한 그루?
링크 로 나무 한 그루 를 저장 하 는 것 도 문제 가 있 을 수 있 습 니 다(1,메모리 희생,2,여러 노드 유형)
1.3.3 나무의 전환
(1)전 환 된 나 무 는 저장 하기 쉽다.아래 의 특징 에 따라 전 환 된 나 무 는 이 진 트 리 라 고 부른다.
① 결점 에 아이 가 있다 면 첫 번 째 아 이 를 이 결점 의 left 점 으로 한다.
② 하나의 결산 점 에 형제 결산 점 이 있다 면 그의 형 제 를 결산 점 으로 삼 아 이 결산 점 의 right 자 결산 점 으로 삼 는 다.
在这里插入图片描述
1.4 이 진 트 리
개념:나무 하나,결점 마다 최대 두 명의 아이 가 있 고,아 이 는 엄격 한 좌우 의 구분 이 있다.
1.4.1 이 진 트 리 의 성질
(1)이 진 트 리 는 다음 과 같은 중요 한 성질 을 가진다.
① 이 진 트 리 는 i 층 에서 최대 2 의(i-1)차방 의 노드 가 있다.
② 차원 이 k 인 이 진 트 리 는 많아야 2 의 k 제곱-1 개의 노드 가 있다.
(2)이 진 트 리 T 에 대해 잎 노드 수가 n0 이 고 도가 2 인 노드 수가 n2 이면 n0=n2+1
(3)n 개의 노드 를 가 진 완전 이 진 트 리,나무의 높이 는 log2n(아래로 정렬)이다.
(4)n 개의 결점 이 있 는 완전 이 진 트 리 의 결점 에 대해 층 차 순 으로 1 부터 번 호 를 매기 면 임의의 결점 에 대해 다음 과 같다.
번호 i 가 1 이면 이 노드 는 이 진 트 리 의 뿌리 입 니 다.
번호 i>1 이면 부모 노드 번 호 는 parent(i)=i/2 입 니 다. 
만약 2i>n 이 라면 이 결점 에는 왼쪽 아이 가 없다.그렇지 않 으 면 왼쪽 아이의 번 호 는 2i 이다.
만약 2i+1>n 이 라면 이 결점 에는 오른쪽 아이 가 없다.그렇지 않 으 면 오른쪽 아이의 번 호 는 2i+1 이다.
(5)이 진 트 리 의 부자 결점 관계:2 배 또는 2 배+1 관계
C>이 진 트 리 는 배열 로 저장 할 수 있 습 니 다.바로 상기 특성 에 따라(그러나 실제 응용 과 개발 에서 우 리 는 보통 링크 로 이 진 트 리 를 저장 합 니 다)
1.4.2 이 진 트 리 의 옮 겨 다 니 기
깊이 우선 순위:스 택
(1)먼저 차례 옮 겨 다 니 기:뿌리 노드 를 옮 겨 다 니 고 왼쪽 트 리 를 옮 겨 다 니 며 오른쪽 트 리 를 옮 겨 다 닌 다.
(2)중간 순서 옮 겨 다 니 기:왼쪽 하위 트 리 를 옮 겨 다 니 고 뿌리 노드 를 옮 겨 다 니 며 오른쪽 하위 트 리 를 옮 겨 다 닌 다.
(3)뒤 순 서 를 옮 겨 다 니 기:먼저 왼쪽 트 리 를 옮 겨 다 니 고 오른쪽 트 리 를 옮 겨 다 니 며 뿌리 결산 점 을 옮 겨 다 닌 다.
우선 순위:대기 열
나무의 넓이 를 우선 적 으로 옮 겨 다 니 는 것 은 보통 한 단계 씩 옮 겨 다 니 는 것 입 니 다.(C>그림 의 넓이 를 우선적으로 옮 겨 다 니 기)
1.4.3 이 진 트 리 의 건축 수
약간의 서열(앞 뒤 순서)을 주 고 우 리 는 나무의 원래 모습 을 복원 했다.
Q1:만약 에 우리 가 앞 순서,가운데 순서,뒤의 한 가지 만 알 고 있다 면 이 진 트 리 를 구축 할 수 있 습 니까?하면,만약,만약...만약 할 수 없다 면,반 례 를 들 어 보 세 요.
답:이 진 트 리 를 만 들 수 는 있 지만 유일한 이 진 트 리 를 만 들 수 는 없다.
Q2:만약 에 우리 가 앞 순서,중간 순서,뒤의 두 가지 만 알 고 있다 면 유일한 이 진 트 리 를 구축 할 수 있 습 니까?하면,만약,만약...만약 할 수 없다 면,반 례 를 들 어 보 세 요.
앞 순서+중간 순 서 는 C>앞 순 서 는 뿌리 노드 를 확정 할 수 있 고 중간 순 서 는 뿌리 노드 에 따라 좌우 서브 트 리 를 나 눌 수 있다.
후 서+중 서 는 C>후 서 는 뿌리 노드 를 확정 할 수 있 고 중 서 는 뿌리 노드 에 따라 좌우 서브 트 리 를 나 눌 수 있다.
앞 순서+뒤 순서,안 됩 니 다.모두 뿌리 노드 만 확인 할 수 있 습 니 다.
2.BST(두 갈래 찾기 트 리,두 갈래 찾기 트 리,두 갈래 정렬 트 리)
바로 이 진 트 리 를 바탕 으로 한 정 된 조건 을 증감 하 는 것 이다.나무 에 있 는 모든 결점 에 대해 왼쪽 나무의 결점 은 이 결점 보다 작고 오른쪽 나무의 결점 은 이 결점 보다 크다.
2.1 코드 구현
在这里插入图片描述
주의:귀환 에 주의해 야 할 일
1.재 귀적 인 핵심 사상:디자인 할 때 시작 과 끝 이 어떻게 되 는 지 고려 하지 말고 핵심 논리,부분 견본 을 잡 아 라.
2.수출 문 제 를 주의해 야 한다.
3.만약 에 재 귀 방법 을 실현 하면 이 방법 이 외부 에 직접 방문 되 지 않도록 해 야 한다(문법 문제 가 없고 조작 행위 가 비교적 위험 할 뿐이다)
4.문제 의 규모 에 주의해 야 한다.

/**
 * @author: Mr.Du
 * @description:      
 * @date: 2021/05/04 17:00
 */
public class MyBSTree<T extends Comparable<T>> {

    private Node root;//        
    private int size;//         

    //    
    public boolean add(T value) {
        //                 null: null      
        if (value == null)
            throw new IllegalArgumentException("The param is null");
        //          
        if (root == null) {
            //            ,               
            root = new Node(value, null, null);
            size++;
            return true;
        }

        //    ,   ,    null
        Node index = root;//    
        Node indexF = null;//        
        int com = 0;//  value    
        while (index != null) {
            //       ,         ,         mid     
            com = index.value.compareTo(value);
            indexF = index;
            if (com > 0) {
                index = index.left;
            } else if (com < 0) {
                index = index.right;
            } else {
                // com = 0
                // value   index      
                //            
                //          :
                //                1,    :                  ,            
                //                2,    :              ,            
                //                3,    BST:                ,     
                //          :
                //                
                return false;
            }
        }

        if (com > 0) {
            indexF.left = new Node(value, null, null);
        } else {
            indexF.right = new Node(value, null, null);
        }
        size++;
        return true;
    }

    //       
    public boolean contains(T value) {
        //                 null: null      
        if (value == null)
            throw new IllegalArgumentException("The param is null");

        Node index = root;
        int com = 0;
        while (index != null) {
            com = value.compareTo(index.value);
            if (com > 0) {
                index = index.right;
            } else if (com < 0) {
                index = index.left;
            } else return true;
        }
        //          ,             : index == null          
        return false;
    }
    //             
    public boolean removeByRecursive(T value){
        int oldSize = size;
        root = removeByRe(root,value);
        return size<oldSize;
    }
    //    root            value   
    private Node removeByRe(Node root,T value){
        if (root == null) return null;
        int com = value.compareTo(root.value);
        if (com>0){
            //  value  ,  right   
            root.right = removeByRe(root.right,value);
            return root;
        }else if (com<0){
            //  value  ,  left   
            root.left = removeByRe(root.left,value);
            return root;
        }else{
            //          
            if (root.left!=null&&root.right!=null){
                //            
                //   right      
                Node rightMin = root.right;
                while (rightMin.left!=null){
                    rightMin = rightMin.left;
                }
                //  
                root.value = rightMin.value;
                //    ,  right     rightMin(  rightMin         )
                //         ,    root right          
                root.right = removeByRe(root.right,root.value);
                return root;
            }
            //            
            Node node = root.left != null? root.left : root.right;
            size--;
            return node;
        }
    }
    //              
    public boolean removeByNonRecursive(T value) {
        //   null: null      
        if (value == null)
            throw new IllegalArgumentException("The param is null");
        /*
          :
                     
                          :       ,    
                     
         */
        Node index = root;
        Node indexF = null;
        int com;
        while (index != null) {
            com = value.compareTo(index.value);
            if (com > 0) {
                indexF = index;
                index = index.right;
            } else if (com < 0) {
                indexF = index;
                index = index.left;
            } else
                break;
        }
        // indexF           
        // index           

        //  index null,         ,  false
        if (index == null)
            return false;

        //   ,           
        if (index.left != null && index.right != null) {
            // right        ,         
            Node rightMin = index.right;
            //        
            Node rightMinF = index;
            // index.right      ,  left   
            while (rightMin.left != null) {
                rightMinF = rightMin;
                rightMin = rightMinF.left;
            }

            //    :rightMin.left=null
            //    right       ,              
            index.value = rightMin.value;
            //                    
            indexF = rightMinF;
            index = rightMin;
        }

        //               
        //             ,              ,        

        //            : index
        //         index       indexF

        //  index     ch:
        //   index    ,  ch = null
        //   index    , ch =   null      
        Node ch = index.left != null ? index.left : index.right;

        //          ,               ,          midF = null
        if (indexF == null) {
            root = ch;
            size--;
            return true;
        }

        //    
        if (indexF.left == index) {
            indexF.left = ch;
        } else
            indexF.right = ch;
        size--;
        return true;
    }

    //           :
    //①  
    public List<T> preOrder() {
        //      
        List<T> list = new ArrayList<>();
        //         
        MyLinkedStack<Node> stack = new MyLinkedStack<>();
        //     
        stack.push(root);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            list.add(pop.value);
            if (pop.right != null)
                stack.push(pop.right);
            if (pop.left != null)
                stack.push(pop.left);
        }
        return list;
    }

    //②  
    public List<T> inOrder() {
        Stack<Node> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        Node index = root;
        while (index != null || !stack.empty()) {
            while (index != null) {
                stack.push(index);
                index = index.left;
            }
            Node pop = stack.pop();
            list.add(pop.value);
            index = pop.right;
        }
        return list;
    }

    //③  
    public List<T> postOrder() {
        Stack<Node> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        stack.push(root);
        while (!stack.empty()) {
            Node pop = stack.pop();
            list.add(0, pop.value);
            if (pop.left != null)
                stack.push(pop.left);
            if (pop.right != null)
                stack.push(pop.right);
        }
        return list;
    }

    //            
    //①  
    public List<T> preOrderRecursive() {
        List<T> list = new LinkedList<>();
        preRecursive(list, root);
        return list;
    }

    //   :     
    private void preRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        list.add(node.value);
        preRecursive(list, node.left);
        preRecursive(list, node.right);
    }

    //②  
    public List<T> inOrderRecursive() {
        List<T> list = new LinkedList<>();
        inRecursive(list, root);
        return list;
    }

    //     :      
    private void inRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        inRecursive(list, node.left);
        list.add(node.value);
        inRecursive(list, node.right);
    }

    //③     
    public List<T> postOrderRecursive() {
        List<T> list = new LinkedList<>();
        postRecursive(list, root);
        return list;
    }

    //   :      
    private void postRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        preRecursive(list, node.left);
        preRecursive(list, node.right);
        list.add(node.value);
    }

    //   :       (BFS)
    public List<T> levOrder() {
        List<T> list = new ArrayList<>();
        Queue<Node> queue = new LinkedBlockingQueue<>();

        //      
        queue.offer(root);
        while (!queue.isEmpty()) {
            //     
            Node poll = queue.poll();
            //  
            list.add(poll.value);
            //               
            if (poll.left != null)
                queue.offer(poll.left);
            if (poll.right != null)
                queue.offer(poll.right);
        }
        return list;
    }


    //    :      ,        ,          


    //     [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //     [-20, -25, -50, -10, -5, 7, 2, 25, 30, 100, 10, 1]
    public Node buildTreeByInAndPostOrder(List<T> inOrder, List<T> postOrder) {
        Node treeRoot = buildTreeByInAndPostOrder2(inOrder, postOrder);
        return treeRoot;
    }

    private Node buildTreeByInAndPostOrder2(List<T> inOrder, List<T> postOrder) {
        if (inOrder.size() == 0) return null;
        if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);
        //    :          
        T rootValue = postOrder.get(postOrder.size() - 1);
        //           
        int rootAtInOrderIndex = inOrder.indexOf(rootValue);

        //       (     ): 0 ~ rootAtInOrderIndex-1
        //       (     ): 0 ~ rootAtInOrderIndex -1

        //       (     ): rootAtInOrderIndex + 1 ~ size -1
        //       (     ): rootAtInOrderIndex ~ size - 2

        //   
        //subList():    
        List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
        List<T> leftPostOrder = postOrder.subList(0, rootAtInOrderIndex);

        //   
        //subList():    
        List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex + 1, inOrder.size());
        List<T> rightPostOrder = postOrder.subList(rootAtInOrderIndex, postOrder.size() - 1);
        //          
        Node node = new Node(rootValue, null, null);
        //        ,      
        node.left = buildTreeByInAndPostOrder2(leftInOrder, leftPostOrder);
        //        ,      
        node.right = buildTreeByInAndPostOrder2(rightInOrder, rightPostOrder);

        return node;
    }

    //     [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //     1  -5  -10  -50  -25  -20   10  2  7  100  30  25
    public Node buildTreeByInAndPreOrder(List<T> inOrder, List<T> preOrder) {
        Node treeRoot = buildTreeByInAndPreOrder2(inOrder, preOrder);
        return treeRoot;
    }

    private Node buildTreeByInAndPreOrder2(List<T> inOrder, List<T> preOrder) {
        if (inOrder.size() == 0) return null;
        if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);

        T rootValue = preOrder.get(0);
        int rootAtInOrderIndex = inOrder.indexOf(rootValue);

        //   
        //subList():    
        List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
        List<T> leftPreOrder = preOrder.subList(1, rootAtInOrderIndex + 1);
        //   
        //subList():    
        List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex+1,inOrder.size());
        List<T> rightPreOrder = preOrder.subList(rootAtInOrderIndex+1,preOrder.size());

        Node node = new Node(rootValue,null,null);
        node.left = buildTreeByInAndPreOrder2(leftInOrder,leftPreOrder);
        node.right = buildTreeByInAndPreOrder2(rightInOrder,rightPreOrder);
        return node;
    }

    //  
    public boolean isEmpty() {
        return size == 0;
    }

    //      
    public int size() {
        return size;
    }

    class Node {
        T value;
        Node left;
        Node right;

        public Node(T value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
자바 데이터 구조 학습 트 리 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!

좋은 웹페이지 즐겨찾기