二分搜索树的深度优先遍历和广度优先遍历

2018-06-18 01:06:39来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

二分搜索树的特点

  二分搜索树首先是一个二叉树,其次其必须满足的条件是:每个节点的键值必须大于其左子节点,每个节点的键值必须小于其右子节点,这样以左右孩子为根的子树仍为二分搜索树,需要注意的是,二分搜索树不一定是一颗完全二叉树。

 

深度优先遍历

  深度优先遍历的基本思想:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。深度优先遍历的非递归的通用做法是采用栈。要特别注意的是,二分搜索树的深度优先遍历比较特殊,可以细分为前序遍历、中序遍历、后序遍历。

  前序遍历:先访问当前节点,再依次递归访问左右子树 ,访问到前面节点才继续
  中序遍历:先递归访问左子树,再访问自身,再递归访问右子树,访问到中间节点才继续 
  后序遍历:先递归访问左右子树,再访问自身节点,访问到后面节点才继续
  例如,对于下面的这个二分搜索树,其前序遍历结果是:28  16  13  22  30  29  42,其中序遍历结果是:13  16  22  28  29  30  42,其后序遍历结果是:13  22  16  29  42  30  28。

 二分搜索树

 

广度优先遍历

  深度优先遍历的基本思想:从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。广度优先遍历的非递归的通用做法是采用队列。

  例如,对于上面的这个二分搜索树,其层序遍历(广度优先遍历)结果是:28 16 30 13 22 29 42。

 

