
- Java 数据结构与算法 教程
- Java 数据结构与算法 - 首页
- Java 数据结构与算法 - 概述
- Java 数据结构与算法 - 环境设置
- Java 数据结构与算法 - 算法
- Java 数据结构与算法 - 数据结构
- Java 数据结构与算法 - 数组
- Java 数据结构与算法 - 链表
- Java 数据结构与算法 - 双向链表
- Java 数据结构与算法 - 循环链表
- Java 数据结构与算法 - 栈
- 数据结构与算法 - 表达式解析
- Java 数据结构与算法 - 队列
- Java 数据结构与算法 - 优先队列
- Java 数据结构与算法 - 树
- Java 数据结构与算法 - 哈希表
- Java 数据结构与算法 - 堆
- Java 数据结构与算法 - 图
- Java 数据结构与算法 - 搜索技术
- Java 数据结构与算法 - 排序技术
- Java 数据结构与算法 - 递归
- Java 数据结构与算法 有用资源
- Java 数据结构与算法 - 快速指南
- Java 数据结构与算法 - 有用资源
- Java 数据结构与算法 - 讨论
Java 数据结构与算法 - 树
概述
树由节点和边连接而成。我们将专门讨论二叉树或二叉搜索树。
二叉树是一种用于数据存储的特殊数据结构。二叉树有一个特殊的条件,即每个节点最多可以有两个子节点。二叉树兼具有序数组和链表的优点,搜索速度与有序数组一样快,插入或删除操作速度与链表一样快。
术语
以下是关于树的一些重要术语。
路径 - 路径指的是树中沿边的一系列节点。
根 - 树顶部的节点称为根。每棵树只有一个根,并且从根节点到任何节点都只有一条路径。
父节点 - 除根节点外的任何节点都有一条向上连接到称为父节点的节点的边。
子节点 - 在给定节点下方由其向下连接的边连接的节点称为其子节点。
叶子节点 - 没有子节点的节点称为叶子节点。
子树 - 子树表示节点的后代。
访问 - 访问是指当控制权在节点上时检查节点的值。
遍历 - 遍历是指按特定顺序通过节点。
层级 - 节点的层级表示节点的代数。如果根节点在第 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 + " "); //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; } } } } }
先序遍历
这是一个简单的三步过程。
访问根节点
遍历左子树
遍历右子树
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 + " "); //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 + " "); } } }
演示程序
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