数据结构知识点-树和二叉树

树

树的基本概念

树（有根树 Rooted Tree）是由有限个结点（即数据元素）组成的集合。若这一集合的结点个数为0，则我们称该树为空树；否则称为非空树，有以下特点：

1. 有且仅有一个称为树根的结点（简称“根结点”），该结点无任何前驱结点（包括直接前驱结点和间接前驱结点）。
2. 当结点数目大于1时，除了树根结点之外的其余结点被分成若干个互不相交的有限集合，这些有限集合均可被视为一棵独立的树，它们均被称为树根结点的子树。

结点：数据元素

分支：表示元素之间关系的线段

结点的度：每个结点拥有子树的数目被称为结点的度。

叶子结点（终端结点）：度为0的结点被称为叶子结点。

分支结点（非终端结点）：度不为0的结点被称为分支结点。

树的度：树内所有结点度的最大值被称为该树的度。

孩子结点（后继结点）：树中任何一个结点的子树的根结点被称为这一结点的孩子结点。

双亲结点：对于树中任何一个结点而言，若其具有孩子结点，那么该结点就被称为其孩子结点的双亲结点。

兄弟结点：同一双亲的孩子结点互为兄弟结点。

祖先结点：从根结点到树中任一结点所经过的所有结点被称为该结点的祖先结点。

子孙结点（后代结点）：树中以某一结点为根的子树中任一结点均被称为该根结点的子孙结点。

结点的深度（depth）：树中结点M的深度就是从树根到M的路径的长度。

结点的层次（level）：深度为d的所有结点都位于树的d层，根结点的层次为0，它也是0层的唯一结点。

树的高度（height）：树的高度比树中最深层结点的深度多1。如图所示树高度为4。

在不同的教材中，深度、高度和层次可能在定义的细节上有所不同，但主要是关于根结点是0层还是1层，深度和高度是否是相同还是差1，并没有本质的差别。

有根树和自由树

自由树是从图论角度定义的树，相当于无向连通图。

自由树由顶点集和边集构成。并且满足以下2个条件：

1. 顶点集中的任意一个顶点与其他任意顶点都是相通的；
2. 树中没有回路，即不存在从任意顶点出发，通过其它顶点其它边又回到该顶点的路径，

如图所示为包含4个结点的两棵自由树。

有序树和无序树

• 有序树(ordered tree)：如果将树中结点的各子树看成从左至右是有次序的，这些子树的位置是不能被改变的，则称该树为有序树。
• 无序树(unordered tree)：如果将树中结点的各子树看成是无次序的，这些子树的位置是能够被改变的，则称该树为无序树。

如没有特别说明，一般情况下，树默认为有序、有根树。

完全k叉树

一棵高度为h的完全k叉树，是由高度为 h-1 的满k叉树以及最下层的连续叶结点（至少1个）构成。

森林

森林(forest)：m(m≥0)个互不相交的树的集合称为森林。删除一棵非空树的根结点，即构成一个森林；反之，若增加一个根结点，让森林中每棵树的根结点都变成它的孩子，则森林就成为一棵树。

树的存储结构

双亲表示法 (顺序存储结构)

用一个一维数组来存储树的结点，同时在每个数组元素中附加一个指示器，用以指示其双亲结点的位置(双亲结点所在数组元素的下标)。

孩子兄弟表示法 (二叉链表表示法)

树的遍历

先序遍历：若树非空，则先访问根结点，然后依次先序遍历根结点的每棵子树。

后序遍历：若树非空，则先依次后序遍历根结点的每棵子树，然后访问根结点。

层序遍历：从根结点开始，一层一层从上往下，每一层从左往右依次访问结点。

树的性质

1、假设树中有 n 个结点，b 根树枝，则 n=b+1，即结点数与树枝数的关系：n=b+1

2、度为 k 的树第 i（i ≥ 0）层上最多结点数为 k^i。

3、高度为h（h ≥ 1）的k叉树最多结点数为 (k^h−1)/(k−1)

4、具有n个结点的k叉树的最小高度为 h=⌈logk(n(k−1)+1)⌉

二叉树

二叉树的定义

• 二叉树（binary tree）是由若干个称为结点(node)的元素构成的集合，它或者为空集，或者由一个称为根（root）的结点和分别称为根的左子树（left subtree）和根的右子树（right subtree）的两棵二叉树组成。其中根结点的左子树和右子树互不相交且与根不相交（不相交意味着他们没有共有的结点）。

  A binary tree is either empty, or it consists of a node（结点） called the root（根） together with two binary trees called the left subtree （左子树）and the right subtree（右子树） of the root.

解读 && 相关术语

(1) 递归定义 (recursive definition)，后续对二叉树进行操作经常使用递归的方法。

(2) 二叉树可以为空 (empty binary tree)

(3) 结点即数据元素(Node,Data Element)

(4) 非空二叉树的3个部分

a. 根结点，地位尊贵，所有其它结点的祖先

b. 根的左子树:一棵二叉树，空或者非空

c. 根的右子树:一棵二叉树，空或者非空

(5) 二叉树的子树严格区分左右

(6) 结点之间的关系：根结点与其子树的根之间的父子关系

