站点图标

考研数据结构 03 树与二叉树 – 基础内容

Morning

一、树的基本概念

1.1 基本术语

  基本概念已经清晰明了，下面回顾下常用的术语。

  1. 高度与深度：对于某个节点来说，其深度从根节点向下到当前节点累加；其高度从当前节点向上累加到根节点。二者同一。这里对空树的高度/深度记录有0和-1两种（只有根节点的数则是1和0），具体情况具体选择。
  2. 父节点与子节点：不言自明。
  3. 节点的度：一个节点的子节点数。
  4. 树的度：树中最大的（节点的）度。
  5. 层次：不言自明。
  6. 有序树：对于任意子树，其根节点为b。b的左子树a的所有节点总小于b，b的右子树c的所有节点总大于b。排序准则自定。
  7. 路径和路径长度：值得注意的是，被计算的两个节点不能跨树。
  8. 森林：一棵树没有了根节点，则是多颗互不相交的树，则是森林。

1.2 性质

  1. 树数中的节点树等于所有节点的度数+1，人话：子节点自己本身的计数总是被递归到父节点上去，称为“度”。
  2. 度为m的树中第i层上至多有mi-1个节点(i>=1)，人话：欲证明，全放第二层试试。
  3. 高度为h的m叉树至多有(mh-1)/(m-1)个节点。
  4. 具有n个节点的m叉树的最小高度为logm(n(m-1)+1)。

二、二叉树

2.1 定义与主要特性

  二叉树是另一种树形结构，其特显是每个节点至多只能有两个子树，并且二叉树有左右之分。

  特别的二叉树：

  1. 满二叉树：高度为h，且节点为2h-1个节点的二叉树，其中每一层都有最多的节点，处叶节点外每个节点的度均为2。
  2. 完全二叉树：不满的满二叉树。在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2n+1。深度为k的完全二叉树，至少有2k-1个节点，至多有2k-1个节点。
  3. 二叉排序树：对于任意子树，其左节点总小于右节点，排序准则自定。
  4. 平衡二叉树：树上任意一个节点左右子树深度差不超过1。

2.2 存储结构

struct BinaryNode
{
    eleType ele;
    BinaryNode* left;
    BinaryNode* right;
}

2.3 遍历

2.3.1 先序遍历

  1. 访问根节点
  2. 先序遍历左子树
  3. 先序遍历右子树
void preOrder(BinaryNode* node)
{
    if (node)
    {
        visit(node);
        preOrder(node->left);
        preOrder(node->right);
    }
}

2.3.2 中序遍历

  1. 中序遍历左子树
  2. 访问根节点
  3. 中序遍历右子树
void inOrder(BinaryNode* node)
{
    if (node)
    {
        inOrder(node->left);
        visit(node);
        inOrder(node->right);
    }
}

2.3.3 后序遍历

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根节点
void postOrder(BinaryNode* node)
{
    if (node)
    {
        postOrder(node->left);
        postOrder(node->right);
        visit(node);
    }
}

2.3.4 层次遍历

void levelOrder(BinaryNode* root)
{
    if (!root)  return;

    // 队列
    std::deque<BinaryNode*> qu;

    // 将根节点放入队列
    qu.push_back(root);

    // while (队列不空)
    while (!qu.empty())
    {
        // 队首出列，访问之。
        BinaryNode* head = qu.front();
        qu.pop_front();
        visit(head);

        // 若有左节点，压入队列；
        if (head->left)  qu.push_back(head->left);

        // 若有右节点，压入队列。
        if (head->right)  qu.push_back(head->right);        
    }
}

2.4 由遍历构造二叉树

2.4.1 由后序和中序遍历构造二叉树

  现在我们有如下例子：

2.4.1.1 算法描述
  1. 通过后序遍历确定根节点A。
  2. 在中序中确定A的左右子树：
    中序：BFD A EGC
    后序：FDB GEC A
  3. 对每个子树重复以上直到每个子树只有一个根节点

  上树的最终结果：

图1：由中序和后序确定先序

图1：由中序和后序确定先序[/caption]
2.4.1.2 C++代码

  代码实现，由后序和中序确定先序遍历。

#include <iostream>
#include <string>
#include <queue>
using namespace std;

class BinaryTree
{
private:
    struct BinaryNode
    {
        char element;
        BinaryNode* left;
        BinaryNode* right;

        BinaryNode() { element = '\0'; left = NULL; right = NULL; }
    };

    BinaryNode* root;
    string pre;
    string::const_iterator it_pre;

