二叉樹

二叉樹簡介

在計算機科學(xué)中，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。

二叉查找樹的子節(jié)點與父節(jié)點的鍵一般滿足一定的順序關(guān)系，習(xí)慣上，左節(jié)點的鍵少于父親節(jié)點的鍵，右節(jié)點的鍵大于父親節(jié)點的鍵。

二叉堆是一種特殊的堆，二叉堆是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）。二叉堆有兩種：最大堆和最小堆。最大堆：父結(jié)點的鍵總是大于或等于任何一個子節(jié)點的鍵；最小堆：父結(jié)點的鍵總是小于或等于任何一個子節(jié)點的鍵。

二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結(jié)點；深度為k的二叉樹至多有2^k-1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n_0，度為2的結(jié)點數(shù)為n_2，則n_0=n_2+1。

一棵深度為k，且有2^k-1個節(jié)點稱之為滿二叉樹；深度為k，有n個節(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個節(jié)點都與深度為k的滿二叉樹中，序號為1至n的節(jié)點對應(yīng)時，稱之為完全二叉樹。

二叉樹與樹的區(qū)別

二叉樹不是樹的一種特殊情形，盡管其與樹有許多相似之處，但樹和二叉樹有兩個主要差別：

1. 樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2。
2. 樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分。

定義二叉樹的結(jié)構(gòu)

二叉樹的每個節(jié)點由鍵key、值value與左右子樹left/right組成，這里我們把節(jié)點聲明為一個泛型結(jié)構(gòu)。

type TreeNode<K,V> = Option<Box<Node<K,V>>>;
#[derive(Debug)]
struct Node<K,V: std::fmt::Display> {
   left: TreeNode<K,V>,
   right: TreeNode<K,V>,
   key: K,
   value: V,
}

實現(xiàn)二叉樹的初始化與二叉查找樹的插入

由于二叉查找樹要求鍵可排序，我們要求K實現(xiàn)PartialOrd

trait BinaryTree<K,V> {
    fn pre_order(&self);
    fn in_order(&self);
    fn pos_order(&self);
}
trait BinarySearchTree<K:PartialOrd,V>:BinaryTree<K,V> {
    fn insert(&mut self, key:K,value: V);
}
impl<K,V:std::fmt::Display> Node<K,V> {
    fn new(key: K,value: V) -> Self {
        Node{
            left: None,
            right: None,
            value: value,
            key: key,
        }
    }
}
impl<K:PartialOrd,V:std::fmt::Display> BinarySearchTree<K,V> for Node<K,V>{
    fn insert(&mut self, key:K,value:V) {
        if self.key < key {
            if let Some(ref mut right) = self.right {
                right.insert(key,value);
            } else {
                self.right = Some(Box::new(Node::new(key,value)));
            }
        } else {
            if let Some(ref mut left) = self.left {
                left.insert(key,value);
            } else {
                self.left = Some(Box::new(Node::new(key,value)));
            }
        }
    }
}

二叉樹的遍歷

• 先序遍歷：首先訪問根，再先序遍歷左（右）子樹，最后先序遍歷右（左）子樹。
• 中序遍歷：首先中序遍歷左（右）子樹，再訪問根，最后中序遍歷右（左）子樹。
• 后序遍歷：首先后序遍歷左（右）子樹，再后序遍歷右（左）子樹，最后訪問根。

下面是代碼實現(xiàn)：

impl<K,V:std::fmt::Display> BinaryTree<K,V> for Node<K,V> {
    fn pre_order(&self) {
        println!("{}", self.value);

        if let Some(ref left) = self.left {
            left.pre_order();
        }
        if let Some(ref right) = self.right {
            right.pre_order();
        }
    }

    fn in_order(&self) {
        if let Some(ref left) = self.left {
            left.in_order();
        }
        println!("{}", self.value);
        if let Some(ref right) = self.right {
            right.in_order();
        }
    }
    fn pos_order(&self) {
        if let Some(ref left) = self.left {
            left.pos_order();
        }
        if let Some(ref right) = self.right {
            right.pos_order();
        }
        println!("{}", self.value);
    }
}

測試代碼

type BST<K,V> = Node<K,V>;

fn test_insert() {
    let mut root = BST::<i32,i32>::new(3,4);
    root.insert(2,3);
    root.insert(4,6);
    root.insert(5,5);
    root.insert(6,6);
    root.insert(1,8);
    if let Some(ref left) = root.left {
        assert_eq!(left.value, 3);
    }

    if let Some(ref right) = root.right {
        assert_eq!(right.value, 6);
        if let Some(ref right) = right.right {
            assert_eq!(right.value, 5);
        }
    }
    println!("Pre Order traversal");
    root.pre_order();
    println!("In Order traversal");
    root.in_order();
    println!("Pos Order traversal");
    root.pos_order();
}

fn main() {
    test_insert();
}

練習(xí)

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