树
TIP
本笔记尚未修改
- 结合向量和列表的特性,兼顾动态与静态操作。向量的 search 成本较低,insert 和 remove 成本较高,列表恰恰相反。
- path from root to v = path v
- subtree rooted at v = subtree v
- 深度和高度:
- 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
时为满二叉树
用二叉树描述多叉树
长子兄弟表现法。
二叉树实现
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
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
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
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
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
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
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
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
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
重构
- 定义:通过一棵树的先序、中序或后序遍历序列还原出一棵树的拓扑结构。
- 真二叉树:度数(孩子数)为0或2。
- (先序|后序)+ 中序
- (先序+后序)x 真二叉树