二分搜索树的深度优先遍历和广度优先遍历
2018-06-18 01:06:39来源:未知 阅读 ()
二分搜索树的特点
二分搜索树首先是一个二叉树,其次其必须满足的条件是:每个节点的键值必须大于其左子节点,每个节点的键值必须小于其右子节点,这样以左右孩子为根的子树仍为二分搜索树,需要注意的是,二分搜索树不一定是一颗完全二叉树。
深度优先遍历
深度优先遍历的基本思想:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。深度优先遍历的非递归的通用做法是采用栈。要特别注意的是,二分搜索树的深度优先遍历比较特殊,可以细分为前序遍历、中序遍历、后序遍历。
广度优先遍历
深度优先遍历的基本思想:从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。广度优先遍历的非递归的通用做法是采用队列。
例如,对于上面的这个二分搜索树,其层序遍历(广度优先遍历)结果是: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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
- LeetCode 面试题33. 二叉搜索树的后序遍历序列 2020-05-22
- 突击Java面试-分布式搜索引擎的架构原理 2020-05-19
- LeetCode 面试题54. 二叉搜索树的第k大节点 2020-05-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash