Little Data Structure

树

TIP

本笔记尚未修改

  • 结合向量和列表的特性，兼顾动态与静态操作。向量的 search 成本较低，insert 和 remove 成本较高，列表恰恰相反。
  • path from root to v = path v
  • subtree rooted at v = subtree v
  • 深度和高度： Tree Depth Height
  • connected：没有落单的节点 node，节点之间均有路径。
  • acyclic：不含闭环 loop
  • path(v, r) = path(v)：每个节点均有一个值表示其与根 root 的距离（路径长度）。
  • 每个节点 node 具有信息：
    • parent：父节点的 rank
    • data
    • rank
    • firstChild()
    • nextSibling()

二叉树 Binary Tree

  • 节点度数不超过 2 的树，即每个节点最多只有两个孩子
  • 节点度数 h：除了叶子（没有孩子的节点）外的层数。
  • 节点总数 n：h < n < h+1
  • n = h+1时为单链
  • n = 2^h+1 -1时为满二叉树

用二叉树描述多叉树

长子兄弟表现法。 First Child Sibling Method

二叉树实现

BinNode 二叉树节点模版类

#define BinNodePosi(T) BinNode<T> *
template <typename T>
typedef enum{ RB_RED, RB_BLACK } RBColor;
struct BinNode
{
    BinNodePosi(T) parent, lc, rc;
    T data;
    int height;
    int npl; //Null Path Length 左式堆
    RBColor color;

    //构造函数
    BinNode(): parent(NULL), lc(NULL), rc(NULL), height(0), npl(1), color(RB_RED){} //默认构造函数
    BinNode(T e, BinNodePosi(T) p = NULL,  BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL, int h = 0, int l = 1, RBColor c = RB_RED): data(e), parent(p), lc(lc), rc(rc), height(h), npl(l), color(c){}
    
    //操作接口
    int size();
    BinNodePosi(T) insertAsLeftChild(T const &);
    BinNodePosi(T) insertAsRightChild(T const &);
    BinNodePosi(T) succ();  //直接后继
    template <typename VST>
    void travLevel(VST &);
    template <typename VST>
    void travPre(VST &);
    template <typename VST>
    void travIn(VST &);
    template <typename VST>
    void travPost(VST &);
};


template <typename T>
BinNodePosi(T) BinNode<T>::insertAsLeftChild(T const &e)
{
    return lChild = new BinNode(e, this);
}

template <typename T>
BinNodePosi(T) BinNode<T>::insertAsRightChild(T const &e)
{
    return rChild = new BinNode(e, this);
}