• A（双亲）-----G（左孩子）
• A（双亲）-----H（右孩子）
• G（双亲）-----C（右孩子）
• G、H 互为兄弟
• H（祖先） ----E F（子孙）

(7) 二叉树是一种层次型的数据结构

(8) 结点的度

• 结点的度：结点所拥有的子树的数目。A的度为2，E的度为1，C的度为0。

• 叶子：度为0的结点。

(9) 二叉树的度：二叉树中结点度的最大值。任意一棵二叉树的度小于等于2。

几类特殊的二叉树

严格二叉树：也称为2树。是指不存在度为1的结点的二叉树，空二叉树是严格二叉树，非空的严格二叉树中，除了叶子结点之外，每个结点都有2个孩子。如图所示为一棵严格二叉树。

扩充二叉树（extended binary tree）：对一棵已有的非空二叉树进行扩充，使得原二叉树中所有结点的度数都变为2。空二叉树的扩充二叉树仍然为空。

满二叉树（full binary tree）：高度为k且含有 2^k-1个结点的二叉树。它的叶子结点全部在最下层，分支结点的度全为2。

完全二叉树（complete binary tree）：所含的n个结点和满二叉树中编号为1至n的结点的编号和形状都一一对应。可在满二叉树的基础上连续删除若干个结点得到。

• 叶子结点集中在最下面两层。
• 对任一结点，若其右子树的深度为h，则其左子树的深度为 h 或 h+1 。
• 完全二叉树是具有相同结点数的二叉树中一棵最矮的二叉树。
• 满二叉树是完全二叉树的一种特例。

单支二叉树：

• 除叶子之外，每个结点都只有一个唯一的左孩子的二叉树，俗称为左单支二叉树（左图）。
• 除叶子之外，每个结点都只有一个唯一的右孩子的二叉树，俗称为右单支二叉树（右图）。

在非单支二叉树中，有时也称其包含的单支部分称为左单支或右单支。

二叉树的性质

• 性质1：假设二叉树中有n个结点，b根树枝，则 n=b+1。

• 性质2：在二叉树的第 i 层上至多有2^i 个结点。(i≥0)

• 性质3：高度为 h 的二叉树上至多含 2^h-1 个结点（h≥1）。

• 性质4：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。

• 性质5：具有n个结点的完全二叉树的高度 h = ⌈log2(n+1)⌉ or ⌊log2n⌋+1

• 性质6：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为 i 的结点：

  • 若 i = 1，则该结点是二叉树的根，无双亲，否则，编号为 ⌊i/2⌋ 的结点为其双亲结点；
  • 若 2i > n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；
  • 若 2i+1 > n，则该结点无右孩子结点，否则，编号为 2i+1 的结点为其右孩子结点。
  

  也有另一种编号方法是进行从0至n-1的编号，那么i号结点的双亲为 ⌊(i−1)/2⌋，左孩子为 2i+1 号，右孩子为 2i+2 号。

二叉树的遍历

按照某种次序对二叉树的每个结点访问并且只访问一次的过程。

层次遍历：从上到下，从左到右遍历。

递归遍历：将对一棵非空二叉树的遍历分解成：

• 对根结点本身的访问，假设用V表示；
• 对根结点左子树的遍历，用L表示；
• 对根结点右子树的遍历，用R表示。

先序遍历(preorder traversal，先根遍历、前序遍历)：若二叉树为空树，则空操作。否则，①访问根结点；②先序遍历左子树；③先序遍历右子树。

中序遍历(inorder traversal，中根遍历)：若二叉树为空树，则空操作。否则，①中序遍历左子树；②访问根结点；③中序遍历右子树。

后序遍历(postorder traversal，后根遍历)：若二叉树为空树，则空操作。否则，①后序遍历左子树；②后序遍历右子树； ③访问根结点。

举例

表达式二叉树的遍历

遍历	表达式形式
先序	前缀表达式
中序	中缀表达式
后序	后缀表达式

二分查找的比较树

对二分查找的比较树的中序遍历得到有序序列。

二叉树的存储结构

二叉树的顺序存储结构

对于完全二叉树，用一组地址连续的存储单元从根结点开始依次自上而下，并按层次从左到右存储完全二叉树上的各结点元素，即将完全二叉树编号为 i 的结点元素存储在下标为 i 的数组元素中（如左图）。

对于非完全二叉树来说，顺序存储结构会造成存储空间的浪费（如右图），并且树的层次越深，结点越少，存储空间浪费越大。因此在实际使用时通常选择链式结构存储二叉树。

二叉树的链式存储结构 (二叉链表)

二叉树结点类

template <class Entry>
struct BinaryNode {
    Entry data;
    Binary_node<Entry> *left;
    Binary_node<Entry> *right;
};

链式二叉树类

template<class Entry>
class BinaryTree {
public:
    // Add methods here.
protected:
    // Add auxiliary function prototypes here.
    BinaryNode<Entry> *root;
};

二叉树基于链式存储结构的操作及算法

对于递归算法，定公有方法以供使用者调用，公有方法调用保护的递归算法。

遍历算法

先序遍历（递归）

