二叉树

二叉树简介

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉查找树的子节点与父节点的键一般满足一定的顺序关系，习惯上，左节点的键少于父亲节点的键，右节点的键大于父亲节点的键。

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键总是大于或等于任何一个子节点的键；最小堆：父结点的键总是小于或等于任何一个子节点的键。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

二叉树与树的区别

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：

  1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2。
  2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

定义二叉树的结构

二叉树的每个节点由键key、值value与左右子树left/right组成，这里我们把节点声明为一个泛型结构。

  1. type TreeNode<K,V> = Option<Box<Node<K,V>>>;
  2. #[derive(Debug)]
  3. struct Node<K,V: std::fmt::Display> {
  4.    left: TreeNode<K,V>,
  5.    right: TreeNode<K,V>,
  6.    key: K,
  7.    value: V,
  8. }

实现二叉树的初始化与二叉查找树的插入

由于二叉查找树要求键可排序，我们要求K实现PartialOrd

  1. trait BinaryTree<K,V> {
  2.     fn pre_order(&self);
  3.     fn in_order(&self);
  4.     fn pos_order(&self);
  5. }
  6. trait BinarySearchTree<K:PartialOrd,V>:BinaryTree<K,V> {
  7.     fn insert(&mut self, key:K,value: V);
  8. }
  9. impl<K,V:std::fmt::Display> Node<K,V> {
  10.     fn new(key: K,value: V) -> Self {
  11.         Node{
  12.             left: None,
  13.             right: None,
  14.             value: value,
  15.             key: key,
  16.         }
  17.     }
  18. }
  19. impl<K:PartialOrd,V:std::fmt::Display> BinarySearchTree<K,V> for Node<K,V>{
  20.     fn insert(&mut self, key:K,value:V) {
  21.         if self.key < key {
  22.             if let Some(ref mut right) = self.right {
  23.                 right.insert(key,value);
  24.             } else {
  25.                 self.right = Some(Box::new(Node::new(key,value)));
  26.             }
  27.         } else {
  28.             if let Some(ref mut left) = self.left {
  29.                 left.insert(key,value);
  30.             } else {
  31.                 self.left = Some(Box::new(Node::new(key,value)));
  32.             }
  33.         }
  34.     }
  35. }

二叉树的遍历

  • 先序遍历：首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树。
  • 中序遍历：首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树。
  • 后序遍历：首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根。

下面是代码实现：

  1. impl<K,V:std::fmt::Display> BinaryTree<K,V> for Node<K,V> {
  2.     fn pre_order(&self) {
  3.         println!("{}", self.value);
  5.         if let Some(ref left) = self.left {
  6.             left.pre_order();
  7.         }
  8.         if let Some(ref right) = self.right {
  9.             right.pre_order();
  10.         }
  11.     }
  13.     fn in_order(&self) {
  14.         if let Some(ref left) = self.left {
  15.             left.in_order();
  16.         }
  17.         println!("{}", self.value);
  18.         if let Some(ref right) = self.right {
  19.             right.in_order();
  20.         }
  21.     }
  22.     fn pos_order(&self) {
  23.         if let Some(ref left) = self.left {
  24.             left.pos_order();
  25.         }
  26.         if let Some(ref right) = self.right {
  27.             right.pos_order();
  28.         }
  29.         println!("{}", self.value);
  30.     }
  31. }

测试代码

  1. type BST<K,V> = Node<K,V>;
  3. fn test_insert() {
  4.     let mut root = BST::<i32,i32>::new(3,4);
  5.     root.insert(2,3);
  6.     root.insert(4,6);
  7.     root.insert(5,5);
  8.     root.insert(6,6);
  9.     root.insert(1,8);
  10.     if let Some(ref left) = root.left {
  11.         assert_eq!(left.value, 3);
  12.     }
  14.     if let Some(ref right) = root.right {
  15.         assert_eq!(right.value, 6);
  16.         if let Some(ref right) = right.right {
  17.             assert_eq!(right.value, 5);
  18.         }
  19.     }
  20.     println!("Pre Order traversal");
  21.     root.pre_order();
  22.     println!("In Order traversal");
  23.     root.in_order();
  24.     println!("Pos Order traversal");
  25.     root.pos_order();
  26. }
  28. fn main() {
  29.     test_insert();
  30. }

练习

基于以上代码，修改成二叉堆的形式。