【数据结构与算法】十五二叉树遍历 DFS 深度优先递归算法

喜欢ヅ旅行 2022-08-21 10:57 136阅读 0赞

# 【数据结构与算法】十五 二叉树遍历 DFS 深度优先 递归算法 #

结合上一篇的二叉树文章.  
遍历即将树的所有结点访问且仅访问一次.  
Depth-First-Search 深度优先  
基于深度优先算法有三种

# 前序遍历：根节点->左子树->右子树 #

private void preorder(Node node){
            if(null == node)
                return ; 
            System.out.print(node.value);
            preorder(node.left);
            preorder(node.right);
        }

--------------------

# 中序遍历：左子树->根节点->右子树 #

private void midorder(Node node){
            if(null == node)
                return ; 
            midorder(node.left);
            System.out.print(node.value);
            midorder(node.right);
        }

--------------------

# 后序遍历：左子树->右子树->根节点 #

private void postorder(Node node){
            if(null == node)
                return ; 
            postorder(node.left);
            postorder(node.right);
            System.out.print(node.value);
        }

--------------------

# 完整code #

package com.cn.mark.algorithm.binarytree;
    
    
    public class BST <T extends Comparable<? super T>>{
    
    
        private static class Node<T> {
    
            private T value ; 
            private Integer position ; 
            private Integer height ;
            private Node<T> left;
            private Node<T> right;
    
    
            public Node(T value , Integer position, Node<T> left, Node<T> right) {
                this.value =  value;
                this.position = position ; 
                this.height = 0;
                this.left = left;
                this.right = right;
            }
        }
    
        private int height(Node<T> t) {
            return t == null ? -1 : t.height;
        }
    
        private Node<T> root ; 
    
        public void add(T value , Integer position){
            root = add( value , position, root );
        }
    
        private Node<T> add(T value , Integer position, Node<T> node){
            if(node == null){
                return new Node<T>(value,position , null ,null);
            }
    
            int comparaResult = value.compareTo(node.value);
    
            if(comparaResult > 0)
                node.right = add(value , position , node.right);
            else if (comparaResult < 0)
                node.left = add(value , position , node.left);
            else 
                System.out.println("as same a value");
    
            node.height = Math.max(height(node.left), height(node.right)) + 1;
            return node;
    
        }
    
        public Integer search(Node<T> node , T value){
            if(node == null)
                return -1 ; 
            int comparaResult = value.compareTo(node.value);
            if(comparaResult == 0)
                return node.position;
            else if(comparaResult > 0)
                return search(node.right, value);
            else if(comparaResult < 0)
                return search(node.left, value);
            else
                return -1;
        }
    
    
    
        private void preorder(Node<T> node){
            if(null == node)
                return ; 
            System.out.print(node.value);
            preorder(node.left);
            preorder(node.right);
        }
    
    
        private void midorder(Node<T> node){
            if(null == node)
                return ; 
            midorder(node.left);
            System.out.print(node.value);
            midorder(node.right);
        }
    
    
        private void postorder(Node<T> node){
            if(null == node)
                return ; 
            postorder(node.left);
            postorder(node.right);
            System.out.print(node.value);
        }
    
    
        public static void main(String[] args){
            BST<Integer> bst = new BST<Integer>();
              int[] array = {
       0,1,5,6,7,2,3,4,8,9};
            for(int i=0;i<array.length;i++)
                bst.add(array[i],i);// 
            System.out.println(bst.height(bst.root));
            System.out.println(bst.search(bst.root, 8));
            System.out.println(bst.search(bst.root, 0));
            System.out.println(bst.search(bst.root, 22));
    
            bst.preorder(bst.root);
            System.out.println();
            bst.midorder(bst.root);
            System.out.println();
            bst.postorder(bst.root);
        }
    }