template<class Entry>
void BinaryTree<Entry>::_recursivePreOrder(BinaryNode<Entry> *subRoot, void (*visit)(Entry &)) {
    if (subRoot != nullptr) {
        (*visit)(subRoot->data);
        _recursiveInOrder(subRoot->left, visit);
        _recursiveInOrder(subRoot->right, visit);
    }
}

中序遍历（递归）

定义一个公有方法 inOrder，调用递归方法 _recursiveInOrder 实现：

公有方法 inOrder()：

template<class Entry>
void BinaryTree<Entry>::inOrder(void (*visit)(Entry &)) {
    _recursiveInOrder(root, visit);
}

protected 递归方法 _recursiveInOrder()：

template<class Entry>
void BinaryTree<Entry>::_recursiveInOrder(BinaryNode<Entry> *subRoot, void (*visit)(Entry &)) {
    if (subRoot != nullptr) {
        _recursiveInOrder(subRoot->left, visit);
        (*visit)(subRoot->data);
        _recursiveInOrder(subRoot->right, visit);
    }
}

后序遍历（递归）

定义一个公有方法 postOrder，调用递归方法 _recursivePostOrder 实现：

公有方法 postOrder()：

template<class Entry>
void BinaryTree<Entry>::postOrder(void (*visit)(Entry &)) {
    _recursivePostOrder(root, visit);
}

protected 递归方法 _recursivePostOrder()：

template<class Entry>
void BinaryTree<Entry>::_recursivePostOrder(BinaryNode<Entry> *subRoot, void (*visit)(Entry &)) {
    if (subRoot != nullptr) {
        _recursiveInOrder(subRoot->left, visit);
        _recursiveInOrder(subRoot->right, visit);
        (*visit)(subRoot->data);
    }
}

层次遍历

template<class Entry>
void BinaryTree<Entry>::levelOrder(void (*visit)(Entry &)) {
    if (root ** nullptr) return;
    queue<BinaryNode<Entry> *> nodeQueue;	// 使用队列
    nodeQueue.push(root);
    while (!nodeQueue.empty()) {
        BinaryNode<Entry> *p = nodeQueue.front();
        (*visit)(p->data);
        if (p->left != nullptr) nodeQueue.push(p->left);
        if (p->right != nullptr) nodeQueue.push(p->right);
        nodeQueue.pop();
    }
}

拷贝方法（递归）

protected 方法，供复制构造函数 BinaryTree(const BinaryTree<Entry> &original)、= 运算符重载函数调用

template<class Entry>
BinaryNode<Entry> *BinaryTree<Entry>::_recursiveCopy(BinaryNode<Entry> *subRoot) {
    if (subRoot ** nullptr) return nullptr;
    BinaryNode<Entry> *newRoot = new BinaryNode<Entry>(subRoot->data);
    newRoot->left = _recursiveCopy(subRoot->left);
    newRoot->right = _recursiveCopy(subRoot->right);
    return newRoot;
}

清空方法（递归）

protected 方法，供析构函数 ~BinaryTree()、方法 clear() 调用

template<class Entry>
void BinaryTree<Entry>::_recursiveClear(BinaryNode<Entry> *&subRoot) {
    if (subRoot != nullptr) {
        _recursiveClear(subRoot->left);
        _recursiveClear(subRoot->right);
        delete subRoot;
        subRoot = nullptr;
    }
}

判空方法

template<class Entry>
bool BinaryTree<Entry>::empty() const {
    return root ** nullptr;
}

计算节点数量（递归）

公有方法 size()：

template<class Entry>
int BinaryTree<Entry>::size() const {
    return _recursiveLeafSize(root);
}

protected 方法 _recursiveLeafSize()：

template<class Entry>
int BinaryTree<Entry>::_recursiveLeafSize(BinaryNode<Entry> *subRoot) {
    if (subRoot ** nullptr) return 0;
    return 1 + _recursiveLeafSize(subRoot->left) + _recursiveLeafSize(subRoot->right);
}

求树的高度（递归）

公有方法 height()：

template<class Entry>
int BinaryTree<Entry>::height() const {
    return _recursiveHeight(root);
}

protected 方法 _recursiveHeight()：

template<class Entry>
int BinaryTree<Entry>::_recursiveHeight(BinaryNode<Entry> *subRoot) {
    if (subRoot ** nullptr) return 0;
    return max(_recursiveHeight(subRoot->left), _recursiveHeight(subRoot->right)) + 1;
}

删除所有叶子结点（递归）

公有方法 deleteLeaf()：

template<class Entry>
void BinaryTree<Entry>::deleteLeaf() {
    _recursiveDeleteLeaf(root);
}

protected 方法 _recursiveDeleteLeaf()：

template<class Entry>
void BinaryTree<Entry>::_recursiveDeleteLeaf(BinaryNode<Entry> *&subRoot) {
    if (subRoot ** nullptr) return;
    if (subRoot->left ** nullptr && subRoot->right ** nullptr) {
        delete subRoot;
        subRoot = nullptr;
        return;
    }
    _recursiveDeleteLeaf(subRoot->left);
    _recursiveDeleteLeaf(subRoot->right);
}