C++算法与数据结构

树的定义 树的定义及特点

树是 n ( n ≥ 1 ) n (n geq 1) n(n≥1)个结点的有限集合T，并且满足：

1. 有一个被称之为根(root)的结点
2. 其余的结点可分为 m ( m ≥ 0 ) m(m geq 0) m(m≥0)个互不相交的集合 T 1 T_1 T1​， T 2 T_2 T2​，…， T m T_m Tm​,这些集合本身也是一棵树，并称它们为根结点的子树(Subree)。每棵子树同样有自己的根结点。

• 树形结构的特点

一个数据元素可以有多个直接后继，但只有至多一个直接前驱，而线性结构中每个数据元素至多只有一个直接前驱和直接后继，因此树形结构可以表达更复杂的关系。

一些术语

1. 根结点，叶结点，内部结点： 树中唯一一个没有直接前驱的结点称为根节点(如上图的A)。树中没有直接后继的结点称为叶结点(如上图的K、L、M)。除根以外的非叶结点称为内部结点。
2. 结点的度和树的度： 一个结点直接后继的数目称为结点的度(如上图的A的度为3)。树中所有结点的度的最大值称为这棵树的度(如上图树的度为3)。
3. 子结点，父结点，祖先结点，子孙结点： 结点的直接后继称为结点的子结点。结点的直接前驱称为结点的父结点。在树中，每个结点都存在着唯一的一条到根结点的路径，路径上的所有结点都是该结点的祖先结点。子孙结点是指该点的所有子树中的全部结点。也就是说，树中除根结点以外的所有结点都是根结点的子孙结点。
4. 兄弟结点： 同一个结点的子结点互为兄弟结点。
5. 结点的层次、高度和树的高度： 结点的层次，也称为深度，是从根结点到这个结点所经过的边数。一棵树中结点的最大层次称为树的高度或深度。结点的高度指的是以该结点为根的子树的高度。
6. 有序树和无序树： 若将树中每个结点的子树看成自左向右有序的，则称该树为有序树，否则称为无序树。在有序树中，最左边的子树称为第一棵子树，最右边的子树称为最后一棵子树。
7. 森林： M棵互不相交的树的集合称为森林。显然，删去了一棵树的根，其子树的集合就形成了一片森林。

树的运算

1. 建树create()：创建一棵空树
2. 清空clear()：删除树中的所有结点
3. 判空IsEmpty()：判别是否为空树
4. 求树的规模size()：统计树上的结点数
5. 找根结点root()：找出树的根结点值；如果树是空树，则返回一个特殊值
6. 找父结点parent(x)：找出结点xx的父结点值；如果x不存在或x是根结点，则返回一个特殊值
7. 找子结点child(x,i)：找结点x的第i个子结点值; 如果x不存在或x的第i个儿子不存在，则返回一个特殊值
8. 剪枝remove(x,i)：删除结点x的第i棵子树
9. 遍历traverse()：访问树上的每一个结点

树的抽象类

template
class tree {
public:
    virtual void clear() = 0;
    virtual bool isEmpty() const = 0;
    virtual int size() = 0;
    virtual T root(T flag) const = 0;
    virtual T parent(T x, T flag) const = 0; 
    virtual T child（T x, int i, T flag) const = 0;
    virtual void remove(T x, int i) = 0;
    virtual void traverse() const = 0;
    virtual ~tree() {}
};

二叉树的定义 二叉树的概念

• 二叉树（Binary Tree）是结点的有限集合，它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又都是二叉树。
  • 注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换一棵二叉树的左右子树后得到的是另一棵二叉树。

• 满二叉树
  • 一棵高度为k并具有 2 k － 1 2^k－1 2k－1个结点的二叉树称为满二叉树。
• 完全二叉树
  • 在满二叉树的最底层自右至左依次(注意：不能跳过任何一个结点)去掉若干个结点得到的二叉树也被称之为完全二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
  • 特点：
    • 所有的叶结点都出现在最低的两层上。
    • 对任一结点，如果其右子树的高度为k，则其左子树的高度为k或k＋1。

二叉树的基本操作

