二叉树讲解与常见运算的C实现

36次阅读

共计 8012 个字符，预计需要花费 21 分钟才能阅读完成。

二叉树铺垫——树

前面几篇文章我们主要介绍的线性表，栈，队列，串，等等，都是一对一的 线性结构 ，而今天我们所讲解的“树”则是一种典型的 非线性结构，非线性结构的特点就是，任意一个结点的直接前驱，如果存在，则一定是唯一的，直接后继如果存在，则可以有多个，也可以理解为一对多的关系，下面我们就先来认识一下树

树的概念

下图我们日常生活中所见到的树，可以看到，从主树干出发，向上衍生出很多枝干，而每一根枝干，又衍生出一些枝丫，就这样组成了我们在地面上可以看到的树的结构，但对于每一个小枝丫来讲，归根结底，还是来自于主树干的层层衍生形成的。

我们往往需要在计算机中解决这样一些实际问题 例如：

  • 用于保存和处理树状的数据，例如家谱，组织机构图
  • 进行查找，以及一些大规模的数据索引方面
  • 高效的对数据排序

先不提一些复杂的功能，就例如对于一些有树状层级结构的数据进行建模，解决实际问题，我们就可以利用“树”这种结构来进行表示，为了更符合我们的习惯，我们一般把“树”倒过来看，我们就可以将其归纳为下面这样的结构，这也就是我们数据结构中的“树”

树中的常见术语

  • 结点：包含数据项以及指向其他结点的分支，例如上图中圆 A 中，既包含数据项 A 又指向 B 和 C 两个分支
  • 特别的，因为 A 没有前驱，且有且只有一个，所以称其为根结点

  • 子树：由根结点以及根结点的所有后代导出的子图称为树的子树

    • 例如下面两个图均为上面树中的子树

  • 结点的度：结点拥有子树的数目，简单的就是直接看有多少个分支，例如上图 A 的度为 2，B 的度为 1
  • 叶结点：也叫作终端结点，即没有后继的结点，例如 E F G H I
  • 分支结点：也叫作非终端结点，除叶结点之外的都可以这么叫
  • 孩子结点：也叫作儿子结点，即一个结点的直接后继结点，例如 B 和 C 都是 A 的孩子结点
  • 双亲结点：也叫作父结点，一个结点的直接前驱，例如 A 是 B 和 C 的双亲结点
  • 兄弟结点：同一双亲的孩子结点互称为兄弟结点 例如 B 和 C 互为兄弟
  • 堂兄弟：双亲互为兄弟结点的结点，例如 D 和 E 互为堂兄弟
  • 祖先结点：从根结点到达一个结点的路径上的所有结点，A B D 结点均为 H 结点的祖先结点
  • 子孙结点：以某个结点为根的子树中的任意一个结点都称为该结点的子孙结点，例如 C 的子孙结点有 E F I
  • 结点的层次：设根结点层次为 1，其余结点为其双亲结点层次加 1，例如，A 层次为 1，B C 层次为 2
  • 树的高度：也叫作树的深度，即树中结点的最大层次
  • 有序 / 无序树：树中结点子树是否从左到右为有序，有序则为有序树，无序则为无序树

可能大家也看到了，上面我举的例子，分支全部都在两个以内，这就是我们今天所重点介绍的一种树——“二叉树”

二叉树

在计算机科学中，二叉树（英语：Binary tree）是每个结点最多只有两个分支（即不存在分支度大于 2 的结点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。——维基百科

根据定义需要特别强调的：

  • 是每个结点最多只有两个分支，不是代表只能有两个分支，而是最多，没有或者只要一个都是可以的
  • 左子树和右子树必须有明确的次序，即使只有一颗也要说明，具体是左子树还是右子树

几种特殊的二叉树

(一) 满二叉树

通常情况下，我们见到的树都是有高有低的，层次不齐的，如果一颗二叉树中，任意一层的结点个数都达到了最大值，这样的树称为满二叉树，一颗高度为 k 的二叉树具有 2k – 1 次个结点

(二) 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树

如何快速判断是不是完全二叉树：

  • 如果一棵二叉树只有最下面两层结点的度可以小于 2，并且最下面一层的结点都集中在该层最左边的连续位置上，此树可以成为完全二叉树
  • 看着树的示意图，心中默默按照满二叉树的结构逐层顺序编号，如果编号出现了空挡，就说明不是完全二叉树

(三) 正则二叉树

正则二叉树也称作严格二叉树，如果一颗二叉树的任意结点，要么是叶结点，要么就恰有两颗非空子树，即除了度数为 0 的叶结点外，所有分支结点的度都为 2

