二分搜索树的特点

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

 

深度优先遍历

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

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

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

　　

 

版权声明：本文为Demrystv原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Demrystv/p/9043356.html