template <typename T>
int BinNode<T>::size()
{
    int s = 1;
    if (lc)
        s += lc->size();
    if (rc)
        s += rc->size();
    return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

BinTree模版类

#include "BinNode.h"
template <typename T>
class BinTree
{
protected:
    int _size;
    BinNodePosi(T) _root;
    virtual int updateHeight(BinNodePosi(T) x);
    void updateHeightAbove(BinNodePosi(T) x);

public:
    //constructor and destructor
    BinTree() : _size(0), _root(NULL) {}
    ~BinTree() :
    {
        if (_size > 0)
            remove(_root);
    }

    int size() const { return _size; }
    bool empty() const { return !_root; }
    BinNodePosi(T) root() const { return _root; }
    BinNodePosi(T) insertAsRoot(T const &e);
    BinNodePosi(T) insertAsLC(BinNodePosi(T) x, T const &e); //e作为x的左孩子接入
    BinNodePosi(T) insertAsRC(BinNodePosi(T) x, T const &e);
};

template <typename T>
int BinTree<T>::updateHeight(BinNodePosi(T) x)
{
    return x->height = 1 + max(stature(x->lChild), stature(x->rChild));
}

template <typename T>
void BinTree<T>::updateHeightAbove(BinNodePosi(T) x)
{
    while ((x->parent) && stature(x->parent) != updateHeight(x->parent))
    {
        x = x->parent;
    }
}

template <typename T>
BinNodePosi(T) BinTree<T>::insertAsRC(BinNodePosi(T) x, T const &e)
{
    _size++;
    x->insertAsRChild(e);
    updateHeightAbove(x);
    return x->rChild;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

遍历

  • 先序、中序、后序，preorder/inorder/postorder, 这个先中后是指vector（root）相对于左右孩子的位置。
  • 尾递归的遍历形式可以改写为迭代。

先序遍历

v|l|r

递归式先序遍历

#define BinNodePosi(T) BinNode<T> *
template <typename T, typename VST> //元素类型、操作器
void trav_pre(BinNodePosi(T) x, VST &visit)
{
    if (!x)
        return;
    visit(x->data);
    trav_pre(x->lChild, visit);
    trav_pre(x->rChild, visit);
} //T(n) = O(1) + T(a) + T(n-a-1) = O(n)
1
2
3
4
5
6
7
8
9
10
  • 尾递归可以转化为迭代形式

迭代式先序遍历

#define BinNodePosi(T) BinNode<T> *
template <typename T, typename VST> //元素类型、操作器
void travPre_I1(BinNodePosi(T) x, VST &visit)
{
    if (!x)
        return;
    Stack<BinNodePosi(T)> s;
    s.push(x);
    while(!s.empty()){
        x = s.pop();
        visit(x->data);
        if(x->rChild) s.push(x->rChild);
        if(x->lChild) s.push(x->lChild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 观察后发现，实际是沿左侧链访问，再沿右孩子上行。
  • 构思：直接访问左侧节点，将右节点存入栈中，将来逆序出栈。
#define BinNodePosi(T) BinNode<T> *
template <typename T, typename VST>
static void visitAlongLeftBranch(BinNodePosi(T) x, VST &visit, Stack<BinNodePosi(T)> &s)
{
    while (x)
    {
        visit(x->data);
        if (x->rChild){
            s.push(x->rChild);
        }
        x = x->lChild;
    }
}

template <typename T, typename VST> //元素类型、操作器
void travPre_I2(BinNodePosi(T) x, VST &visit)
{
    if (!x)
        return;
    Stack<BinNodePosi(T)> s;
    while (true)
    {
        visitAlongLeftBranch(x, visit, s);
        if (s.empty())
            break;
        x = s.pop();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

中序遍历

  • l|v|r

递归式中序遍历

#define BinNodePosi(T) BinNode<T> *
template <typename T, typename VST> //元素类型、操作器
void travPre(BinNodePosi(T) x, VST &visit)
{
    if (!x)
        return;
    travPre(x->lChild, visit);
    visit(x->data);
    travPre(x->rChild, visit);
} //T(n) = O(1) + T(a) + T(n-a-1) = O(n)
1
2
3
4
5
6
7
8
9
10

迭代式中序遍历

  • 从根节点开始沿左侧链下行，一边将节点存入栈中。无法下行时访问栈首元素，然后转入其右子树。栈空时遍历完成。
#define BinNodePosi(T) BinNode<T> *
template <typename T, typename VST>
static void goAlongLeftBranch(BinNodePosi(T) x, Stack<BinNodePosi(T)> &s)
{
    while (x)
    {
        s.push(x);
        x = x->lChild;
    }
}

template <typename T, typename VST> //元素类型、操作器
void travPre_I1(BinNodePosi(T) x, VST &visit)
{
    if (!x)
        return;
    Stack<BinNodePosi(T)> s;
    while (true)
    {
        goAlongLeftBranch(x, s);
        if (s.empty())
            break;
        x = s.pop();
        visit(x->data);
        x = x->rChild;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

后序遍历

  • lrv
  • 尽可能沿左分支，实在不得已才沿右分支。从最左边的叶子开始遍历：先把同一层的左子树遍历完再遍历右子树和父节点。
  • 实现：如果栈顶元素不为空，如果有右孩子，先存右孩子再存左孩子。弹出栈顶的空节点。
template <typename T>
static void gotoLeftMostLeaf(Stack<BinNodePosi(T)> &s)
{
    while (BinNodePosi(T) x = s.top())
    {
        if (HasLChild(*x))
        {
            if (HasRChild(*x))
                s.push(x->rChild);
            s.push(x->lChild);
        }
        else
            s.push(x->rChild);
    }
    s.pop(); //弹出栈顶的空节点
}

template <typename T, typename VST>
void travPost_I(BinNodePosi(T) x, VST &visit)
{
    Stack<BinNodePosi(T)> s;
    if (x)
        s.push(x);
    while (!s.empty())
    {
        if (s.top() != x->parent)  //如果栈顶元素不是当前节点的父节点
            gotoLeftMostLeaf(s);  //说明当前节点有右节点
        x = s.pop();
        visit(x->data);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

层次遍历

template <typename T, typename VST>
void BinNode<T>::travLevel(VST &visit)
{
    Queue<BinNodePosi(T)> Q;
    Q.enqueue(this);
    while (!Q.empty())
    {
        BinNodePosi(T) x = Q.dequeue();
        visit(x->data);
        if (x->lChild)
            Q.enqueue(x->lChild);
        if (x->rChild)
            Q.enqueue(x->rChild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

重构

  • 定义：通过一棵树的先序、中序或后序遍历序列还原出一棵树的拓扑结构。
  • 真二叉树：度数（孩子数）为0或2。
  • （先序｜后序）+ 中序
  • （先序+后序）x 真二叉树
Last Updated: 2021/11/22 03:17:18
Contributors: oddnaveed