• 建树create()：创建一棵空的二叉树
• 清空clear()：删除二叉树中的所有结点
• 判空IsEmpty()：判别二叉树是否为空树
• 求树的规模size()：统计树上的结点数
• 找根结点root()：找出二叉树的根结点值；如果树是空树，则返回一个特殊值
• 找父结点parent(x)：找出结点x的父结点值；如果x不存在或x是根，则返回一个特殊值
• 找左孩子lchild(x)：找结点x的左孩子结点值；如果x不存在或x的左儿子不存在，则返回一个特殊值
• 找右孩子rchild(x)：找结点x的右孩子结点值；如果x不存在或x的右儿子不存在，则返回一个特殊值
• 删除左子树delLeft(x)：删除结点x的左子树
• 删除右子树delRight(x)：删除结点x的右子树
• 前序遍历preOrder()：前序遍历二叉树上的每一个结点
  • 如果二叉树为空，则操作为空；否则：
    • 访问根结点
    • 前序遍历左子树
    • 前序遍历右子树
• 中序遍历midOrder()：中序遍历二叉树上的每一个结点
  • 如果二叉树为空，则操作为空；否则：
    • 中序遍历左子树
    • 访问根结点
    • 中序遍历右子树
• 后序遍历postOrder()：后序遍历二叉树上的每一个结点
  • 如果二叉树为空，则操作为空；否则：
    • 后序遍历左子树
    • 后序遍历右子树
    • 访问根结点
• 层次遍历levelOrder()：层次遍历二叉树上的每个结点
  • 先访问根结点，然后按从左到右的次序访问第二层的结点。在访问了第k层的所有结点后，再按从左到右的次序访问第k+1层。以此类推，直到最后一层。

我们可以通过前序＋中序遍历确定一棵二叉树：

• 找出根结点，区分左右子树
• 继续对左右子树重复这个过程
• 右子树只有根结点
• 找出左子树的前序、中序序列

二叉树抽象类

template
class bTree {
public:
    virtual void clear() = 0;
    virtual bool isEmpty() const = 0;
    virtual int size() const = 0;
    virtual T Root(T flag) const = 0;
    virtual T parent(T x， T flag) const = 0; 
    virtual T lchild（T x, T flag) const = 0;
    virtual T rchild（T x, T flag) const = 0;
    virtual void delLeft(T x) = 0;
    virtual void delRight(T x) = 0;
    virtual void preOrder() const = 0;
    virtual void midOrder() const = 0;
    virtual void postOrder() const= 0;
    virtual void levelOrder() const = 0;
    virtual bTree() {}
};

二叉树的性质

二叉树有以下性质：

1. 一棵非空二叉树的第 i 层上最多有 2 i − 1 2^{i - 1} 2i−1个结点 （ i ≥ 1 ） （i geq 1） （i≥1）。
   • 可以用数学归纳法证明。
2. 一棵高度为k的二叉树，最多具有 2 k － 1 2^k－1 2k－1个结点。
   • 根据性质1可以推断得到。
3. 对于一棵非空二叉树，如果叶子结点数为 n 0 n_0 n0​，度数为2的结点数为 n 2 n_2 n2​，则有: n 0 ＝ n 2 ＋ 1 n_0＝n_2＋1 n0​＝n2​＋1成立。
4. 具有n个结点的完全二叉树的高度为 k = ⌊ l o g 2 n ⌋ + 1 k = lfloor log_{2}n rfloor + 1 k=⌊log2​n⌋+1
5. 非常有用：如果对一棵有n个结点的完全二叉树中的结点按层自上而下（从第1层到第 ⌊ l o g 2 n ⌋ + 1 lfloor log_{2}n rfloor +1 ⌊log2​n⌋+1层），每一层按自左至右依次编号。若设根结点的编号为1。则对任一编号为i的结点 ( 1 ≤ i ≤ n ) (1≤i≤n) (1≤i≤n),有：
   • 如果 i ＝ 1 i＝1 i＝1，则该结点是二叉树的根结点；如果 i > 1 i>1 i>1，则其父亲结点的编号为 ⌊ i 2 ⌋ lfloor frac{i}{2} rfloor ⌊2i​⌋。
   • 如果 2 i > n 2i > n 2i>n，则编号为i的结点为叶子结点，没有儿子；否则，其左儿子的编号为 2 i 2i 2i。
   • 如果 2 i + 1 > n 2i + 1 > n 2i+1>n，则编号为i的结点无右儿子；否则，其右儿子的编号为 2 i + 1 2i+1 2i+1。

