什么是二叉树？
- 和链表一样，同样也是动态数据结构
- 二叉树具有唯一的根节点
class Node<E> { var e: E? = null var left: Node<E>? = null var right: Node<E>? = null }
- 每个节点最多有两个节点
- 二叉树具有天然递归结构
- 每个节点的左子树和右字数也是二叉树
- 二叉树不一定是满的
二叉树
一个null树也叫做二叉树，就算只有一个根节点，也是二叉树
左斜树&右斜树
二叉树中每个节点方向相同，全部节点只有左子节点的称为左斜树，只有右子节点的称为右斜树。
满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
完全二叉树
完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
什么是二分搜索树(Binary Search Tree)？\
- 二分搜索树是二叉树；
- 二分搜索树的每个节点的值大于其左子树所有节点的值，小于其右子树的所有节点的值,简称 左小右大；
- 每一颗字数也是二分搜索树；
- 存储的元素必须有可比较性；
二叉树的遍历
前序遍历
先遍历 节点e,再遍历左子树，最后遍历右子树
中序遍历
先遍历 左子树，再遍历节点e,最后遍历右子树
后序遍历
先遍历左子树，再遍历右子树，最后遍历节点e
举个栗子🌰
前序遍历
28，20，17，15，25，30，29，35
中序遍历
15，17，20，25，28，29，30，35
后序遍历
15，17，25，20，29，35，30，28
代码实现
这里实现一些比较经典的案例，比较简单的如前序遍历，中序遍历，后序遍历，使用递归，栈，队列 都可以简单实现。
二叉树的插入
private fun add(node: Node<E>?, e: E): Node<E> { if (node == null) { ++size return Node(e) } if (node.e > e) node.left = add(node.left, e) else if (node.e < e) node.right = add(node.right, e) return node }
整体思路也非常简单，按照前序遍历的方式，我们先遍历左子树，然后再遍历右子树，通过递归的实现，非常容易。
二叉树的删除
/** * 删除以node 为根的二分搜索树 值为e的节点 * 返回 删除节点后新的二分搜索树的根 * */ private fun remove(node: Node<E>?, e: E): Node<E>? { //健壮性判断 if (node == null) return node return when { //遍历左孩子 e < node.e -> { node.left=remove(node.left, e) node } //否则遍历右孩子 e > node.e -> { node.right=remove(node.right, e) node } else -> { //node.e==e //左孩子为null if (node.left == null) { //先拿到当前右孩子 val rightNode = node.right //删除右子树 node.right = null //更新树的高度 --size //返回删除后的右子树 return rightNode } //右孩子为null if (node.right == null) { val leftNode = node.left node.left = null --size return leftNode } //找到待删除节点左右子树均不为null的情况 //找到比待删除节点大的最小节点，即删除节点右子树的最小节点 // 用这个节点替代删除节点的位置 val nodeSuccess = minimum(node.right!!) nodeSuccess.right = removeMin(node.right) nodeSuccess.left = node.left node.left = null node.right = null return nodeSuccess } } }
二分搜索树的层序遍历
bfs实现
/** bfs-层序遍历 */ fun bfsTraverse(node: Node<Int>?): List<List<Int>>? { return node?.let { it -> val arrayList: ArrayList<ArrayList<Int>> = ArrayList() val queue = LinkedList<Node<Int>>() queue.add(it) while (queue.isNotEmpty()) { var count = queue.size val tempList = ArrayList<Int>() while (count > 0) { val temp = queue.pop() tempList.add(temp.e) temp.left?.let { queue.add(it) } temp.right?.let { queue.add(it) } --count } arrayList.add(tempList) } arrayList } }
dfs实现(按层输出)
/* 层序遍历-普通arraylist */ private fun getBstList( node: Node<E>?, height: Int, arrayList: ArrayList<LinkedList<String>> ): ArrayList<LinkedList<String>> { //如果当前高度为null,就新增一个子list if (arrayList.size <= height) { arrayList.add(LinkedList()) } if (node == null) { val nullLists = arrayList[height] nullLists.add("#") return arrayList } //拿到子list，开始增加 val lists = arrayList[height] //计算什么位置时增加下标 lists.add(node.e.toString()) getBstList(node.left, height + 1, arrayList) getBstList(node.right, height + 1, arrayList) return arrayList }
更多方法
相关的更多实现方法这里就不一一列举了
- 前，中，后序遍历
- 寻找树中最小元素，最大元素
- 寻找树中最小元素节点，最大元素节点
- 二分搜索树删除最小值，最大值所在节点，并返回最小值，最大值
