数据结构——树

本文最后更新于：Saturday, August 22nd 2020, 3:22 pm

1、树的相关术语

  1. 度：一个结点的子结点数目。树的度指度数最大的那个结点的度

  2. 叶结点，分支结点

    度为0的结点——叶结点；度大于0的结点——分支结点

  3. 结点的层数

    (1) root(T)——层数为0

    (2)其余结点层数为前驱结点层数 + 1

  4. 路径

    同时满足$V_{i+1} $是$V_i$ （m <=i<=m+k-1)的子结点,则称结点序列为$V_m$ 到 $V_{m+1}$ 的路径。该路径经历的边数k称为路径长度

  5. 子孙结点、祖先结点

    一棵树中若存在结点$V_m$ 到$V_n$的路径，则称为$V_n$是$V_m$的子孙结点,为$V_n$是$V_m$的祖先结点。

  6. 树的高度

    树中结点的最大层数。

2、二叉树引理

  1. 设T为n个结点构成的二叉树，其中叶子节点个数为n~0~，度为2的结点个数为n~2~,则有:

    证明：

  1. 满二叉树和完全二叉树

    满二叉树：每一层都充满了结点，一颗非空高度为k的满二叉树，有$2^{k+1}+1$个结点。

    完全二叉树：只有最后一层不满，其余层全是满的。且最后一层从最左边开始填充。

    mark

  2. 若将n个结点的完全二叉树按层次顺序从1开始编号，则对编号为i(1 <= i <= n)的结点有：

    1. 若 i $\neq$ = 1,则编号为i的结点父节点编号为$\left \lfloor i/2 \right \rfloor$
    2. 若 2i $\leq$ n, 则编号为i的结点左孩子编号为2i,否则无左孩子
    3. 若 2i+1 $\leq$ n, 则编号为i的右孩子编号为2i + 1,否者无有孩子。
    4. 推论：一棵具有n个结点的完全二叉树，分支结点个数为$\left \lfloor n/2 \right \rfloor$。(最后一个结点n的父节点为$\left \lfloor n/2 \right \rfloor$)

    mark

  3. 具有n个结点的完全二叉树高度为$\left \lfloor log_2n \right \rfloor$

    证明：

3、二叉树递归遍历

  1. 先根遍历(Preorder Traversal)

    1
    2
    3
    4
    5
    Preorder(t)
    IF t = NULL Then return.
    print(data(t)).				// 直接打印出根，然后往左找
    Preorder(left(t))
    Preorder(right(t))

  2. 中根遍历(Inorder Traversal)

    1
    2
    3
    4
    5
    Inorder( t )
    IF t = NULL Then return.
    INorder(left(t))
    print(data(t))
    INorder(right(t))

  3. 后根遍历(Postorder Traversal)

    1
    2
    3
    4
    5
    Postorder( t )
    IF t = NULL Then return.
    Postorder(left(t))
    Postorder(right(t))
    print(data(t))

    4、二叉树非递归遍历

1、先根遍历

策略：

  1. 一直往左走，只要不为空就访问，访问完进栈。当为空时弹栈，访问右子树。
  2. 进栈的是访问结点的右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
create(S);p = root(t)		// 创建一个辅助栈,辅助指针p指向根t。
while(true) 				// 一直循环，直到栈为空
{
	while(p)				// 当p不为空，访问它，把它压栈或者它右子树压栈
	{
		process(p.data);
		S.push(p) or S.push(p.right);
		p = p.left;
	}
	if(S.empty()) return;	// 循环出口。
	p = S.pop();			// 出栈
	p = p.right;			// 如果是压的右子树，这一步省略
}

2、中根遍历

策略：一直往走，中途结点全部压入栈。直到左子树为空，出栈访问，把右子树压栈。然后继续。

1
2
3
4
5
6
7
8
9
10
11
12
13
creat(S);p=root(T);
while(true)
{
 while(p)
    {
        S.push(p);
        p = p.left;
    }
    if(S.empty()) return;
    p = S.pop();
    process(p);				// 处理出栈的最左边结点
    p = p.right;			// 续上开头，现在p.right相当于root
}

3、二叉树的形态

中根和先根算法进出栈的顺序是一样的。进栈序列：先根序列;出栈序列:中根序列

假设先根序列为1…n时，有多少种中跟序列就有多少种二叉树形态。(中根+先根唯一确定一棵树)

即n个数有多少种出栈方式:

4、后根遍历

策略：

  1. 一直往左走，压栈。如果遇到右子树为空或者右子树已经遍历过了就出栈访问它。否者就访问右子树。开始新的遍历。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    Create(S); p = root(T);pre=NULL		//pre存储p之前访问过的结点。
      while(true)
      {
          while(p)
          {
              S.push(p);
              p = p.left;
          }
          if(S.empty) return;
          p = peak(S);
          if(p.right == NULL or p.right == pre)
          {
              S.pop();
              process(p.data);
              pre = p;					//始终记录上一次访问过的结点
              p = NULL;					//为了下一个循环中去父节点的右结点。
          }
          else p = p.right;
      }

    mark

  2. 允许多次进出栈。栈元素为二元组（结点，标号i)

    i = 1 ：没有访问结点的任何子树。准备遍历其左子树

    i = 2 ：遍历完左子树，准备遍历右子树

    i = 3：遍历完右子树

    初始化：（root(T), 1)压入栈。弹栈，判断出栈元素标号：

    i = 1, 则将(p, 2) 压栈，准备遍历左子树。把（left(p), 1)压栈

    i = 2, 则将(p, 3)压栈，准备遍历右子树，即把（right(p),1)压栈

    i = 3, 访问结点p

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    create(S);S.push((root(T),1));
    while(!S.isempty())
    {
    	(p,i) = S.pop();
        if(p)					// 防止空指针
        {
            if(i == 1)
            {
                S.push((p,2));
                S.push((p.left, 1));
            }
            if(i == 2)
            {
                S.push((p,3));
                S.push((p.right,1));
            }
            else
            {
                process(p.data)
            }
        }
    }