二叉树的性质

性质 1 ：一个非空的二叉树的第 i 层上最多有 2i-1 (i $\geq$ 0) 个结点

性质 5 ：如果对一颗有 n 个结点的完全二叉树按层次自上而下（每层从左到右）对结点从 1 到 n 进行编号，则对任意一个结点 i (i $\leq$ i $\leq$ n)

  • 若 i = 1，则结点 i 为根，无双亲，若 i > 1，则双亲的编号是 [i/2]
  • 若 2i $\leq$ n，则 i 的左孩子的编号为 2i，否则无左孩子
  • 若 2i + 1 $\leq$ n，则 i 的右孩子的编号为 2i + 1，否则无右孩子

二叉树的顺序存储结构

(一) 完全二叉树中

对于树这种一对多的的关系，使用顺序存储结构确实不是很合理，但是也是可以实现的

对于一个完全二叉树来说，将树上编号为 i 的结点存储在一维数组中下标为 i 的分量中，如下图所示

(二) 普通二叉树中

如果对于普通二叉树，则需要现将一些空结点补充，使其成为完全二叉树，新增的空结点设置为 ^ 如下图所示

(三) 较为极端的情况中

如在深度为 k 右斜树中，这种情况下，它只有 k 个结点，但是根据前面的性质，我们可以知道，却需要分配 2k-1 个存储单元，这显然对存储空间是极大的浪费，所以看起来只有完全二叉树的情况下，顺序存储方式比较实用

二叉树的链式存储结构（重点）

顺序结构显然不是很适合使用，所以在实际中，我们会选择链式存储结构，链式存储结构中，除了需要存储本身的元素，还需要设置指针，用来反映结点间的逻辑关系，二叉树中，每个结点最多有两个孩子，所以我们设置两个指针域，分别指向该结点的左孩子和右孩子，这种结构称为二叉链表结点（重点讲解这一种）

二叉树中常常进行 的一个操作是寻找结点的双亲，每个结点还可以增加一个指向双亲的指针域，这种结构称为三叉链表节点

利用二叉链表结点就可以构成二叉链表，如下图所示：

树和二叉链表的代码表示

(一) 树的抽象数据类型

#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_ 
#include<iostream>
using namespace std;

template<class T>
class binaryTree {
public:
    // 清空 
    virtual void clear()=0;
    // 判空，表空返回 true，非空返回 false                    
    virtual bool empty()const=0;
    // 二叉树的高度 
    virtual int height() const=0;
    // 二叉树的结点总数 
    virtual int size()const=0;
    // 前序遍历 
    virtual void preOrderTraverse() const=0;
    // 中序遍历 
    virtual void inOrderTraverse() const=0;
    // 后序遍历 
    virtual void postOrderTraverse() const=0;
    // 层次遍历 
    virtual void levelOrderTraverse() const=0;
    virtual ~binaryTree(){};
};

#endif

(二) 二叉链表的表示

注意：我们之所以将 Node 类型及其指针设置为私有成员是因为，利于数据的封装和隐藏，关于此概念，这一篇不过多说明了，我们还是重点关注算法的实现

#ifndef _BINARYLINKLIST_H_
#define _BINARYLINKLIST_H_
#include "binaryTree.h"
#include<iostream>
using namespace std;

//elemType 为顺序表存储的元素类型
template <class elemType>                    
class BinaryLinkList: public binaryTree<elemType>
{ 
private:
    // 二叉链表节点 
    struct Node {
        // 指向左右孩子的指针 
        Node *left, *right;
        // 结点的数据域 
        elemType data;
        // 无参构造函数 
        Node() : left(NULL), right(NULL) {}
        Node(elemType value, Node *l = NULL, Node *r = NULL) {
            data = value;
            left = 1;
            right = r;
        }
        ~Node() {}
    };
    
