이 진 트 리 의 재 귀, 비 재 귀 및 층 차 를 옮 겨 다 니 는 자바 구현

요 며칠 동안 의 임 무 는 나 무 를 사용 해 야 하 는데 마침 자바 를 배 웠 을 때 자바 로 가장 기본 적 인 이 진 트 리 를 복습 하고 싶 었 습 니 다.방금 공 부 했 기 때문에 코드 가 규범 에 맞지 않 고 간결 하 게 쓰 여 개인 기록 만 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:

/**
 * @author qiaoyang
 * @version 1.0
 */
class TreeNode //     
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val=val;
    }
}

다음은 이 진 트 리 의 구축 방법 으로 이 진 트 리 가 비어 있 는 것 과 비어 있 는 것 두 가지 상황 으로 나 뉜 다.이 진 트 리 는 빈 곳 에 뿌리 노드 를 만 들 고 빈 곳 이 아 닐 때 적당 한 위 치 를 선택 하여 삽입 합 니 다.

    public void insert(int val) {//     
        if (root == null) {
            root = new TreeNode(val);
        } else {
            _insert(root, val);
        }
    }

    private void _insert(TreeNode n, int val) {
    //       ，        
        assert n != null;
        if (val > n.val) {//   ，    
            if (n.right != null) {
                _insert(n.right, val);
            } else {
                n.right = new TreeNode(val);
            }
        }
        else{
            if (n.left != null) {
                _insert(n.left, val);
            } else {
                n.left = new TreeNode(val);
            }
        }
    }

그 다음 에 나무의 층 차 를 옮 겨 다 니 는 것 입 니 다. 즉, 넓 은 범위 에서 먼저 옮 겨 다 니 는 코드 입 니 다.

public void BFS(TreeNode root)//      
    {
        ArrayDeque deque=new ArrayDeque();
        deque.add(root);//     
        while(!deque.isEmpty()){
            TreeNode temp=deque.remove();
            System.out.print(temp.val+"--");
            if(temp.left!=null){
                deque.add(temp.left);
            }
            if(temp.right!=null){
                deque.add(temp.right);
            }
        }
    }

다음은 이 진 트 리 의 세 가지 재 귀적 코드 입 니 다.

    public void PreOrder(TreeNode root)//      
    {
        if(root!=null){
            System.out.print(root.val+"--");//        
            PreOrder(root.left);
            PreOrder(root.right);
        }
    }
    public void InOorder(TreeNode root)//      
    {
        if(root!=null){
            InOorder(root.left);
            System.out.print(root.val+"--");
            InOorder(root.right);
        }
    }
    public void PostOrder(TreeNode root)//      
    {
        if(root!=null){
            PostOrder(root.left);
            PostOrder(root.right);
            System.out.print(root.val+"--");
        }
    }

다음은 이 진 트 리 의 세 가지 비 재 귀적 으로 옮 겨 다 니 며 스 택 을 사용 하여 이 루어 집 니 다.

public void PreOrder_Stack(TreeNode root)//        
    {
        Stack sta=new Stack();
        while(!sta.empty()||root!=null){
            if(root==null){
                TreeNode temp=sta.pop();
                root=temp.right;
            }
            else{
                System.out.print(root.val+"--");//    
                sta.push(root);//   ，       
                root=root.left; 
            }
        }
    }

    public void InOorder_Stack(TreeNode root)//       
    {
        Stack sta=new Stack();
        while(!sta.empty()||root!=null){
            if(root==null){
                TreeNode temp=sta.pop();
                System.out.print(temp.val+"--");
                root=temp.right;
            }
            else{
                sta.push(root);
                root=root.left;//       
            }
        }
    }
    public void PostOrder_Stack(TreeNode root)//       
    {
        Stack sta=new Stack();
        TreeNode p=root;
        do{
    //      while  ，          ，    ，      
            while(p!=null){//       
                sta.push(p);
                p=p.left;
            }
            TreeNode q=null;
            while(!sta.empty()){
                p=sta.pop();
                if(p.right==q){
                    System.out.print(p.val+"--");
                    q=p;//        
                }
                else{
                    sta.push(p);
                    p=p.right;
                    break;
                }
            }
        }while(!sta.empty());
    }

마지막 으로 간단 한 주 함 수 를 써 서 테스트 를 진행 하 였 다.

public class Main//  
{
    public static void main(String[] args)
    {
        Tree tree=new Tree();
        int arr[]={2,4,6,7,1,5,9,12,3,0};
        for(int i=0;i
            tree.insert(arr[i]);
        }
        System.out.println("    ：");
        tree.PreOrder(tree.root);
        System.out.println("");
        tree.InOorder(tree.root);
        System.out.println("");
        tree.PostOrder(tree.root);
        System.out.println("");
        System.out.println("     ");
        tree.PreOrder_Stack(tree.root);
        System.out.println("");
        tree.InOorder_Stack(tree.root);
        System.out.println("");
        tree.PostOrder_Stack(tree.root);
        System.out.println("");
        System.out.println("      ：");
        tree.BFS(tree.root);
    }
}

기본적으로 이 진 트 리 의 생 성, 재 귀 와 비 재 귀, 그리고 층 차 를 옮 겨 다 니 는 것 을 실현 했다.