두 갈래 나무의 기본 개념

2452 단어

두 갈래 나무의 기본 개념

  • 노드의 도: 노드가 가지고 있는 서브트리의 개수를 이 노드의 도라고 부른다
  • 잎 노드: 아이가 없는 노드, 즉 도가 0인 노드, 단말기 노드라고도 부른다
  • 분지 노드: 도가 0이 아닌 노드, 나무 한 그루에 잎 노드가 아니면 분지 노드..
  • 노드의 층수: 나무의 뿌리 노드의 층수는 1이고 다른 것은 순서대로 증가한다..
  • 나무의 깊이: 나무 한 그루의 최대 층수..
  • 나무의 도: 나무의 노드의 최대 층수는 바로 이 나무의 도이다..
  • 만 두 갈래 나무(완벽한 두 갈래 나무라고도 부른다): 각 가지 노드에는 좌우 아이가 있고 모든 잎 노드가 같은 층에 있다..
  • 완전 두 갈래 나무: 잎 노드는 최하층이나 차하층에만 나타난다.그리고 최하층의 잎 노드는 나무의 왼쪽에만 있다.주: 만 두 갈래 나무는 틀림없이 완전 두 갈래 나무이고, 완전 두 갈래 나무는 꼭 만 두 갈래 나무가 아니다

  • 두 갈래 나무의 기본 성질

  • 비공 두 갈래 나무의 i층 위에 최대 2i-1개의 노드가 있다(i>=0)
  • 깊이가 k인 두 갈래 나무는 최대 2k-1개의 노드가 있다.최소 K 개의 노드가 있습니다
  • 비공의 수에 대해 도가 0인 노드 수는 총 비례가 2인 노드 수가 1이 많다.왜냐하면 n=01+n2+n0=01+2*n2+1----->n0=n2+1..
  • n개의 노드를 가진 완전한 두 갈래 나무의 깊이는log2n+1이다
  • n개의 노드를 가진 수 중 모두 n-1개의 변이 있고 뿌리 노드를 제외한 다른 노드는 모두 입변이 있다..

  • 두 갈래 트리 코드

    public class Node {
        public int data;
        public Node left;
        public Node right;
        public Node(int data) {
            this.data = data; 
            this.left = null; 
            this.right = null;    
        }  
    }
    

    데이터를 질서정연한 두 갈래 트리에 삽입하여 중간 순서로 훑어보고 작은 것에서 큰 것까지 훑어보고 왼쪽 나무가 가장 작다.현재 노드를 가져옵니다. 데이터가 현재 노드보다 크면 오른쪽 트리에 놓고, 오른쪽 트리가 비어 있지 않으면 계속 아래로 찾습니다.
     public void insert(int data,Node root){
            Node newNode = new Node(data);
            if(root==null){
                root = newNode;
            }else {
                Node current = root;
                Node parent;
                while (true){
                    parent=current;
                    if(data

    귀속 방법 이 두루 퍼지다

       /*
         
         */
        public void inOrder(Node root){
            if(root!=null){
                inOrder(root.left);
                System.out.print(root.data+" ");
                inOrder(root.right);
            }
        }
        /*
         
         */
        public void preOrder(Node root){
            if(root !=null){
                System.out.print(root.data+" ");
                preOrder(root.left);
                preOrder(root.right);
            }
        }
        /*
         
         */
        public void postOrder(Node root){
            if(root!=null){
                postOrder(root.left);
                preOrder(root.right);
                System.out.print(root.data+" ");
            }
        }
    

    좋은 웹페이지 즐겨찾기