5.18. Depth-first traversal of binary search tree

发布时间 ： 2025-10-25 13:35:40 UTC      

Page Views: 25 views

Binary search tree traversal is divided into two categories, depth-first traversal and sequence traversal.

There are three types of depth-first traversal: pre-order traversal (preorder tree walk), mid-order traversal (inorder tree walk), and post-order traversal (postorder tree walk). They are:

  • 1、前序遍历： First visit the current node, and then recursively access the left and right subtrees.

  • 2、中序遍历 First recursively visit the left subtree, then visit itself, and then recursively visit the right subtree.

  • 3、后序遍历 Recursively visit the left and right subtrees first, and then access your own nodes

The result of preorder traversal is shown as follows:

image0

Corresponding code example:

...
// 对以node为根的二叉搜索树进行前序遍历, 递归算法
private void preOrder(Node node){
    if( node != null ){
        System.out.println(node.key);
        preOrder(node.left);
        preOrder(node.right);
    }
}
...

The traversal result in the middle order is shown as follows:

image1

Corresponding code example:

...
// 对以node为根的二叉搜索树进行中序遍历, 递归算法
private void inOrder(Node node){
    if( node != null ){
        inOrder(node.left);
        System.out.println(node.key);
        inOrder(node.right);
    }
}
...

The result of traversing in the following order is shown:

image2

Corresponding code example:

...
// 对以node为根的二叉搜索树进行后序遍历, 递归算法
private void postOrder(Node node){
    if( node != null ){
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.key);
    }
}
...

5.18.1. Java instance code

源码包下载： Download

Src/runoob/binary/Traverse.java file code: 

package runoob.binary;
/*\*
 \* 优先遍历
 */
public class Traverse, Value>  {
    // 树中的节点为私有的类, 外界不需要了解二分搜索树节点的具体实现
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;
        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
    private Node root;  // 根节点
    private int count;  // 树种的节点个数
    // 构造函数, 默认构造一棵空二分搜索树
    public Traverse() {
        root = null;
        count = 0;
    }
    // 返回二分搜索树的节点个数
    public int size() {
        return count;
    }
    // 返回二分搜索树是否为空
    public boolean isEmpty() {
        return count == 0;
    }
    // 向二分搜索树中插入一个新的(key, value)数据对
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }
    // 查看二分搜索树中是否存在键key
    public boolean contain(Key key){
        return contain(root, key);
    }
    // 在二分搜索树中搜索键key所对应的值。如果这个值不存在, 则返回null
    public Value search(Key key){
        return search( root , key );
    }
    // 二分搜索树的前序遍历
    public void preOrder(){
        preOrder(root);
    }
    // 二分搜索树的中序遍历
    public void inOrder(){
        inOrder(root);
    }
    // 二分搜索树的后序遍历
    public void postOrder(){
        postOrder(root);
    }
    //*******************\*
    //\* 二分搜索树的辅助函数
    //*******************\*
    // 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法
    // 返回插入新节点后的二分搜索树的根
    private Node insert(Node node, Key key, Value value){
        if( node == null ){
            count ++;
            return new Node(key, value);
        }
        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);
        return node;
    }
    // 查看以node为根的二分搜索树中是否包含键值为key的节点, 使用递归算法
    private boolean contain(Node node, Key key){
        if( node == null )
            return false;
        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }
    // 在以node为根的二分搜索树中查找key所对应的value, 递归算法
    // 若value不存在, 则返回NULL
    private Value search(Node node, Key key){
        if( node == null )
            return null;
        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }
    // 对以node为根的二叉搜索树进行前序遍历, 递归算法
    private void preOrder(Node node){
        if( node != null ){
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    // 对以node为根的二叉搜索树进行中序遍历, 递归算法
    private void inOrder(Node node){
        if( node != null ){
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }
    // 对以node为根的二叉搜索树进行后序遍历, 递归算法
    private void postOrder(Node node){
        if( node != null ){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }
}
      
                    
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.18. Depth-first traversal of binary search tree 
                        

                    

                

            
        
        

            

    
        

            

                

                    
                        
                        
                            
Principles and Applications of WebGIS 

                        
                        
                             37
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Web框架 

                        
                        
                             942
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
WEB基础 

                        
                        
                             287
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Principles, Technologies, and Methods of Geographic Information Systems 

                        
                        
                             102
                        
                    
                    
                        

                            
 
 
 In recent years, Geographic Information Systems (GIS) have undergone rapid development in both theoretical and practical dimensions. GIS has been widely applied for modeling and decision-making support across various fields such as urban management, regional planning, and environmental remediation, establishing geographic information as a vital component of the information era. The introduction of the “Digital Earth” concept has further accelerated the advancement of GIS, which serves as its technical foundation. Concurrently, scholars have been dedicated to theoretical research in areas like spatial cognition, spatial data uncertainty, and the formalization of spatial relationships. This reflects the dual nature of GIS as both an applied technology and an academic discipline, with the two aspects forming a mutually reinforcing cycle of progress.