找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

二叉树算法,你懂吗?

admin 2019-11-25 15:54 137人围观 C++相关

点击蓝色“码出高效面试的程序媛”关注我,

了解更多技术流行面试题



二叉树,搜索二叉树,是算法面试的必面题。聊聊面试点:

一、树 & 二叉树


树的组成为节点和边,节点用来储存元素。节点组成为根节点、父节点和子节点。

如图:树深 length 为 4;根节点的值为 5 ;父子节点关系:值为 8 和 值为 3 的节点



理解了树,那什么是二叉树?

二叉树 (Binary Tree),二叉是分叉的意思,就是用边区分。节点最多有两个子节点,分别为左子节点和右子节点。连接节点的就是边,所以节点最多会有三条边。二叉树的场景很多,比如用来表示算术表达式等等。

如图:值为 1 或者 8 的节点是左节点;值为 2 或 3 的节点是右节点;



二、二叉搜索树 BST


上面理解了二叉树,那么搜索二叉树就好理解了。搜索二叉树为了搜索而设计,要求也是将无序存储变成有序。即每个节点的值要比左子树的值大,比右子树的值小。

如图:



Java 实现代码如下:

  1. publicclassBinarySearchTree{

  2. /**

  3. * 根节点

  4. */

  5. publicstaticTreeNode root;


  6. publicBinarySearchTree(){

  7. this.root =null;

  8. }


  9. /**

  10. * 查找

  11. */

  12. publicTreeNode search (int key){

  13. TreeNode current = root;

  14. while(current !=null

  15. && key != current.value){

  16. if(key < current.value )

  17. current = current.left;

  18. else

  19. current = current.right;

  20. }

  21. return current;

  22. }


  23. /**

  24. * 插入

  25. */

  26. publicTreeNode insert (int key){

  27. // 新增节点

  28. TreeNode newNode =newTreeNode(key);

  29. // 当前节点

  30. TreeNode current = root;

  31. // 上个节点

  32. TreeNode parent =null;

  33. // 如果根节点为空

  34. if(current ==null){

  35. root = newNode;

  36. return newNode;

  37. }

  38. while(true){

  39. parent = current;

  40. if(key < current.value){

  41. current = current.left;

  42. if(current ==null){

  43. parent.left = newNode;

  44. return newNode;

  45. }

  46. }else{

  47. current = current.right;

  48. if(current ==null){

  49. parent.right = newNode;

  50. return newNode;

  51. }

  52. }

  53. }

  54. }


  55. /**

  56. * 删除节点

  57. */

  58. publicTreeNodedelete(int key){

  59. TreeNode parent = root;

  60. TreeNode current = root;

  61. boolean isLeftChild =false;

  62. // 找到删除节点 及 是否在左子树

  63. while(current.value != key){

  64. parent = current;

  65. if(current.value > key){

  66. isLeftChild =true;

  67. current = current.left;

  68. }else{

  69. isLeftChild =false;

  70. current = current.right;

  71. }


  72. if(current ==null){

  73. return current;

  74. }

  75. }


  76. // 如果删除节点左节点为空 , 右节点也为空

  77. if(current.left ==null&& current.right ==null){

  78. if(current == root){

  79. root =null;

  80. }

  81. // 在左子树

  82. if(isLeftChild ==true){

  83. parent.left =null;

  84. }else{

  85. parent.right =null;

  86. }

  87. }

  88. // 如果删除节点只有一个子节点 右节点 或者 左节点

  89. elseif(current.right ==null){

  90. if(current == root){

  91. root = current.left;

  92. }elseif(isLeftChild){

  93. parent.left = current.left;

  94. }else{

  95. parent.right = current.left;

  96. }


  97. }

  98. elseif(current.left ==null){

  99. if(current == root){

  100. root = current.right;

  101. }elseif(isLeftChild){

  102. parent.left = current.right;

  103. }else{

  104. parent.right = current.right;

  105. }

  106. }

  107. // 如果删除节点左右子节点都不为空

  108. elseif(current.left !=null&& current.right !=null){

  109. // 找到删除节点的后继者

  110. TreeNode successor = getDeleteSuccessor(current);

  111. if(current == root){

  112. root = successor;

  113. }elseif(isLeftChild){

  114. parent.left = successor;

  115. }else{

  116. parent.right = successor;

  117. }

  118. successor.left = current.left;

  119. }

  120. return current;

  121. }


  122. /**

  123. * 获取删除节点的后继者

  124. * 删除节点的后继者是在其右节点树种最小的节点

  125. */

  126. publicTreeNode getDeleteSuccessor(TreeNode deleteNode){

  127. // 后继者

  128. TreeNode successor =null;

  129. TreeNode successorParent =null;

  130. TreeNode current = deleteNode.right;


  131. while(current !=null){

  132. successorParent = successor;

  133. successor = current;

  134. current = current.left;

  135. }


  136. // 检查后继者(不可能有左节点树)是否有右节点树

  137. // 如果它有右节点树,则替换后继者位置,加到后继者父亲节点的左节点.

  138. if(successor != deleteNode.right){

  139. successorParent.left = successor.right;

  140. successor.right = deleteNode.right;

  141. }


  142. return successor;

  143. }


  144. publicvoid toString(TreeNode root){

  145. if(root !=null){

  146. toString(root.left);

  147. System.out.print("value = "+ root.value +" -> ");

  148. toString(root.right);

  149. }

  150. }

  151. }


  152. /**

  153. * 节点

  154. */

  155. classTreeNode{


  156. /**

  157. * 节点值

  158. */

  159. int value;


  160. /**

  161. * 左节点

  162. */

  163. TreeNode left;


  164. /**

  165. * 右节点

  166. */

  167. TreeNode right;


  168. publicTreeNode(int value){

  169. this.value = value;

  170. left =null;

  171. right =null;

  172. }

  173. }