二叉树的顺序存储

二叉树可以顺序存储或者链接存储。

顺序存储的概念

顺序存储就是用数组存储二叉树。

• 完全二叉树的顺序存储：按层编号把层次关系映射到线性关系。
• 非完全二叉树的顺序存储：将普通的树修补成完全二叉树，按层编号把层次关系映射到线性关系，用特殊的值表示“假”结点。

顺序存储的特点

• 浪费空间，比如极端情况：只有右儿子。
• 因此一般只用于一些特殊的场合，如静态的并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。

练习

顺序存储二叉树的节点数量统计

现有一棵根节点为1且按照顺序存储的完全二叉树。我们已知完全二叉树的最后一个结点是n。我们想知道，以结点m为根节点，其所在的子树中一共包括多少个结点。

输入描述：

一行两个整数n m。

对于100%的数据满足 1 ≤ m ≤ n ≤ 1 0 5 1 ≤ m ≤ n ≤ 10^5 1≤m≤n≤105。

输出描述：

输出一行，该行包含一个整数，表示结点m所在子树中包括的结点的数目。

示例 1：

输入：
7 3
输出：
3

代码：

#include 

using namespace std; 

int n, m, ans;

void getAns(int pos) {
    ans++;
    if (pos * 2 <= n)
        getAns(pos * 2);
    if (pos * 2 + 1 <= n)
        getAns(pos * 2 + 1);
    return;
}

int main() {
    cin >> n >> m;
    getAns(m);
    cout << ans;
    return 0;
}

二叉树的链接存储

二叉树的链接存储有两种方式。

• 二叉链表 指出儿子结点：类似单链表。

• 三叉链表 同时指出父亲和儿子结点：类似双链表。
  

由于在二叉树中很少存在通过儿子找父亲的操作，所以我们常使用二叉链表进行存储，二叉链表也被称作二叉树的标准存储方式。

练习

子树的大小

有一棵有n个结点的二叉树，节点编号为1 ~ n，已知所有结点的左右子节点和根节点的编号r，现在我们想知道每个节点所在的子树中一共包括多少个结点。

对于100%的数据满足 1 ≤ r ≤ n ≤ 1 0 5 1 ≤ r ≤ n ≤ 10^5 1≤r≤n≤105。

输入描述：

第一行两个整数n r，分别表示节点的数量和根节点的编号。

接下来n行，每行两个整数，第i行表示节点i的左右子树，若为0则表示为空。

输出描述：

n行，每行一个整数，第i行表示以结点i为根节点，其所在的子树中一共包括多少个结点。

示例 1：

输入：
5 1
2 3
4 5
0 0
0 0
0 0
输出：
5
3
1
1
1

代码：

#include 

#define N 100010

using namespace std; 

int lson[N], rson[N], val[N];

void getAns(int pos) {
    if (lson[pos])
        getAns(lson[pos]);
    if (rson[pos])
        getAns(rson[pos]);
    val[pos] = val[lson[pos]] + val[rson[pos]] + 1;
    return;
}

int main() {
    int n, r;
    cin >> n >> r;
    for (int i = 1; i <= n; i++)
        cin >> lson[i] >> rson[i];
    getAns(r);
    for (int i = 1; i <= n; i++)
        cout << val[i] << endl;
    return 0;
}

二叉树链表类设计 二叉链表的概念和设计

1. 数据成员设计

由两个类组成:

• 结点类：
  • 数据成员：数据及左右孩子的指针。
  • 结点的操作包括：构造和析构
  • 是树类的私有内嵌类
• 二叉树类：
  • 数据成员：指向根结点的指针

2. 成员函数设计

• 实现抽象类规定的所有函数；
• 二叉树是递归定义，所以操作可用递归实现：
  • 递归函数必须有一个控制递归终止的参数；
  • 每个需要递归实现的公有成员函数对应一个私有的、带递归参数的成员函数；
  • 公有函数调用私有函数完成相应的功能；
• 有些操作需要先找到某个结点的地址。
  • 增设一个私有成员函数find

二叉链表类定义

