数据结构之二叉查找树
二叉查找树
定义：树是n(n>=0)个节点的有限集。二叉树是另一种树型结构，特点是每个节点最多有2个子节点，并且二叉树的子树有左右之分。
看上图，比如添加2节点的时候，发现2比3小，所以放到左侧树中，又发现比1大，所以最终在1的右节点处。
创建一个二叉查找树的类：
/// <summary> /// 二叉查找树类 /// IComparable：使用此进行限制是为了实现 两个实体类之间按>，=，<进行比较 /// </summary> /// <typeparam name="E"></typeparam> class BST<E> where E : IComparable<E> { /// <summary> /// 节点类 /// </summary> private class Node { public E e; public Node left; public Node right; public Node(E e) { this.e = e; left = null; right = null; } } private Node root; private int N; public BST() { root = null; N = 0; } public int Count { get { return N; } } public bool IsEmpty { get { return N == 0; } } }
添加节点
递归添加方法：
public void Add(E e) { root= Add(root,e); } /// <summary> /// 添加新节点 /// 1： /// </summary> /// <param name="node"></param> /// <param name="e"></param> /// <returns></returns> private Node Add(Node node, E e) { if (root == null) { N++; return new Node(e); } if (e.CompareTo(node.e) < 0) { //添加的节点比当前要比较的节点小 node.left = Add(node.left, e); } else if (e.CompareTo(node.e) > 0) { node.right = Add(node.right, e); } return node; }
递归添加过程分析
比如一次要添加8,4,6,7节点，添加8节点的时候，8作为根节点，添加4节点的时候，4<8,所以执行node.left = Add(node.left, e);，实时的情况为8.left=Add(null,4);因为此时8节点没有左孩子，是空的，根据Add方法内部逻辑可知if(node==null),那么返回new Node(4),所以最终节点4作为8的左孩子。
二叉查找树中的包含（递归实现）
/// <summary> /// 是否包含元素 /// </summary> /// <param name="e"></param> /// <returns></returns> public bool Contains(E e) { //从根节点开始查找 return Contains(root,e); } /// <summary> /// 从根节点开始查找是否包含此节点 /// 1：根据查找的节点从根节点开始比较大小 /// </summary> /// <param name="node">根节点或者二叉树中被比较的节点</param> /// <param name="e">目标节点</param> /// <returns></returns> private bool Contains(Node node, E e) { if (node == null) { return false; } if (e.CompareTo(node.e) == 0) { //说明找到了 return true; } else if (e.CompareTo(node.e) < 0) { //目标节点比被比较节点小，所以在被比较节点的左子树中找 Contains(node.left,e); }else if(e.CompareTo(node.e)>0) { //目标节点比被比较节点大，所以在被比较节点的右子树中找 Contains(node.right, e); } return false; }
二叉查找树的遍历
遍历和包含不一样，遍历要从根节点开始访问，最后将二叉树上的所有节点都访问一遍
1.前序遍历方法
步骤：从节点8开始遍历，8左节点是4,4的左节点是2,2没有子节点，所以回到4节点，然后再看4节点的右节点6,6节点同样没有子节点，回退到4节点，4节点的子节点已遍历完毕，回退到8节点，此时8节点的左子树已经遍历完毕，开始遍历右子树，步骤和左子树中的步骤一样遍历完成之后结果为：8->4->2->6->12->10->14
代码实现：
public void PreOrder() { PreOrder(root); } /// <summary> /// 前序遍历 /// </summary> /// <param name="node"></param> private void PreOrder(Node node) { if(node==null) { return; } Console.WriteLine(node.e); PreOrder(node.left); PreOrder(node.right); }
中序遍历
它是先遍历左子树，然后遍历根节点，最后遍历右子树
中序遍历是以左根右规则进行的，所以从8节点开始找其左子树，其中4节点也还是存在左节点2，并且2无子节点，所以第一个遍历出来的是2，然后找2节点的根节点4，再看4节点的右子节点6,4节点的子节点都遍历完成之后退回到根节点8，然后按照规则再遍历右子树即可。
递归代码实现
public void InOrder() { InOrder(root); } /// <summary> /// 中序遍历 /// </summary> /// <param name="node"></param> private void InOrder(Node node) { if (node == null) { return; } //1：遍历左子树 InOrder(node.left); //2：访问根节点 Console.WriteLine(node.e); //3：遍历右子树 InOrder(node.right); }
后序遍历
代码实现：
public void PostOrder() { PostOrder(root); } /// <summary> /// 后序遍历 /// </summary> /// <param name="node"></param> private void PostOrder(Node node) { if (node == null) { return; } //1：遍历左子树 PostOrder(node.left); //2：遍历右子树 PostOrder(node.right); //3：访问根节点 Console.WriteLine(node.e); }
层序遍历
层序遍历是和队列有关系的，一层一层的遍历。
代码：
public void LevelOrder() { Queue<Node> q = new Queue<Node>(); //在队列的末尾添加一个元素 q.Enqueue(root); while (q.Count != 0) { //移除队头的元素 Node cur = q.Dequeue(); Console.Write(cur.e); if(cur.left!=null) { q.Enqueue(cur.left); } if (cur.right != null) { q.Enqueue(cur.right); } } }
删除二叉树的节点
1.删除最大值，最小值。
在二叉树中寻找最大值最小值很方便，因为左子树永远是最小的，找当前节点的左子树，一直找到最后就是最小值，最大值同理。
代码：
public E Min() { if (root == null) { throw new Exception("空树"); } return Min(root).e; } /// <summary> /// 查找最小值 /// </summary> /// <param name="node"></param> /// <returns></returns> private Node Min(Node node) { if (node.left == null) { return node; } return Min(node.left); } public E Max() { if (root == null) { throw new Exception("空树"); } return Max(root).e; } /// <summary> /// 查找最大值 /// </summary> /// <param name="node"></param> /// <returns></returns> private Node Max(Node node) { if (node.left == null) { return node; } return Max(node.right); }
（2）删除最大最小值
#region 删除最大最小值 public E RemoveMin() { E ret = Min(); root = RemoveMin(root); return ret; } private Node RemoveMin(Node node) { if (node.left == null) { N--; return node.right; } node.left = RemoveMin(node.left); return node; } public E RemoveMax() { E ret = Min(); root = RemoveMax(root); return ret; } private Node RemoveMax(Node node) { //如果node右子树为空，说明当前节点最大，所以需要删除当前 //节点，直接返回当前节点的右子树 if (node.right == null) { N--; //此时还需要保留被删除节点的左子树，因为它的左子树肯定比其小，不需要删除， //所以直接保留下来。就算是此时左子树为空也没问题，因为存在空树。 return node.left; } //如果找到了最大节点，会返回最大节点右子树(此时为空)，赋给上一个节点的右孩子节点 //所以此时当前节点被删除了。 node.right = RemoveMax(node.right); return node; } #endregion
（3）删除任意值
1：要删除节点只有左孩子时。
比如删除12，最后变为：
2：删除节点只有右孩子时:
比如说删除12：就是将12节点 的右子树成为8的右子树即可。
（3）删除叶子节点(就是没有左右子树的节点)
这时候可以把叶子节点看做是只有左子树或者只有右子树的节点，只不过是左右子树都为空而已，没什么区别。
（4）删除节点存在左右孩子
比如还是删除12节点，此时我们需要在12的右子树中寻找一个最小节点来代替12节点。所以需要先找出右子树中的最小节点13，然后将其从14节点左子树中删除，然后将12节点的左子树赋给13节点，
#region 删除任意元素 /// <summary> /// 删除以node为根节点的二叉查找树中值为e的节点。 /// 返回删除节点后新的二叉查找树的根。 /// </summary> /// <param name="node"></param> /// <param name="e"></param> /// <returns></returns> private Node Remove(Node node, E e) { if (node == null) return null; if (e.CompareTo(node.e) < 0) { //如果要查找的值小于被删除的节点，到左子树中找 node.left = Remove(node.left, e); return node; } else if (e.CompareTo(node.e) > 0) { //如果要查找的值大于被删除的节点，到右子树中找 node.right = Remove(node.right, e); return node; } else { //被删除节点就是要查找的节点 if (node.right == null) { N--; return node.left; } if (node.left == null) { N--; return node.right; } //左右子树都存在的情况 Node s = Min(node.right); s.right = RemoveMin(node.right); s.left = node.left; return s; } } #endregion
树的最大高度以及性能分析
看上图，同样一组数，不同顺序导致了二叉树的形状不同，最终导致了性能也不同，最坏的情况已经退化成了链表了。
所以对于无序的性能比较高。
如：
（1）计算二叉树的最大高度
通过高度我们可以看出当前二叉树的性能。
#region 计算高度 public int MaxHeight() { return MaxHeight(root); } /// <summary> /// 以node为根节点的二叉树的最大高度 /// </summary> /// <param name="node"></param> /// <returns></returns> private int MaxHeight(Node node) { if (node == null) { return 0; } int l = MaxHeight(node.left); int r = MaxHeight(node.right); //加1是为了加上根节点本身高度 return Math.Max(l, r) + 1; } #endregion
完整代码：
/// <summary> /// 二叉查找树类 /// IComparable：使用此进行限制是为了实现 两个实体类之间按>，=，<进行比较 /// </summary> /// <typeparam name="E"></typeparam> class BST<E> where E : IComparable<E> { /// <summary> /// 节点类 /// </summary> private class Node { public E e; public Node left; public Node right; public Node(E e) { this.e = e; left = null; right = null; } } private Node root; private int N; public BST() { root = null; N = 0; } public int Count { get { return N; } } public bool IsEmpty { get { return N == 0; } } public void Add(E e) { root = Add(root, e); } /// <summary> /// 添加新节点 /// 1： /// </summary> /// <param name="node"></param> /// <param name="e"></param> /// <returns></returns> private Node Add(Node node, E e) { if (node == null) { N++; return new Node(e); } if (e.CompareTo(node.e) < 0) { //添加的节点比当前要比较的节点小 node.left = Add(node.left, e); } else if (e.CompareTo(node.e) > 0) { node.right = Add(node.right, e); } return node; } /// <summary> /// 是否包含元素 /// </summary> /// <param name="e"></param> /// <returns></returns> public bool Contains(E e) { //从根节点开始查找 return Contains(root, e); } /// <summary> /// 从根节点开始查找是否包含此节点 /// 1：根据查找的节点从根节点开始比较大小 /// </summary> /// <param name="node">根节点或者二叉树中被比较的节点</param> /// <param name="e">目标节点</param> /// <returns></returns> private bool Contains(Node node, E e) { if (node == null) { return false; } if (e.CompareTo(node.e) == 0) { //说明找到了 return true; } else if (e.CompareTo(node.e) < 0) { //目标节点比被比较节点小，所以在被比较节点的左子树中找 Contains(node.left, e); } else if (e.CompareTo(node.e) > 0) { //目标节点比被比较节点大，所以在被比较节点的右子树中找 Contains(node.right, e); } return false; } public void PreOrder() { PreOrder(root); } /// <summary> /// 前序遍历 /// </summary> /// <param name="node"></param> private void PreOrder(Node node) { if (node == null) { return; } Console.WriteLine(node.e); PreOrder(node.left); PreOrder(node.right); } public void InOrder() { InOrder(root); } /// <summary> /// 中序遍历 /// </summary> /// <param name="node"></param> private void InOrder(Node node) { if (node == null) { return; } //1：遍历左子树 InOrder(node.left); //2：访问根节点 Console.WriteLine(node.e); //3：遍历右子树 InOrder(node.right); } public void PostOrder() { PostOrder(root); } /// <summary> /// 后序遍历 /// </summary> /// <param name="node"></param> private void PostOrder(Node node) { if (node == null) { return; } //1：遍历左子树 PostOrder(node.left); //2：遍历右子树 PostOrder(node.right); //3：访问根节点 Console.WriteLine(node.e); } public void LevelOrder() { Queue<Node> q = new Queue<Node>(); //在队列的末尾添加一个元素 q.Enqueue(root); while (q.Count != 0) { //移除队头的元素 Node cur = q.Dequeue(); Console.Write(cur.e); if (cur.left != null) { q.Enqueue(cur.left); } if (cur.right != null) { q.Enqueue(cur.right); } } } public E Min() { if (root == null) { throw new Exception("空树"); } return Min(root).e; } /// <summary> /// 查找最小值 /// </summary> /// <param name="node"></param> /// <returns></returns> private Node Min(Node node) { if (node.left == null) { return node; } return Min(node.left); } public E Max() { if (root == null) { throw new Exception("空树"); } return Max(root).e; } /// <summary> /// 查找最大值 /// </summary> /// <param name="node"></param> /// <returns></returns> private Node Max(Node node) { if (node.left == null) { return node; } return Max(node.right); } #region 删除最大最小值 public E RemoveMin() { E ret = Min(); root = RemoveMin(root); return ret; } private Node RemoveMin(Node node) { if (node.left == null) { N--; return node.right; } node.left = RemoveMin(node.left); return node; } public E RemoveMax() { E ret = Min(); root = RemoveMax(root); return ret; } private Node RemoveMax(Node node) { //如果node右子树为空，说明当前节点最大，所以需要删除当前 //节点，直接返回当前节点的右子树 if (node.right == null) { N--; //此时还需要保留被删除节点的左子树，因为它的左子树肯定比其小，不需要删除， //所以直接保留下来。就算是此时左子树为空也没问题，因为存在空树。 return node.left; } //如果找到了最大节点，会返回最大节点右子树(此时为空)，赋给上一个节点的右孩子节点 //所以此时当前节点被删除了。 node.right = RemoveMax(node.right); return node; } #endregion #region 删除任意元素 /// <summary> /// 删除以node为根节点的二叉查找树中值为e的节点。 /// 返回删除节点后新的二叉查找树的根。 /// </summary> /// <param name="node"></param> /// <param name="e"></param> /// <returns></returns> private Node Remove(Node node, E e) { if (node == null) return null; if (e.CompareTo(node.e) < 0) { //如果要查找的值小于被删除的节点，到左子树中找 node.left = Remove(node.left, e); return node; } else if (e.CompareTo(node.e) > 0) { //如果要查找的值大于被删除的节点，到右子树中找 node.right = Remove(node.right, e); return node; } else { //被删除节点就是要查找的节点 if (node.right == null) { N--; return node.left; } if (node.left == null) { N--; return node.right; } //左右子树都存在的情况 Node s = Min(node.right); s.right = RemoveMin(node.right); s.left = node.left; return s; } } #endregion #region 计算高度 public int MaxHeight() { return MaxHeight(root); } /// <summary> /// 以node为根节点的二叉树的最大高度 /// </summary> /// <param name="node"></param> /// <returns></returns> private int MaxHeight(Node node) { if (node == null) { return 0; } int l = MaxHeight(node.left); int r = MaxHeight(node.right); //加1是为了加上根节点本身高度 return Math.Max(l, r) + 1; } #endregion }