5、层次遍历

1
2
3
4
5
6
7
8
9
create(Q);
if(root(T)) Q.enqueue(T);			//先将头结点入队
while(!Q.empty)
{
    p = Q.dequeue();
    process(p.data);				//取头结点访问
    if(p.left) Q.enqueue(p.left);	 //如果左节点不空，加入(先进先出)
    if(p.right) Q.enqueue(p.right);
}

由中根遍历 + （层次/先根/后根）唯一确定一棵树

5、二叉树相关应用

1、搜索给定结点的父节点

1
2
3
4
5
6
7
8
Father(t,p.q)

if(p == NULL or p==t) return NULL;
if(t.left ==p or t.right == p) return t;
// return Father(t.left, p) || Fathre(t.right, p)
q = Father(t.left,p);
if(q) return q;
else return Father(t.right, p)

2、释放二叉树

1
2
3
4
5
6
Del(p)

if(p == NULL) return;
Del(p.left);
Del(p.right);
free(p);			// 后续遍历删除，从后往前删。

3、删除一颗小树

删除给定结点以及其左右子树

1
2
3
4
5
6
7
8
9
10
11
12
DILR(t,p)

if(!p) return;		// 为空
if(p == t)
{
	Del(p);
    t = NULL		//删除整棵树 t还有定义，可以再赋值。
}
q = Father(t,p);
if(q.left == p) q.left = NULL;		//修改原来指向p的指针为空
if(q.right == p) q.right == NULL;
Del(p);

4、创建二叉树

由于先根序列不能体现左右子树为空的情况，所有用#表示空子结点。则可以唯一表示一课树。

mark

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
递归算法（CreateBinTree)(简称为CBT)
输入：包含空指针的先根序列
输出：根指针t

算法CBT(.t)
p = getchar();
if(p == "\n" || p == "#") 
{
    t = NULL;			// 指针置为空。即#代表空指针
 	return t;			// 递归出口
}
t = create(p);
t->left = CBT(.t);
t->right = CBT(.t);		// 建立左右子树
return t;


Treeptr createbigtree(void)
{
	char p;
	Treeptr t;
	p = getchar();
	if(p == '\n' || p == '#') 
	{
	    t = NULL;
	    return t;
	}
	t = createtree(p);
	t->left = createbigtree();
	t->right = createbigtree();
	return t;
}

5、复制一颗二叉树

1
2
3
4
5
6
7
8
9
Treeptr copybigtree(Treeptr sample)
{
    if(sample) return NULL;						// 递归出口
    Treeptr t = createtree(sample->data);		// 复制根
    t->left = copybigtree(sample->left);		// 复制左子树
    t->right = copybigtree(sample->right);      // 复制右子树
    return t;
}

6、后序遍历求结点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
算法 Count(t.n)
if t=^  then (n <-- 0.return.)
Count(left(t).nl).
COunt(right(t).nr).
n <-- nl+nr+1.|
    
    
/* 利用后续遍历计算二叉树结点数 */
int Countnode(Treeptr p)
{
    if(p == NULL) return 0;
    return Countnode(p->left) + Countnode(p->right) + 1;
}

7、计算二叉树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
算法 depth(t.h)
if t=^ then(d <-- -1. return.)
else
(
	depth(left(t).d1).
	depth(right(t).d2).
	if(d1>d2) then d <-- d1+1.
	else d <-- d2+1.
)|

int depthtree(Treeptr p)
{
    if(!p) return -1;
    int ld = depthtree(p->left);
    int rd = depthtree(p->right);
    return ld>rd ? ld+1:rd +1;
}

8、二叉树首尾结点

先, 中, 后（不使用递归，不适应栈）
先根序列第一个结点

后根序列第一个结点

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
/**************** 中根序列 ********************/
---------------------第一个结点(最左边的结点)
if(t==NULL) then return NULL;
p = t;
while(p->left) p = p->left;
return p;

----------------------最后一个结点（最右边的结点）
if(t==NULL) then return NULL;
p = t;
while(p->right) p = p->right;
return p;
    
/***************** 先根序列 **********************/
-----------------------第一个结点（即根）
return t;

-----------------------最后一个结点(往右找第一个叶结点，找不到往左再重复上一步操作)
if(t==NULL) then return NULL;
p = t;
while(p)
{
    if(p->right) p = p->right;
    else if(p->left) p = p->left;	//不能往右就往左一步
    else return p					// 无路可走就是他了
}

/******************* 后根序列 ***********************/
-------------------------第一个结点(往左找第一个叶结点，找不到往左一步再重复上一步)
if(t==NULL) then return NULL;
p = t;
while(p)
{
    if(p->left) p = p->left;
    else if(p->right) p = p->right;
    else return p;
}
CS Data Structure
C

本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议 。转载请注明出处！