面试点一:理解 TreeNode 数据结构


节点数据结构,即节点、左节点和右节点。如图



面试点二:如何确定二叉树的最大深度或者最小深度


答案:简单的递归实现即可,代码如下:

  1. int maxDeath(TreeNode node){

  2. if(node==null){

  3. return0;

  4. }

  5. int left = maxDeath(node.left);

  6. int right = maxDeath(node.right);

  7. returnMath.max(left,right)+1;

  8. }


  9. int getMinDepth(TreeNode root){

  10. if(root ==null){

  11. return0;

  12. }

  13. return getMin(root);

  14. }

  15. int getMin(TreeNode root){

  16. if(root ==null){

  17. returnInteger.MAX_VALUE;

  18. }

  19. if(root.left ==null&&root.right ==null){

  20. return1;

  21. }

  22. returnMath.min(getMin(root.left),getMin(root.right))+1;

  23. }

面试点三:如何确定二叉树是否是平衡二叉树


答案:简单的递归实现即可,代码如下:

  1. boolean isBalanced(TreeNode node){

  2. return maxDeath2(node)!=-1;

  3. }

  4. int maxDeath2(TreeNode node){

  5. if(node ==null){

  6. return0;

  7. }

  8. int left = maxDeath2(node.left);

  9. int right = maxDeath2(node.right);

  10. if(left==-1||right==-1||Math.abs(left-right)>1){

  11. return-1;

  12. }

  13. returnMath.max(left, right)+1;

  14. }

前面面试点是 二叉树 的,后面面试点是 搜索二叉树 的。先运行搜搜二叉树代码:

  1. publicclassBinarySearchTreeTest{


  2. publicstaticvoid main(String[] args){

  3. BinarySearchTree b =newBinarySearchTree();

  4. b.insert(3);b.insert(8);b.insert(1);b.insert(4);b.insert(6);

  5. b.insert(2);b.insert(10);b.insert(9);b.insert(20);b.insert(25);


  6. // 打印二叉树

  7. b.toString(b.root);

  8. System.out.println();


  9. // 是否存在节点值10

  10. TreeNode node01 = b.search(10);

  11. System.out.println("是否存在节点值为10 => "+ node01.value);

  12. // 是否存在节点值11

  13. TreeNode node02 = b.search(11);

  14. System.out.println("是否存在节点值为11 => "+ node02);


  15. // 删除节点8

  16. TreeNode node03 = b.delete(8);

  17. System.out.println("删除节点8 => "+ node03.value);

  18. b.toString(b.root);



  19. }

  20. }

结果如下:

  1. value =1-> value =2-> value =3-> value =4-> value =6-> value =8-> value =9-> value =10-> value =20-> value =25->

  2. 是否存在节点值为10=>10

  3. 是否存在节点值为11=>null

  4. 删除节点8=>8

  5. value =1-> value =2-> value =3-> value =4-> value =6-> value =9-> value =10-> value =20-> value =25->

面试点四:搜索二叉树如何实现插入


插入,还是比较容易理解的。就按照要求,插入到指定的位置。如果插入到叉搜索树的中间节点,那么会引起节点的动态变化。如图插入的逻辑:




  1. 值为 2 的节点开始判断

  2. 如果为空,则插入该节点

  3. 循环下面节点:

    1. 节点当前值大于,继续循环左节点

    2. 节点当前值小于,继续循环右节点

面试点五:搜索二叉树如何实现查找


算法复杂度 : O(lgN)。如图搜索及查找逻辑:




  1. 值为 2 的节点开始判断

    1. 节点当前值大于,继续循环左节点

    2. 节点当前值小于,继续循环右节点

  2. 如果值相等,搜索到对应的值,并返回

  3. 如果循环完毕没有,则返回未找到

面试点五:搜索二叉树如何实现删除


比较复杂了。相比新增、搜搜,删除需要将树重置。逻辑为:删除的节点后,其替代的节点为,其右节点树中值最小对应的节点。如图:



结果为:



三、小结


就像码出高效面试的程序媛偶尔吃一碗“老坛酸菜牛肉面”一样的味道,品味一个算法,比如 BST 的时候,总是那种说不出的味道。

面试必备小结:

  • 树,二叉树的概念

  • BST 算法




如以上文章或链接对你有帮助的话

可以点击页面右上角边按钮哦,让更多的人阅读这篇文章




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:编程帮,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......