JAVA 이 진 트 리 의 몇 가지 옮 겨 다 니 기(재 귀,비 재 귀)실현

먼저 이 진 트 리 는 나무 구조의 특수 한 유형 으로 나무 구조의 모든 특징 에 부합된다.이 블 로 그 는 이 진 트 리 에 대해 나무의 기본 개념,이 진 트 리 의 기본 조작(저장,나무의 깊이,노드 갯 수,각 층 의 노드 갯 수),이 진 트 리 의 네 가지 옮 겨 다 니 기(차원,순서,중간 순서,뒤 순서)를 소개 합 니 다.
기본 개념
이 진 트 리 는 5 가지 기본 형태 가 있다.

주:이 진 트 리 질서 있 는 나 무 는 한 노드 의 좌우 노드 는 크기 의 구분 이 있 습 니 다.우 리 는 보통 왼쪽 아이 가 오른쪽 아이 보다 크 고 아래 의 실현 은 모두 이 규칙 을 바탕 으로 합 니 다.이 진 트 리 는 세 가지 로 나 뉜 다.이 진 트 리,완전 이 진 트 리,불완전 이 진 트 리 이다.

이 진 트 리 의 네 가지 옮 겨 다 니 기:차원,선서,중 서,후 서 는 먼저 비 재 귀적 으로 위의 그림 의 만 이 진 트 리 를 실현 합 니 다.1.선서:뿌리 정도,스 택 으로 이 루어 집 니 다.다음은 그의 흐름 도와 스 택 에 들 어 가 는 상태 도(n 은 각 노드 의 값)출력:12,10,9,11,15,14,16


2.중 서:왼쪽 뿌리 오른쪽,스 택 으로 이 루어 집 니 다.중 서 의 스 택 상 태 는 선 서 와 같 습 니 다.출력 위치 만 다 르 고 먼저 스 택 에 들 어가 기 전에 출력 합 니 다.중 서 는 스 택 에서 나 온 후에 출력 합 니 다.9,10,11,12,14,15,16

3.후 순:좌우 뿌리,두 개의 스 택 으로 출력:9,11,10,14,16,15,12


다음은 실 현 된 코드 입 니 다.

//       
 class Node {
  public int key;//    
  public String Data;//       
  public Node leftNode;//   
  public Node rightNode;//   

  //        
  public Node(int key,String Data){
    this.key=key;
    this.Data=Data;
    this.leftNode=null;
    this.rightNode=null;
  }

  //    
  public int getKey(){
    return key;

}

}
public class BinaryTree {
  public Node root;
  public int h=0;

  //    
  public void insert(int key,String Data){
    //       
    Node newNode=new Node(key, Data);
    //            
    if(root==null){
      root=newNode;

    }
    else
    {
      Node current=root;
      Node parent;
      while(true){
        parent=current;
        //    ，              
        if(key<current.key){
          current=current.leftNode;//       
          if(current==null){
            parent.leftNode=newNode;//      
            return;
          }//     If end;
        }//    If end;
        else{
          current=current.rightNode;
          if(current==null){
            parent.rightNode=newNode;
            return;
          }//  
        }//   

      }
    }
  }//insert end;

//  
  public void printlTree(Node node){
    System.out.print("*");

    System.out.print(node.getKey());


  }




  //  
  public int Height(Node node){
    if(node==null){
      return 0;
    }
    else{
      int i=Height(node.leftNode);
      int j=Height(node.rightNode);
      return (i>j)?(i+1):(j+1);

    }
  }

  //    
  public int NodeNum(Node node){
    if(node==null){
      return 0;
    }
    return NodeNum(node.leftNode)+NodeNum(node.rightNode)+1;

  }

  // K      
  public int getLeafNodeNum(Node node,int i){
    if(node==null){
      return 0;
    }
    else{
      if(i==0){
        return 1;
      }
      else{
        int numLeft=getLeafNodeNum(node.leftNode,i-1);
        int numRight=getLeafNodeNum(node.rightNode,i-1);
        return (numLeft+numRight);
      }
    }
    }