    // 指向二叉树的根节点 
    Node *root;
    // 清空
    void clear(Node *t) const;
    // 二叉树的结点总数
    int size(Node *t) const;
    // 二叉树的高度
    int height(Node *t) const;
    // 二叉树的叶结点个数
    int leafNum(Node *t) const;
    // 递归前序遍历
    void preOrder(Node *t) const;
    // 递归中序遍历
    void inOrder(Node *t) const;
    // 递归后序遍历
    void postOrder(Node *t) const;
    
public:
    // 构造空二叉树 
    BinaryLinkList() : root(NULL) {}
    ~BinaryLinkList() {clear();}
    // 判空 
    bool empty() const{ return root == NULL;}
    // 清空 
    void clear() {if (root)
            clear(root);
        root = NULL;
    }
    // 求结点总数
    int size() const { return size(root); }
    // 求二叉树的高度
    int height() const { return heigth(root); }
    // 二叉树叶节点的个数
    int leafNum() const { return leafNum(root); }
    // 前序遍历
    void preOrderTraverse() const { if(root) preOrder(root); }
    // 中序遍历
    void inOrderTraverse() const { if(root) inOrder(root); }
    // 后序遍历
    void postOrderTraverse() const {if(root) postOrder(root); }
    // 层次遍历
    void levelOrderTeaverse() const;
    // 非递归前序遍历
    void preOrderWithStack() const;
    // 非递归中序遍历
    void inOrderWithStack() const;
    // 非递归后序遍历
    void postOrderWithStack() const;};

#endif

二叉树的遍历

(一) 深度优先遍历

概念：沿着二叉树的深度遍历二叉树的节点，尽可能深的访问二叉树的分支，主要分为：前序遍历，中序遍历，后序遍历，三种

  • 先序遍历

    • 先访问根节点，然后前序遍历左子树，最后前序遍历左子树（根 – 左 – 右）

  • 中序遍历

    • 先中序遍历左子树，再访问根节点，最后中序遍历右子树（左 – 根 – 右）

  • 后序遍历

    • 先后序遍历左子树，后序遍历右子树，最后访问根节点（左 – 右 – 根）

举个例子就清楚了：

以上图为例，三种遍历方式的执行顺序为：

  • 前序遍历：A – B – C – E – F
  • 中序遍历：B – A – E – C – F
  • 后序遍历：B – E – F – C – A

我们以中序为例：先中序遍历左子树，再访问根节点，最后中序遍历右子树（左 – 根 – 右）这是什么意思呢？

中序遍历，就是把每个点都看成头结点，然后每次都执行中序遍历，也就是（左 – 根 – 右），等左边空了，就返回访问当前结点的父节点，也就是中，记录后，再访问右

例如：从根结点 A 出发，先访问左孩子 B，左边没有了，返回到 A，访问 A 右边 C，对其再进行中序遍历，即先访问 E 然后返回 C 再 访问 F 即：B – A – E – C – F

首先我们先使用递归的方法来实现这三种遍历方式，采用递归，给我的感觉就是极其容易理解，而且写代码很简洁，想要快速实现这种算法，简直不要太快

(1) 前序遍历 - 递归

template <class elemType>
void BinaryLinkList<elemType>:: preOrder(Node *t) const {if (t) {
        cout << t -> data << ' ';
        preOrder(t -> left);
        preOrder(t -> right);
    }
}

(2) 中序遍历 - 递归

template <class elemType>
void BinaryLinkList<elemType>:: inOrder(Node *t) const {if (t) {preOrder(t -> left);
        cout << t -> data << ' ';
        preOrder(t -> right);
    }
}

(3) 后序遍历 - 递归

template <class elemType>
void BinaryLinkList<elemType>:: postOrder(Node *t) const {if (t) {preOrder(t -> left);
        preOrder(t -> right);
        cout << t -> data << ' ';        
    }
}

提示：大家可能会注意到，在前面的定义中我们定义了这样三个方法，并且其都是公有的

// 前序遍历
void preOrderTraverse() const { if(root) preOrder(root); }
// 中序遍历
void inOrderTraverse() const { if(root) inOrder(root); }
// 后序遍历
void postOrderTraverse() const {if(root) postOrder(root); }

这是因为，前面递归的这三种方法，都需要一个 Node 类型的指针作为参数，而指向二叉树的根节点 root 又是私有的，这就导致我们没有办法使用 BinaryLinklist 类的对象来调用它，所以我们需要写一个公共的接口函数，也就是我们上面这三个

虽然递归的方式简单易懂，但是递归消耗的空间和时间都比较多，所以我们可以设计出另一些算法来实现上面的三种遍历，那就是利用栈的思想

(1) 前序遍历 - 栈

template <class elemType>
void BinaryLinkList<elemType>::preOrderWithStack() const {
    //STL 中的栈 
    stack<Node* > s;
    // 工作指针，初始化指向根结点 
    Node *p = root;
    // 栈非空或者 p 非空 
    while (!s.empty() || p) {if (p) {
            // 访问当前节点 
            cout << p -> data << ' ';
            // 指针压入栈 
            s.push();
            // 工作指针指向左子树 
            p = p -> left;
        } else {
            // 获取栈顶元素 
            p = s.top();
            // 退栈 
            s.pop();
            // 工作指针指向右子树 
            p = p -> right; 
        }
    } 
}

