使用 Java 的 DSA - 树

概述

树表示通过边连接的节点。我们将专门讨论二叉树或二叉搜索树。

二叉树是一种用于数据存储目的的特殊数据结构。二叉树有一个特殊条件，即每个节点最多可以有两个子节点。二叉树兼具有序数组和链表的优点，因为搜索速度与排序数组一样快，插入或删除操作与链表一样快。

术语

以下是与树有关的重要术语。

路径 −路径是指沿着树的边缘的节点序列。
根 − 树顶部的节点称为根。每棵树只有一个根，从根节点到任何节点只有一条路径。
父节点 − 除根节点外的任何节点都有一条向上的边指向称为父节点的节点。
子节点 − 通过向下的边连接的给定节点下方的节点称为其子节点。
叶节点 − 没有任何子节点的节点称为叶节点。
子树 − 子树表示节点的后代。
访问 −访问是指在控制节点上时检查节点的值。
遍历 − 遍历意味着按特定顺序穿过节点。
级别 − 节点的级别表示节点的代数。如果根节点在级别 0，则其下一个子节点在级别 1，其孙节点在级别 2，依此类推。
键 − 键表示节点的值，基于该值对节点执行搜索操作。

二叉搜索树表现出一种特殊的行为。节点的左子节点的值必须小于其父节点的值，而节点的右子节点的值必须大于其父节点的值。

二叉搜索树表示

我们将使用节点对象实现树并通过引用连接它们。

基本操作

以下是树的基本主要操作。

搜索 − 在树中搜索元素。
插入 − 在树中插入元素。
前序遍历 − 以前序方式遍历树。
中序遍历 −以中序方式遍历树。
后序遍历 − 以后序方式遍历树。

节点

定义一个节点，其中包含一些数据、对其左子节点和右子节点的引用。

public class Node {
   public int data;
   public Node leftChild;
   public Node rightChild;

   public Node(){}

   public void display(){
      System.out.print("("+data+ ")");
   }
}

搜索操作

每当要搜索元素时。从根节点开始搜索，然后如果数据小于键值，则在左子树中搜索元素，否则在右子树中搜索元素。对每个节点遵循相同的算法。

public Node search(int data){
   Node current = root;
   System.out.print("Visiting elements: ");
   while(current.data != data){
      if(current != null)
         System.out.print(current.data + " "); 
         //转到左边的树
         if(current.data > data){
            current = current.leftChild;
         }//否则转到右树
         else{                
            current = current.rightChild;
         }
         //未找到
         if(current == null){
            return null;
         }
      }
   return current;
}

插入操作

每当要插入一个元素时。首先找到其正确的位置。从根节点开始搜索，然后如果数据小于键值，则在左子树中搜索空位置并插入数据。否则在右子树中搜索空位置并插入数据。

