Dsa Using Java 简明教程
DSA using Java - Tree
Overview
树表示通过边连接起来的多个节点。我们将专门讨论二叉树或二叉搜索树。
二叉树是一个特殊的数据结构，用于数据存储。二叉树有一个特殊条件，即每个节点最多可以有两个子节点。二叉树同时具有有序数组和链表的优点，如搜索像在已排序数组中一样快速，插入或删除操作像在链表中一样快。
Terms
以下是关于树的一些重要术语。
-
Path − 路径是指沿着树边缘的一系列节点。
-
Root − 树顶部的节点称为根节点。每个树只有一个根节点，并且从根节点到任何节点只有一条路径。
-
Parent − 除了根节点之外的任何节点都有一条向上的边连接到一个称为父节点的节点。
-
Child − 通过向下的边与给定节点相连接的下方节点称为其子节点。
-
Leaf − 没有子节点的节点称为叶节点。
-
Subtree − 子树表示节点的后代。
-
Visiting − 访问是指在控制权在节点上的时候检查节点的值。
-
Traversing − 遍历指按照特定顺序经过节点。
-
Levels − 节点的等级表示节点的代。如果根节点在第 0 级，那么它的下一个子节点在第 1 级，它的孙子节点在第 2 级，以此类推。
-
keys − 键表示节点的值，基于此值针对节点执行搜索操作。
二叉搜索树表现出一种特殊的行为。节点的左子节点的值必须小于其父节点的值，节点的右子节点的值必须大于其父节点的值。
Basic Operations
下面是一些树的基本基本操作。
-
Search − 在树中搜索一个元素。
-
Insert − 在树中插入一个元素。
-
Preorder Traversal - 以先序方式遍历树。
-
Inorder Traversal - 以中序方式遍历树。
-
Postorder Traversal - 以后序方式遍历树。
Node
定义一个节点，它具有一些数据、针对其左侧和右侧子节点的引用。
public class Node {
public int data;
public Node leftChild;
public Node rightChild;
public Node(){}
public void display(){
System.out.print("("+data+ ")");
}
}Search Operation
如果某一元素搜索。从根节点开始搜索，此时，如果数据小于键值，在左子树中搜索元素，否则，在右子树中搜索元素。遵循相同的算法针对每个节点。
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
如果某一元素要插入。首先，找到它适当的位置。从根节点开始搜索，此时，如果数据小于键值，在左子树中查找空位置，并插入数据。否则，在右子树中查找空位置，并插入数据。
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
这是一个简单的三步流程。
-
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
这是一个简单的三步流程。
-
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
这是一个简单的三步流程。
-
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);
}
}如果我们编译并运行上述程序，它将生成以下结果 -
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