Dsa Using Java 简明教程

DSA using Java - Tree

Overview

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

Tree represents nodes connected by edges. We’ll going to discuss binary tree or binary search tree specifically.

二叉树是一个特殊的数据结构，用于数据存储。二叉树有一个特殊条件，即每个节点最多可以有两个子节点。二叉树同时具有有序数组和链表的优点，如搜索像在已排序数组中一样快速，插入或删除操作像在链表中一样快。

Binary Tree is a special datastructure used for data storage purposes. A binary tree has a special condition that each node can have two children at maximum. A binary tree have benefits of both an ordered array and a linked list as search is as quick as in sorted array and insertion or deletion operation are as fast as in linked list.

Terms

以下是关于树的一些重要术语。

Following are important terms with respect to tree.

Path − Path refers to sequence of nodes along the edges of a tree.
Root − Node at the top of the tree is called root. There is only one root per tree and one path from root node to any node.
Parent − Any node except root node has one edge upward to a node called parent.
Child − Node below a given node connected by its edge downward is called its child node.
Leaf − Node which does not have any child node is called leaf node.
Subtree − Subtree represents descendents of a node.
Visiting − Visiting refers to checking value of a node when control is on the node.
Traversing − Traversing means passing through nodes in a specific order.
Levels − Level of a node represents the generation of a node. If root node is at level 0, then its next child node is at level 1, its grandchild is at level 2 and so on.
keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

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

Binary Search tree exibits a special behaviour. A node’s left child must have value less than its parent’s value and node’s right child must have value greater than it’s parent value.

Binary Search Tree Representation

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

We’re going to implement tree using node object and connecting them through references.

Basic Operations

下面是一些树的基本基本操作。

Following are basic primary operations of a tree which are following.

Search − search an element in a tree.
Insert − insert an element in a tree.
Preorder Traversal − traverse a tree in a preorder manner.
Inorder Traversal − traverse a tree in an inorder manner.
Postorder Traversal − traverse a tree in a postorder manner.

Node

定义一个节点，它具有一些数据、针对其左侧和右侧子节点的引用。

Define a node having some data, references to its left and right child nodes.

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

   public Node(){}

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

Search Operation

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

Whenever an element is to be search. Start search from root node then if data is less than key value, search element in left subtree otherwise search element in right subtree. Follow the same algorithm for each node.

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 + " ");
         //go to left tree
         if(current.data > data){
            current = current.leftChild;
         }//else go to right tree
         else{
            current = current.rightChild;
         }
         //not found
         if(current == null){
            return null;
         }
      }
   return current;
}

Insert Operation

如果某一元素要插入。首先，找到它适当的位置。从根节点开始搜索，此时，如果数据小于键值，在左子树中查找空位置，并插入数据。否则，在右子树中查找空位置，并插入数据。

Whenever an element is to be inserted. First locate its proper location. Start search from root node then if data is less than key value, search empty location in left subtree and insert the data. Otherwise search empty location in right subtree and insert the data.

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

   //if tree is empty
   if(root == null){
      root = tempNode;
   }else{
      Node current = root;
      Node parent = null;

      while(true){
         parent = current;
         //go to left of the tree
         if(data < parent.data){
            current = current.leftChild;
            //insert to the left
            if(current == null){
               parent.leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else{
            current = current.rightChild;
            //insert to the right
            if(current == null){
               parent.rightChild = tempNode;
               return;
            }
         }
      }
   }
}

Preorder Traversal

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

It is a simple three step process.

visit root node
traverse left subtree
traverse right subtree

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

Inorder Traversal

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

It is a simple three step process.

traverse left subtree
visit root node
traverse right subtree

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

Postorder Traversal

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

It is a simple three step process.

traverse left subtree
traverse right subtree
visit root node

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

Tree Implementation

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 + " ");
            //go to left tree
            if(current.data > data){
               current = current.leftChild;
            }//else go to right tree
            else{
               current = current.rightChild;
            }
            //not found
            if(current == null){
               return null;
            }
         }
      return current;
   }

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

      //if tree is empty
      if(root == null){
         root = tempNode;
     }else{
         Node current = root;
         Node parent = null;

         while(true){
            parent = current;
            //go to left of the tree
            if(data < parent.data){
               current = current.leftChild;
               //insert to the left
               if(current == null){
                  parent.leftChild = tempNode;
                  return;
               }
            }//go to right of the tree
            else{
               current = current.rightChild;
               //insert to the right
               if(current == null){
                  parent.rightChild = tempNode;
                  return;
               }
            }
         }
      }
   }

   public void traverse(int traversalType){
      switch(traversalType){
         case 1:
            System.out.print("\nPreorder traversal: ");
            preOrder(root);
            break;
         case 2:
            System.out.print("\nInorder traversal: ");
            inOrder(root);
            break;
         case 3:
            System.out.print("\nPostorder 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 + " ");
      }
   }
}

Demo Program

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);
   }
}

如果我们编译并运行上述程序，它将生成以下结果 -

If we compile and run the above program then it would produce following result −

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