public void insert(int data){
   Node tempNode = new Node();
   tempNode.data = data;

   //如果树为空
   if(root == null){
      root = tempNode;
   }else{
      Node current = root;
      Node parent = null;

      while(true){                
         parent = current;
         //转到树的左边
         if(data < parent.data){
            current = current.leftChild;                
            //插入到左侧
            if(current == null){
               parent.leftChild = tempNode;
               return;
            }
         }// 转到树的右边
         else{
            current = current.rightChild;
            //插入到右侧
            if(current == null){
               parent.rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

前序遍历

这是一个简单的三步过程。

访问根节点
遍历左子树
遍历右子树

private void preOrder(Node root){
   if(root!=null){
      System.out.print(root.data + " ");
      preOrder(root.leftChild);
      preOrder(root.rightChild);
   }
}

中序遍历

这是一个简单的三步过程。

遍历左子树
访问根节点
遍历右子树

private void inOrder(Node root){
    if(root!=null){
    inOrder(root.leftChild);
    System.out.print(root.data + " ");
    inOrder(root.rightChild);
    }
}

后序遍历

这是一个简单的三步过程。

遍历左子树
遍历右子树
访问根节点

private void postOrder(Node root){
   if(root!=null){            
      postOrder(root.leftChild);
      postOrder(root.rightChild);
      System.out.print(root.data + " ");
   }
}

树的实现

Node.java

package com.tutorialspoint.datastructure;

public class Node {
   public int data;
   public Node leftChild;
   public Node rightChild;

   public Node(){}

   public void display(){
      System.out.print("("+data+ ")");
   }
}

Tree.java

package com.tutorialspoint.datastructure;

public class Tree {
   private Node root;

   public Tree(){
      root = null;
   }
   
   public Node search(int data){
      Node current = root;
      System.out.print("Visiting elements: ");
      while(current.data != data){
         if(current != null)
            System.out.print(current.data + " "); 
            //转到左边的树
            if(current.data > data){
               current = current.leftChild;
            }//否则转到右树
            else{                
               current = current.rightChild;
            }
            //未找到
            if(current == null){
               return null;
            }
         }
      return current;
   }

   public void insert(int data){
      Node tempNode = new Node();
      tempNode.data = data;

      //如果树为空
      if(root == null){
         root = tempNode;
     }else{
         Node current = root;
         Node parent = null;

         while(true){                
            parent = current;
            //转到树的左边
            if(data < parent.data){
               current = current.leftChild;                
               //插入到左侧
               if(current == null){
                  parent.leftChild = tempNode;
                  return;
               }
            }// 转到树的右边
            else{
               current = current.rightChild;
               //插入到右侧
               if(current == null){
                  parent.rightChild = tempNode;
                  return;
               }
            }
         }            
      }
   }    

   public void traverse(int traversalType){
      switch(traversalType){
         case 1:
            System.out.print("
Preorder traversal: ");
            preOrder(root);
            break;
         case 2:
            System.out.print("
Inorder traversal: ");
            inOrder(root);
            break;
         case 3:
            System.out.print("
Postorder traversal: ");
            postOrder(root);
            break;
         }            
   }   

   private void preOrder(Node root){
      if(root!=null){
         System.out.print(root.data + " ");
         preOrder(root.leftChild);
         preOrder(root.rightChild);
      }
   }

   private void inOrder(Node root){
      if(root!=null){
         inOrder(root.leftChild);
         System.out.print(root.data + " ");            
         inOrder(root.rightChild);
      }
   }

   private void postOrder(Node root){
      if(root!=null){            
         postOrder(root.leftChild);
         postOrder(root.rightChild);
         System.out.print(root.data + " ");
      }
   }
}

演示程序

TreeDemo.java

package com.tutorialspoint.datastructure;

public class TreeDemo {
   public static void main(String[] args){
      Tree tree = new Tree();

      /*                     11               //Level 0
      */
      tree.insert(11);
      /*                     11               //Level 0
      *                      |
      *                      |---20           //Level 1
      */
      tree.insert(20);
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      */
      tree.insert(3);        
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      *                           |
      *                           |--42       //Level 2
      */
      tree.insert(42);
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      *                           |
      *                           |--42       //Level 2
      *                               |
      *                               |--54   //Level 3
      */
      tree.insert(54);
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      *                           |
      *                       16--|--42       //Level 2
      *                               |
      *                               |--54   //Level 3
      */
      tree.insert(16);
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      *                           |
      *                       16--|--42       //Level 2
      *                               |
      *                           32--|--54   //Level 3
      */
      tree.insert(32);
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      *                  |        |
      *                  |--9 16--|--42       //Level 2
      *                               |
      *                           32--|--54   //Level 3
      */
      tree.insert(9);
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      *                  |        |
      *                  |--9 16--|--42       //Level 2
      *                     |         |
      *                  4--|     32--|--54   //Level 3
      */
      tree.insert(4);
      /*                     11               //Level 0
      *                      |
      *                  3---|---20           //Level 1
      *                  |        |
      *                  |--9 16--|--42       //Level 2
      *                     |         |
      *                  4--|--10 32--|--54   //Level 3
      */
      tree.insert(10);
      Node node = tree.search(32);
      if(node!=null){
         System.out.print("Element found.");
         node.display();
         System.out.println();
      }else{
         System.out.println("Element not found.");
      }

      Node node1 = tree.search(2);
      if(node1!=null){
         System.out.println("Element found.");
         node1.display();
         System.out.println();
      }else{
         System.out.println("Element not found.");
      }        

      //pre-order traversal
      //root, left ,right
      tree.traverse(1);
      //in-order traversal
      //left, root ,right
      tree.traverse(2);
      //post order traversal
      //left, right, root
      tree.traverse(3);       
   }
}

如果我们编译并运行上述程序，则会产生以下结果 −

Visiting elements: 11 20 42 Element found.(32)
Visiting elements: 11 3 Element not found.

Preorder traversal: 11 3 9 4 10 20 16 42 32 54 
Inorder traversal: 3 4 9 10 11 16 20 32 42 54 
Postorder traversal: 4 10 9 3 16 32 54 42 20 11

使用 Java 的 DSA 教程

有用资源

使用 Java 的 DSA - 树

概述

术语

二叉搜索树表示

基本操作

节点

搜索操作

插入操作

前序遍历

中序遍历

后序遍历

树的实现

演示程序

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！