Java代码实现深度优先遍历和广度优先遍历

  下面采用Java语言来构建这个二分搜索树,并且实现前序遍历、中序遍历、后序遍历三种不同方式的深度优先遍历和广度优先遍历(层序遍历)。

  1 package com.allSorts;
  2 
  3 
  4 import java.util.LinkedList;
  5 import java.util.Queue;
  6 
  7 /**
  8  * Created by Demrystv.
  9  */
 10 public class BSTTraverseTest {
 11 
 12     public static void main(String[] args) {
 13         BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
 14         tree.insertNode(28);
 15         tree.insertNode(16);
 16         tree.insertNode(13);
 17         tree.insertNode(22);
 18         tree.insertNode(30);
 19         tree.insertNode(29);
 20         tree.insertNode(42);
 21         System.out.print("前序遍历(递归):");
 22         tree.preOrderTraverse(tree.getRoot());
 23         System.out.println();
 24         System.out.print("中序遍历(递归):");
 25         tree.inOrderTraverse(tree.getRoot());
 26         System.out.println();
 27         System.out.print("后序遍历(递归):");
 28         tree.postOrderTraverse(tree.getRoot());
 29         System.out.println();
 30         System.out.print("前序遍历(非递归):");
 31         tree.preOrderTraverseNoRecursion(tree.getRoot());
 32         System.out.println();
 33         System.out.print("中序遍历(非递归):");
 34         tree.inOrderTraverseNoRecursion(tree.getRoot());
 35         System.out.println();
 36         System.out.print("后序遍历(非递归):");
 37         tree.postOrderTraverseNoRecursion(tree.getRoot());
 38         System.out.println();
 39         System.out.print("广度优先遍历:");
 40         tree.breadthFirstTraverse(tree.getRoot());
 41     }
 42 
 43 
 44     /**
 45      * 结点
 46      */
 47     public static class Node<E extends Comparable<E>> {
 48         E value;
 49         Node<E> left;
 50         Node<E> right;
 51         Node(E value) {
 52             this.value = value;
 53             left = null;
 54             right = null;
 55         }
 56     }
 57 
 58     /**
 59      * 使用一个前序遍历构建一棵二分搜索树
 60      */
 61     public static class BinarySearchTree<E extends Comparable<E>> {
 62         private Node<E> root;
 63         BinarySearchTree() {
 64             root = null;
 65         }
 66         public void insertNode(E value) {
 67             if (root == null) {
 68                 root = new Node<E>(value);
 69                 return;
 70             }
 71             Node<E> currentNode = root;
 72             while (true) {
 73                 if (value.compareTo(currentNode.value) > 0) {
 74                     if (currentNode.right == null) {
 75                         currentNode.right = new Node<E>(value);
 76                         break;
 77                     }
 78                     currentNode = currentNode.right;
 79                 } else {
 80                     if (currentNode.left == null) {
 81                         currentNode.left = new Node<E>(value);
 82                         break;
 83                     }
 84                     currentNode = currentNode.left;
 85                 }
 86             }
 87         }
 88         public Node<E> getRoot(){
 89             return root;
 90         }
 91         /**
 92          * 前序遍历二分搜索树(递归)
 93          * @param node
 94          */
 95         public void preOrderTraverse(Node<E> node) {
 96             System.out.print(node.value + " ");
 97             if (node.left != null)
 98                 preOrderTraverse(node.left);
 99             if (node.right != null)
100                 preOrderTraverse(node.right);
101         }
102         /**
103          * 中序遍历二分搜索树(递归)
104          * @param node
105          */
106         public void inOrderTraverse(Node<E> node) {
107             if (node.left != null)
108                 inOrderTraverse(node.left);
109             System.out.print(node.value + " ");
110             if (node.right != null)
111                 inOrderTraverse(node.right);
112         }
113         /**
114          * 后序遍历二分搜索树(递归)
115          * @param node
116          */
117         public void postOrderTraverse(Node<E> node) {
118             if (node.left != null)
119                 postOrderTraverse(node.left);
120             if (node.right != null)
121                 postOrderTraverse(node.right);
122             System.out.print(node.value + " ");
123         }
124         /**
125          * 前序遍历二分搜索树(非递归),用的是栈
126          * @param root
127          */
128         public void preOrderTraverseNoRecursion(Node<E> root) {
129             LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
130             Node<E> currentNode = null;
131             stack.push(root);
132             while (!stack.isEmpty()) {
133                 currentNode = stack.pop();
134                 System.out.print(currentNode.value + " ");
135                 if (currentNode.right != null)
136                     stack.push(currentNode.right);
137                 if (currentNode.left != null)
138                     stack.push(currentNode.left);
139             }
140         }
141         /**
142          * 中序遍历二分搜索树(非递归),用的是栈
143          * @param root
144          */
145         public void inOrderTraverseNoRecursion(Node<E> root) {
146             LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
147             Node<E> currentNode = root;
148             while (currentNode != null || !stack.isEmpty()) {
149                 // 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
150                 while (currentNode != null) {
151                     stack.push(currentNode);
152                     currentNode = currentNode.left;
153                 }
154                 currentNode = stack.pop();
155                 System.out.print(currentNode.value + " ");
156                 currentNode = currentNode.right;
157             }
158         }
159         /**
160          * 后序遍历二分搜索树(非递归),用的是栈
161          * @param root
162          */
163         public void postOrderTraverseNoRecursion(Node<E> root) {
164             LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
165             Node<E> currentNode = root;
166             Node<E> rightNode = null;
167             while (currentNode != null || !stack.isEmpty()) {
168                 // 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
169                 while (currentNode != null) {
170                     stack.push(currentNode);
171                     currentNode = currentNode.left;
172                 }
173                 currentNode = stack.pop();
174                 // 当前结点没有右结点或上一个结点(已经输出的结点)是当前结点的右结点,则输出当前结点
175                 while (currentNode.right == null || currentNode.right == rightNode) {
176                     System.out.print(currentNode.value + " ");
177                     rightNode = currentNode;
178                     if (stack.isEmpty()) {
179                         return; //root以输出,则遍历结束
180                     }
181                     currentNode = stack.pop();
182                 }
183                 stack.push(currentNode); //还有右结点没有遍历
184                 currentNode = currentNode.right;
185             }
186         }
187         /**
188          * 广度优先遍历二分搜索树,又称层次遍历,用的是队列
189          * @param root
190          */
191         public void breadthFirstTraverse(Node<E> root) {
192             Queue<Node<E>> queue = new LinkedList<Node<E>>();
193             Node<E> currentNode = null;
194             queue.offer(root);
195             while (!queue.isEmpty()) {
196                 currentNode = queue.poll();
197                 System.out.print(currentNode.value + " ");
198                 if (currentNode.left != null)
199                     queue.offer(currentNode.left);
200                 if (currentNode.right != null)
201                     queue.offer(currentNode.right);
202             }
203         }
204     }
205 }

  运行结果如下,与前面理论分析完全对应。

  

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:使用apicloud开发app应用安卓和ios上出现中文乱码解决方法

下一篇:SpringMVC框架学习笔记(二)