  //    
  public void LevelOrder(Node node){
    Queue<Node> queue=new LinkedList<Node>();
    if(node==null){
      return;
    }
    queue.add(node);
    while(!queue.isEmpty()){
      Node temp=queue.poll();
      System.out.print("*");
      System.out.print(temp.getKey());
      if(temp.leftNode!=null){
        queue.add(temp.leftNode);
      }
      if(temp.rightNode!=null){
        queue.add(temp.rightNode);
      }
    }
  }

  //      
  public void preOrder(Node node){
    if(node!=null){
    printlTree(node);
    preOrder(node.leftNode);
    preOrder(node.rightNode);
  }
  }
  //       
  public void NpreOrder(Node node){

    Stack<Node> sk=new Stack<Node>();
    Node n=node;
    while(!sk.isEmpty()||n!=null){
      if(n!=null){
      System.out.print("<<<");
      System.out.print(n.getKey());

      sk.push(n);
      n=n.leftNode;
      }

      else{
      n=sk.pop();;
      n=n.rightNode;
    }
  }
  }


  //    
    public void inOrder(Node node){
      if(node!=null){
      preOrder(node.leftNode);
      printlTree(node);

      preOrder(node.rightNode);
    }
    }

    //        
    public void NinOrder(Node node){
      Stack<Node> s=new Stack<Node>();
      Node n=node;
      while(n!=null||!s.isEmpty()){
        if(n!=null){
          s.push(n);
          n=n.leftNode;
        }
        else{
          n=s.pop();
          System.out.println(n.getKey());
          n=n.rightNode;

        }
      }
    }

    //    
        public void postOrder(Node node){
          if(node!=null){
          preOrder(node.leftNode);

          preOrder(node.rightNode);
          printlTree(node);

        }
        }

        //       
        public void NpostOrder(Node node){
          Stack<Node> s1=new Stack<Node>();//     
          Stack<Node> s2=new Stack<Node>();//     
          Node n=node;
        while(!s1.isEmpty()||n!=null){
          if(n!=null){
            s1.push(n);
            s2.push(n);
            n=n.rightNode;
          }
          else{
            n=s1.pop();
            n=n.leftNode;
          }
        }
        while(!s2.isEmpty()){
          System.out.println("((("+s2.pop().getKey());
        }

        }

public static void main(String[] args) {

    BinaryTree bt=new BinaryTree();
    bt.insert(12, "A");
    bt.insert(10, "B");
    bt.insert(15, "C");
    bt.insert(9, "D");
    bt.insert(11, "E");
    bt.insert(14, "F");
    bt.insert(16, "G");

   System.out.println("        ："+bt.Height(bt.root));
    System.out.println("          ："+bt.NodeNum(bt.root));


    System.out.println("    ：");
    bt.preOrder(bt.root);
    System.out.println();

    System.out.println("       ：");
    bt.NpreOrder(bt.root);
    System.out.println();

    System.out.println("    ：");
    bt.inOrder(bt.root);
    System.out.println();

    System.out.println("       ：");
    bt.NinOrder(bt.root);
    System.out.println();

    System.out.println("    ：");
    bt.postOrder(bt.root);
    System.out.println();

    System.out.println("       ：");
    bt.NpostOrder(bt.root);
    System.out.println();

    System.out.println("    ：");
    bt.LevelOrder(bt.root);
    System.out.println();

    System.out.println("    "+bt.getLeafNodeNum(bt.root, 2));

  }
    }

코드 테스트 실행 가능(*65342-*65342)V
이것 은 단지 이 진 트 리 의 일부분 일 뿐 입 니 다.데이터 구 조 를 처음 배 우 는 친 구 를 도 울 수 있 기 를 바 랍 니 다.잘못된 부분 이 있 으 면 말씀 해 주 십시오!!