template
class binaryTree : public bTree {
    friend void printTree(const binaryTree &t, T flag);
    private:
        struct Node {                          //二叉树的结点类
            Node  *left , *right ;               
            T data;                         
            Node() : left(NULL), right(NULL) { }
            Node(T item, Node *L = NULL, Node * R =NULL) : data(item), left(L), right(R) { }
            ~Node() {} 
        };
        Node *root;
    public:
        // 创造空二叉树
        binaryTree() : root(NULL) {}
        // 创造只有根结点的二叉树
        binaryTree(T x) { root = new Node(x); }
        ~binaryTree()  { clear() ; }
        void clear() ;
        bool isEmpty() const{return root == NULL;}
        int size() const;
        T Root(T flag) const;
        T lchild(T x, T flag) const;
        T rchild(T x, T flag) const; 
        void delLeft(T x) ;
        void delRight(T x);
        void preOrder() const;
        void midOrder() const;
        void postOrder() const;
        void levelOrder() const;
        void createTree(T flag);
    private:
        Node *find(T x, Node *t ) const;
        // 同名公有函数递归调用以下函数实现
        void clear(Node *&t);
        int size(Node *t) const; 
        void preOrder(Node *t) const;
        void midOrder(Node *t) const;
        void postOrder(Node *t) const;
}; 

二叉链表成员函数实现

• root函数的实现
  • 返回root指向的结点的数据部分。如果二叉树是空树，则返回一个特殊的标记。

template 
T binaryTree::Root(T flag) const {
    if (root == NULL) return flag;
    else return root->data;
}

• size函数的实现
  • 一棵二叉树由三部分组成：根结点、左子树、右子树。
  • 树 的 结 点 数 = 左 子 树 结 点 数 + 右 子 树 结 点 数 + 1 树的结点数 = 左子树结点数 + 右子树结点数 + 1 树的结点数=左子树结点数+右子树结点数+1
  • 计算左右子树的结点数需要递归调用本函数

template
int binaryTree::size(binaryTree::Node *t) const {
    if (t == NULL) return 0;
    else return size(t->left) + size(t->right) + 1;
}

template
int binaryTree::size() const {
    return  size(root);
} 

• clear函数的实现
  • 一棵二叉树由三部分组成：根结点、左子树、右子树。
  • 删 除 一 棵 树 = 删 除 左 子 树 + 删 除 右 子 树 + 删 除 根 删除一棵树 = 删除左子树 + 删除右子树 + 删除根 删除一棵树=删除左子树+删除右子树+删除根
  • 删除左右子树需要递归调用本函数

template
void binaryTree::clear(binaryTree::Node *&t) {
    if (t == NULL)  return;
    clear(t->left);
    clear(t->right);
    delete t;
    t = NULL;
}

template
void binaryTree::clear() {
    clear(root);
} 

• 前序遍历的实现
  • if （空树） return;
  • 访问根结点；
  • 前序遍历左子树；
  • 前序遍历右子树；

template
void binaryTree::preOrder(binaryTree::Node *t) const { 
    if (t == NULL) return;
    cout << t->data << ' ';
    preOrder(t->left);
    preOrder(t->right);
}

template
void binaryTree::preOrder()  const { 
    cout << "n前序遍历：";
    preOrder(root);
}

• 中序遍历的实现
  • if （空树） return;
  • 中序遍历左子树；
  • 访问根结点；
  • 中序遍历右子树；

template
void binaryTree::midOrder (binaryTree::Node *t) const {
    if (t == NULL) return;
    midOrder(t->left);
    cout << t->data << ' ';
    midOrder(t->right);
}

template
void binaryTree::midOrder() const {  
    cout << "n中序遍历：";
    midOrder(root);
}

• 后序遍历的实现
  • if（空树）return;
  • 访问根结点；
  • 后序遍历左子树；
  • 后序遍历右子树；

template
void binaryTree::postOrder (binaryTree::Node *t) const {
    if (t == NULL) return;
    postOrder(t->left);	
    postOrder(t->right);
    cout << t->data << ' ';
}

template
void binaryTree::postOrder() const {  
    cout << "n后序遍历：";
    postOrder(root);	
}

• 层次遍历的实现
  • 访问过程
    • 根节点
    • 根节点的儿子
    • 根节点的儿子的儿子
  • 关键问题
    • 如何储存已经可以被访问的结点
    • 使用队列
  • 工作过程：