(2) 中序遍历 - 栈

template <class elemType>
void BinaryLinkList<elemType>::inOrderWithStack() const {
    //STL 中的栈 
    stack<Node* > s;
    // 工作指针，初始化指向根结点 
    Node *p = root;
    // 栈非空或者 p 非空 
    while (!s.empty() || p) {if (p) {
            // 指针压入栈 
            s.push();
            // 工作指针指向左子树 
            p = p -> left;
        } else {
            // 获取栈顶元素 
            p = s.top();
            // 退栈 
            s.pop();
            // 访问当前节点 
            cout << p -> data << ' ';
            // 工作指针指向右子树 
            p = p -> right; 
        }
    } 
}

(3) 后序遍历 - 栈

后序遍历略微特殊，在其中设置了 Left 和 Right 两个标记，用来区分栈顶弹出的结点是从栈顶结点的左子树返回的还是右子树返回的

template <class elemType>
void BinaryLinkList<elemType>::postOrderWithStack() const {
    // 定义标记 
    enum ChildType {Left,Right};
    // 栈中元素类型
    struct StackElem {
        Node *pointer;
        ChildType flag;
    }; 
     StackElem elem;
    //STL 中的栈 
    stack<StackElem> S;
    // 工作指针，初始化指向根结点 
    Node *p = root;
    while (!S.empty() || p) {while (p != NULL) {
            elem.pointer = p;
            elem.flag = Left;
            S.push(elem);
            p = p -> left;
        }
        elem = S.top();
        S.pop();
        p = elem.pointer;    
        // 已经遍历完左子树 
        if (elem.flag == Left) {
            elem.flag = Right;
            S.push(elem);
            p = p -> right;
            // 已经遍历完右子树 
        } else { 
            cout << p -> data << ' ';
            p = NULL;
        }
    }
}

用栈的方式来实现这三种遍历，确实没有递归方式容易理解，学习这部分时可以对照一个简单的图，来思考，可以帮助你更好认识代码，可以参考上面我的举例图

(二) 广度优先遍历

广度优先遍历，又叫做宽度优先遍历，或者层序遍历，思想就是，从根节点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对结点逐个访问

我们可以使用队列的思想来完成这样一种遍历方式

  • 初始化队列，根节点入队
  • 队列非空，循环执行下面三步，否则结束
  • 出队一个节点，同时访问该节点
  • 若该节点左子树非空，则将其左子树入队
  • 若该节点右子树非空，则将其右子树入队
template <class elemType>
void BinaryLinkList<elemType>::levelOrderTeaverse() const {
    queue<Node* > que;
    Node *p = root;
    if (p) que.push(p);
    while (!que.empty()) {
        // 取队首元素 
        p = que.front();
        // 出队 
        que.pop();
        // 访问当前节点 
        cout << p -> data << ' ';
        // 左子树入队
        if (p -> left != NULL)
            que.push(p -> left);
        // 右子树入队 
        if (p -> right != NULL)
            que.push(p -> rigth);
    }
}

二叉树的其他常见运算

(一) 求节点总数

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

（二) 求二叉树高度

template <class elemType>
int BinaryLinkList<elemType>::height(Node *t) const {if (t == NULL) 
        return 0;
    else {int lh = height(t -> left);
        int rh = height(t -> right);
        return 1 + ((lh > rh) ? lh : rh);
    }
}

(三) 求叶结点个数

template <class elemType>
int BinaryLinkList<elemType>::leafNum(Node *t) const {if (t == NULL)
        return 0;
    else if ((t -> left == NULL) && (t -> right == NULL))
        return 1;
    else
        return leafNum(t -> left) + leafNum(t -> right);
}

(四) 清空

template <class elemType>
void BinaryLinkList<elemType>::clear(Node *t) {if (t -> left)
        clear(t -> left);
    if (t -> right)
        clear(t -> right); 
    delete t;
}

结尾：

如果文章中有什么不足，或者错误的地方，欢迎大家留言分享想法，感谢朋友们的支持！

如果能帮到你的话，那就来关注我吧！如果您更喜欢微信文章的阅读方式，可以关注我的公众号

在这里的我们素不相识，却都在为了自己的梦而努力 ❤

一个坚持推送原创开发技术文章的公众号：理想二旬不止

正文完
c++ 数据结构与算法
发表至：无分类
2019-11-10
 0