二叉树

Posted on | In

定义：二叉树(binary tree)t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。

所谓二叉树（Binary Tree），其意义是：“任何节点最多只允许两个子节点”。如果以递归的方式来定义二叉树，我们可以说：“一个二叉树如果不为空，便是由一个根节点和左右两子树构成；左右都可能为空。

数据结构中，二叉搜索树（Binary Search Tree）、平衡二叉搜索树（Balanced Binary Search Tree）、完全二叉树（Complete Binary Tree）、AVL Tree（Adelson-Velskii-Landis Tree）、红黑树（RB-Tree）等，都是基于二叉树实现的。

二叉树的表示

二叉树通常使用链表和指针来表示。每个元素使用带有两个指针域的节点表示，两个指针域分别是LeftChild和RightChild，除此之外，每个节点还有一个Data。代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T>
class BinaryTreeNode{
    typedef BinaryTreeNode<T>* node_ptr;
public:
    BinaryTreeNode(){ left_child_  = right_child_ = 0;}
    BinaryTreeNode(const T &e, node_ptr l = 0, node_ptr r = 0)
    {
        data_ = e;
        left_child_ = l;
        right_child_ = r;
    }
    
private:
    T data_;
    node_ptr left_child_;
    node_ptr right_child_;
}

获取二叉树的深度

通常使用递归的解法求解二叉树的深度：

  • 若二叉树为空，则深度为0；
  • 若二叉树不为空，二叉树的深度 = max（左子树深度，右子树深度）+ 1。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
template<class T>
int GetDepth(BinaryTreeNode<T> *root_prt)
{
    if(root_ptr == NULL){
        return 0;
    }
    
    int left_depth = GetDepth(root_ptr->left_child_);
    int right_depth = GetDepth(root_ptr->right_child_);
    
    return left_depth > right_depth ? (left_depth + 1) : (right_depth + 1);
}

获取二叉树的节点数

  • 若二叉树为空，则节点数为0；
  • 若二叉树不为空，二叉树节点数 = 左子树节点数 + 右子树节点数 + 1。

代码如下：

1
2
3
4
5
6
7
8
9
template<class T>
int GetNodeNum(BinaryTreeNode<T> *root_ptr)
{
    if(root_ptr == NULL){
        return 0;
    }
    
    return GetNodeNum(root_ptr->left_child_) + GetNodeNum(root_ptr->right_child_) + 1;
}