根结点入队
While（队列非空） {
    出队并访问
    将儿子入队
}

template
void binaryTree::levelOrder() const {
    linkQueue< Node * > que;
    Node *tmp;
    
    cout << “n层次遍历：”;
    que.enQueue(root);	
    while (!que.isEmpty()) {
        tmp = que.deQueue();
        cout << tmp->data << ' ';
        if (tmp->left)
            que.enQueue(tmp->left);
        if (tmp->right)
            que.enQueue(tmp->right);
    }
}

• find的实现
  • 如何找结点x：遍历，可以采用任一种遍历
  • 工作过程：采用前序遍历

if (根结点是x) 返回根结点地址
tmp = 左子树递归调用find函数
if (tmp不是空指针) return tmp;
else return 对右子树递归调用find的结果

binaryTree::Node *binaryTree::find(T x, binaryTree::Node *t) const {
    Node *tmp;
    if (t == NULL) return NULL;
    if (t->data == x) return t;   
    if (tmp = find(x, t->left) ) return tmp;
    else return find(x, t->right);
}

• lchild的实现
  • 返回结点x的left值

template 
T binaryTree::lchild(T x, T flag) const {
    Node * tmp = find(x, root);

    if (tmp == NULL || tmp->left == NULL)
        return flag;
    
    return tmp->left->data;
}

• rchild的实现
  • 返回结点x的right值

template 
T binaryTree::rchild(T x, T flag) const {
    Node * tmp = find(x, root);

    if (tmp == NULL || tmp->right == NULL)
        return flag;

    return tmp->right->data;
}

• delLeft的实现
  • 对左子树调用clear函数删除左子树，然后将结点x的left置为NULL。

template 
void binaryTree::delLeft(T x) {
    Node *tmp = find(x, root);

    if (tmp == NULL) return;
    clear(tmp->left);
}

• delRight的实现
  • 对右子树调用clear函数删除右子树，然后将结点x的right置为NULL。

template 
void binaryTree::delLeft(T x) {
    Node *tmp = find(x, root);

    if (tmp == NULL) return;
    clear(tmp->left);
}

• createTree创建一棵树
  • 创建过程
    • 按层次遍历输入结点
    • 先输入根结点；对已输入的每个结点，依次输入它的两个儿子的值。如果没有儿子，则输入一个特定值

template 
void BinaryTree::createTree(Type flag) { 
    linkQueue que;
    Node *tmp;
    Type x, ldata, rdata;

    cout << "n输入根结点：";
    cin >> x;
    root = new Node(x);
    que.enQueue(root);
    while (!que.isEmpty()) {
        tmp = que.deQueue();
        cout << "n输入" << tmp->data   << "的两个儿子(" << flag   << "表示空结点)：";
        cin >> ldata >> rdata;
        if (ldata != flag)
            que.enQueue(tmp->left = new Node(ldata));
        if (rdata != flag)   
            que.enQueue(tmp->right = new Node(rdata));
    }
    cout << "create completed!n";
}

• printTree输出一棵树
  • 以层次遍历的次序输出每个结点和它的左右孩子

template 
void printTree(const binaryTree &t, T flag) {
    linkQueue q;

    q.enQueue(t.root->data);
    cout << endl;
    while (!q.isEmpty()) {
        char p, l, r;
        p = q.deQueue();
        l = t.lchild(p,  flag);
        r = t.rchild(p,  flag);
        cout << p << "  " << l  << "  " << r << endl;
        if (l != flag) q.enQueue(l);
        if (r != flag) q.enQueue(r);
    }
     que.enQueue(tmp->right = new Node(rdata));
    }
    cout << "create completed!n";
}

• printTree输出一棵树
  • 以层次遍历的次序输出每个结点和它的左右孩子

template 
void printTree(const binaryTree &t, T flag) {
    linkQueue q;

    q.enQueue(t.root->data);
    cout << endl;
    while (!q.isEmpty()) {
        char p, l, r;
        p = q.deQueue();
        l = t.lchild(p,  flag);
        r = t.rchild(p,  flag);
        cout << p << "  " << l  << "  " << r << endl;
        if (l != flag) q.enQueue(l);
        if (r != flag) q.enQueue(r);
    }
}