    void Creat_in_pos(BinaryNode*& t, string in, string pos)
    {
        if (in.size() == 0 || pos.size() == 0)  //安全检查
        {
            return;
        }

        t = new BinaryNode; //开辟新空间
        if (root == NULL)
        {
            root = t;
        }

        string::const_iterator back = pos.end() - 1;
        t->element = *back;  //在后序输入中找到当前树的根:A
        string left_in, right_in;   //确定左右子树的中序输入

        string::const_iterator it_in = in.begin();  //在当前树的中序输入中寻找A的位置
        for (; it_in != in.end(); ++it_in)
        {
            if (*it_in == t->element)
            {
                break;
            }
        }

        //substr的参数;(起点,个数)/size_t;
        left_in = in.substr(0, it_in - in.begin()); //切分左子树
        right_in = in.substr(it_in - in.begin() + 1, in.end() - it_in); //切分右子树
        string left_pos, right_pos; //确定左右子树的后序输入
        left_pos = pos.substr(0, left_in.size());
        right_pos = pos.substr(left_in.size(), right_in.size());

        Creat_in_pos(t->left, left_in, left_pos);    //递归创建
        Creat_in_pos(t->right, right_in, right_pos);
        return;
    }

    void Traverse_pre(BinaryNode* t)const
    {
        if (t == NULL)
        {
            return;
        }
        cout << t->element;
        Traverse_pre(t->left);
        Traverse_pre(t->right);
        return;
    }

public:
    BinaryTree() { root = NULL; }

    void Creat_in_pos(const string& in, const string& pos)
    {
        Creat_in_pos(root, in, pos);
        return;
    }

    void Traverse_pre()
    {
        Traverse_pre(root);
    }
};

int main()
{
    string in, pos;
    cin >> in >> pos;
    BinaryTree a;
    a.Creat_in_pos(in, pos);
    a.Traverse_pre();
    return 0;
}

2.4.2 由先序和中序遍历构造二叉树

  同样是上面那个例子：

2.4.2.1 算法描述
  1. 通过先序遍历确定根节点A。
  2. 在中序中确定A的左右子树：
    中序：BFD A EGC
    先序：BDF CEG A
  3. 对每个子树重复以上直到每个子树只有一个根节点
2.4.2.2 C++代码

  代码实现，由先序和中序确定后序遍历。

#include <iostream>
#include <string>
#include <queue>
using namespace std;

class BinaryTree
{
private:
    struct BinaryNode   //二叉树的节点
    {
        char element;
        BinaryNode* left;
        BinaryNode* right;

        BinaryNode()    //节点的初始化
        {
            element = '\0';
            left = NULL;
            right = NULL;
        }
    };

    BinaryNode* root;   //二叉树的根
    string pre; //先序遍历
    string::const_iterator it_pre;

    void creat_in_pre(BinaryNode*& t, string in, string pre)
    {
        if (in.size() == 0 || pre.size() == 0)
        {
            return;
        }
        t = new BinaryNode;
        if (root == NULL)
        {
            root = t;
        }

        string::const_iterator it_root;
        it_root = pre.begin();
        t->element = *it_root;

        string left_in, right_in;
        string::const_iterator it_in = in.begin();  //通过中序遍历来确定根的左右子树
        for (; it_in != in.end(); ++it_in)
        {
            if (*it_root == *it_in)
            {
                break;
            }
        }

        left_in = in.substr(0, it_in - in.begin());
        right_in = in.substr(it_in - in.begin() + 1, in.size());
        string left_pre, right_pre;
        left_pre = pre.substr(1, left_in.size());
        right_pre = pre.substr(left_in.size() + 1, right_in.size());

        creat_in_pre(t->left, left_in, left_pre);
        creat_in_pre(t->right, right_in, right_pre);
        return;
    }

    void traverse_pos(BinaryNode* t)const
    {
        if (t == NULL)
        {
            return;
        }
        traverse_pos(t->left);
        traverse_pos(t->right);
        cout << t->element;
        return;
    }

public:
    BinaryTree()    //二叉树的初始化
    {
        root = NULL;
    }

    void creat_in_pre(const string& _in, const string& _pre)
    {
        creat_in_pre(root, _in, _pre);
        return;
    }

    void traverse_pos()
    {
        traverse_pos(root);
    }
};

int main()
{
    BinaryTree tree;
    string a, b;
    cin >> a >> b;
    tree.creat_in_pre(a, b);
    tree.traverse_pos();

    return 0;
}

三、线索二叉树

  线索二叉树定义如下：

“一个二叉树通过如下的方法“穿起来”：所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。”

图2：线索二叉树

  线索二叉树能线性地遍历二叉树，从而比递归的 中序遍历更快。使用线索二叉树也能够方便的找到一个节点的父节点，这比显式地使用父亲节点指针或者栈效率更高。这在栈空间有限，或者无法使用存储父节点的栈时很有作用（对于通过深度优先搜索来查找父节点而言)。 考虑这样的例子：一个节点k有一个右孩子r，那么r的左指针可能是指向一个孩子节点，或是一个指回k的线索。如果r有左孩子，这个左孩子同样也应该有一个左孩子或是指回k的线索。对于所有的左孩子同理。因此沿着这些从r发出的左指针，我们最终会找到一个指回k的线索。这种特性是对称的：当q是p的左孩子时，我们可以沿着q的右孩子找到一个指回p的线索。

  传统的二叉树一般都是以链式存储的结构来表示。这样，二叉树中的每个节点都可以用链表中的一个链节点来存储，每个链节点就包含了若干个指针。但是，这种传统的链式存储结构只能表现出二叉树中节点之间的父子关系，而且不能利用空余的指针来直接得到某个节点的在特定的遍历顺序（先序，中序，后序）中的直接前驱和直接后继。通过分析传统的二叉树链式存储结构表示的二叉树中，存在大量的空闲指针。若能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针，则可以进行某些更方便的运算。这些被重新利用起来的空指针就被称为线索，加上了这些线索的二叉树就是线索二叉树。

  线索二叉树的结构描述：

struct Node
{
    eleType data;
    Node* left, right;
    int ltag, rtag;

    /*
    ltag = 0,   左子节点
         = 1,   节点的前驱
    rtag = 0,   右子节点
         = 1,   节点的后驱
    */

    Node()
    {
        left = right = nullptr;
        ltag = rtag = 0;
    }
}

3.1 通过中序遍历构造线索二叉树

// 参数，当前节点，中序前驱节点
void Threaded(Node* p, Node* pre)
{
    if (!p) return;

/* ===== Section I : 递归构建左子树 ===== */
    Threaded(p->left, pre);

/* ===== Section II : 中序处理当前节点 ===== */

    // 建立当前节点的前驱
    if (!p->left)
    {
        p->left = pre;
        p->ltag = 1;
    }

    // 建立前驱节点的后继
    if ((pre) && (!p->right))
    {
        pre->right = p;
        pre->rtag = 1;
    }

    pre = p;

/* ===== Section III : 递归构建右子树 ===== */
    // 递归构建右子树
    Threaded(p->left, right);
}

int main()
{

    Node* root;
    // ...一系列操作...
    // 现在我们已经有一个**非空**二叉树，其根节点为root，我们对其进行线索化

    Node* pre = nullptr;
    Threaded(root, pre);

    // 处理遍历的最后一个节点
    pre->right = nullptr;
    pre->rtag = 1;

    return 0;
}

3.2 中序遍历

void Node* leftMost(Node* node)
{
    if (!node) return nullptr;

    while (node->left)
    {
        node = node->left;
    }

    return node;
}

void inOrder(Node* root)
{
    Node* pCur = leftMost(root);

    while (pCur)
    {
        visti(pCur);

        if (pCur->rtag)
        {
            pCur = pCur->right;
        }
        else
        {
            pCur = leftMost(pCur->right);
        }
    }
}

四、树和森林

4.1 树的存储结构

  现在我们有一棵树，如图所示。

图3：树

  现在我们尝试用三种方法来表示它。

4.1.1 双亲表示法（数组）

id data parent
0 R -1
1 A 0
2 B 0
3 C 0
4 D 1
5 E 1
6 F 3
7 G 6
8 H 6
9 K 6

  这种方法利用了每个节点（除根）只有一个父节点的特性，可以很快得到节点的父节点，但求子节点时需要遍历整个表。

4.1.2 孩子表示法

  改种方法将每个节点的孩子节点用单链表串起来形成一个线性结构。即，用vector<Node*>之类的结构来存放子节点。

4.1.3 孩子兄弟表示法

  又称为二叉树表示法，即以二叉链表作为树的存储结构。每个节点包含三部分内容：节点值、指向节点第一个孩子的指针、指向节点下一个兄弟节点的指针。

struct Node
{
    eleType data;
    Node* child, next;
}

4.2 树、森林与二叉树的转换

  这里只讨论树和二叉树的“画法”的转换，因为孩子兄弟表示法本身从结构上已经满足二叉树的结构了。

  1. 用孩子兄弟表示法表示树。
  2. 顺时针旋转45°。

  其他的转换同理。

退出移动版