树

树（Tree）是n（n≥0）个结点的有限集合，当n=0时，为空树；n>0时，为非空树。任意一棵非空树，满足：

  1. 有且仅有一个称之为根的结点；
  2. 除根结点以外的其余结点可分为$m（m＞0）$个互不相交的有限集$T1, T2, …, Tm$, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
  • 节点：节点包含数据元素以及若干子树的分支信息
  • 节点的度：节点拥有的子树个数
  • 树的度：树中节点的最大度数
  • 终端节点：度为0的结点，又称为叶子
  • 分支节点：度大于0的节点。除了叶子都是分支结点
  • 内部节点：除了树根和叶子都是内部节点
  • 节点的层次：从根到该节点的层数（根节点为第一层）
  • 树的深度（高度）：所有节点中的最大层数

image-20200812155326876

  • 路径：树中两个结点之间的所经过的结点序列。
  • 路径长度：两结点之间路径上经过的边数。
  • 双亲、孩子：结点的子树的根称为该结点的孩子
  • 兄弟：双亲相同的结点互称兄弟。
  • 堂兄弟：双亲是兄弟的结点互称堂兄弟。小
  • 祖先：即从该结点到树根经过的所有结点，称为该结点的祖先。
  • 子孙：结点的子树中的所有结点都称为该结点的子孙。
  • 有序树：结点的各子树从左至右有序，不能互换位置。
  • 无序树：结点各子树可互换位置。
  • 森林：由m（m≥0）棵不相交的树组成的集合。

顺序存储

image-20200812160616355

链式存储

image-20200812160636782

树转换二叉树

孩子兄弟表示法：长子当作左孩子，兄弟关系向右斜。

image-20200812161213179

image-20200812161219387

二叉树还原树

image-20200812161239822

森林转换二叉树

image-20200812161258049

二叉树

二叉树（Binary Tree）是n（n≥0）个结点所构成的集合，它或为空树（n=0）；或为非空树。对于非空树T满足：

  1. 有且仅有一个称为根的结点；
  2. 除根结点以外，其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身都是二叉树。

二叉树的性质

  1. 在二叉树的第 i层上至多有 $2^{i-1}$个结点。
  2. 深度为k的二叉树至多有 $2^k-1$ 个结点。
  3. 对于任何一棵二叉树，若叶子数为$n_0$，度为2 的结点数为$n_2$，则$n_0=n_2+1$。
  4. 具有n个结点的完全二叉树的深度必为$(\log_2n)+1$.
  5. 对于完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为$2i$。其有孩子编号必为$2i+1$：其双亲的编号必为$i/2$。

满二叉树：一棵深度为k且有$2^k-1$ 个结点的二叉树。

完全二叉树：除了最后一层外，每一层都是满的（达到最大结点数），最后一层结点是从左向右出现的。

顺序存储

image-20200812162337056

补空法是指如果左子树或者右子树为空时，则用特殊字符补空，如’#’。然后按照先序遍历的顺序，得到先序遍历的序列，根据该序列递归床加你二叉树。

image-20200812162904787

补空法还原二叉树，代码实现：

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/**
 * 补空法创建二叉树
 */

typedef struct BTree {
  char val;
  struct BTree *left, *right;
} BNode, *BTree;

// 字符指针
int cur = 0;
int slen = 0;

BTree newBTree(char val) {
  BTree b = (BTree) malloc(sizeof(struct BTree));
  b->val = val;
  return b;
}

BTree buildBTree(char *s) {
  if(s[cur] == '#' || cur >= slen) {
    cur ++;
    return NULL;
  } else {
    BTree b = newBTree(s[cur]);
    cur ++;
    b->left = buildBTree(s);
    b->right = buildBTree(s);
    return b;
  }
}

void printBTree(BTree tree) {
  if(tree) {
    printf("%c\t", tree->val);
    printBTree(tree->left);
    printBTree(tree->right);
  }
}

int main(int argc, char *argv[])
{
  char *s = "ABD##E##CF#G###";
  slen = strlen(s);
  BTree b = buildBTree(s);
  printBTree(b);
  return 0;
}

链式存储

image-20200812162351611

二叉树的深度

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
#include <stdio.h>
#include <stdlib.h>

/**
 * 补空法创建二叉树
 */

typedef struct BTree {
  int val;
  struct BTree *left, *right;
} BNode, *BTree;

BTree newBTree(int val) {
  BTree b = (BTree) malloc(sizeof(struct BTree));
  b->val = val;
  return b;
}

int depth(BTree tree) {
  int m, n;
  if(tree == NULL) {
    return 0;
  }
  m = depth(tree->left);
  n = depth(tree->right);
  return (m>n?m:n)+1;
}

int main(int argc, char *argv[])
{
  BTree t1 = newBTree(1);
  BTree t2 = newBTree(1);
  BTree t3 = newBTree(1);
  BTree t4 = newBTree(1);

  t1->left = t2;
  t2->left = t3;
  t3->left = t4;

  printf("%d \n", depth(t1));
  printf("%d \n", depth(t2));
  printf("%d \n", depth(t3));
  printf("%d \n", depth(t4));
  return 0;
}

二叉树的叶子数和节点数

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
54
#include <stdio.h>
#include <stdlib.h>

/**
 * 补空法创建二叉树
 */

typedef struct BTree {
  int val;
  struct BTree *left, *right;
} BNode, *BTree;

BTree newBTree(int val) {
  BTree b = (BTree) malloc(sizeof(struct BTree));
  b->val = val;
  return b;
}

// 求二叉树的叶子
int leafCount(BTree tree) {
  if(tree == NULL) {
    return 0;
  }
  if(tree->left == NULL && tree->right == NULL) {
    return 1;
  }
  return leafCount(tree->left) + leafCount(tree->right);
}

int nodeCount(BTree tree) {
  if(tree == NULL) {
    return 0;
  }
  return nodeCount(tree->left) + nodeCount(tree->right) + 1;
}

int main(int argc, char *argv[])
{
  BTree t1 = newBTree(1);
  BTree t2 = newBTree(1);
  BTree t3 = newBTree(1);
  BTree t4 = newBTree(1);

  t1->left = t2;
  t2->left = t3;
  t3->left = t4;

  printf("leafCount: %d \n", leafCount(t1));
  printf("leafCount: %d \n", leafCount(t2));

  printf("nodeCount: %d \n", nodeCount(t1));
  printf("nodeCount: %d \n", nodeCount(t2));
  return 0;
}

二叉树的遍历

按照根的访问顺序不同，根在前面称为先序遍历（DLR），根在中间称为中序遍历（LDR），根在最后称为后序遍历（LRD）。

  1. 先序遍历：先访问根节点，然后先序遍历左子树，再先序遍历右子树
  2. 中序遍历：先中序遍历左子树，然后访问根节点，再中序遍历右子树
  3. 后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点

二叉树的遍历，代码实现：

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <stdio.h>
#include <stdlib.h>

/**
 * 补空法创建二叉树
 */

typedef struct BTree {
  int val;
  struct BTree *left, *right;
} BNode, *BTree;

// 实现队列
typedef struct Queue {
  void* val;
  struct Queue *next;
} *Queue;

Queue initialQueue() {
  Queue q = (Queue) malloc(sizeof(Queue));
  if(!q) return NULL;
  q->next = NULL;
  return q;
}

int isEmpty(Queue q) {
  return q->next == NULL;
}

void enQueue(Queue q, void* val) {
  Queue p = q;
  while(p->next) {
    p = p->next;
  }
  Queue elem = (Queue) malloc(sizeof(Queue));
  elem->val = val;
  p->next = elem;
}

void deQueue(Queue q) {
  if(!isEmpty(q)) {
    Queue temp = q->next;
    q->next = temp->next;
    free(temp);
  }
}

void* getHead(Queue q) {
  if(isEmpty(q)) {
    printf("queue is empty.\n");
    return NULL;
  }
  return q->next->val;
}

BTree newBTree(int val) {
  BTree b = (BTree) malloc(sizeof(struct BTree));
  b->val = val;
  return b;
}

// 先序遍历
void preorder(BTree tree) {
  if(tree) {
    printf("%d ", tree->val);
    preorder(tree->left);
    preorder(tree->right);
  }
}

// 中序遍历
void inorder(BTree tree) {
  if(tree) {
    inorder(tree->left);
    printf("%d ", tree->val);
    inorder(tree->right);
  }
}

// 后序遍历
void posorder(BTree tree) {
  if(tree) {
    posorder(tree->left);
    posorder(tree->right);
    printf("%d ", tree->val);
  }
}

// 层次遍历
void levelTraverse(BTree tree) {
  if(!tree) {
    return;
  }
  Queue qe = initialQueue();
  enQueue(qe, tree);
  BTree p;
  while(!isEmpty(qe)) {
    p = getHead(qe);
    deQueue(qe);
    printf("%d ", p->val);
    if(p->left) enQueue(qe, p->left);
    if(p->right) enQueue(qe, p->right);
  }
}

int main(int argc, char *argv[])
{
  BTree t1 = newBTree(1);
  BTree t2 = newBTree(2);
  BTree t3 = newBTree(3);
  BTree t4 = newBTree(4);
  BTree t5 = newBTree(5);
  BTree t6 = newBTree(6);
  BTree t7 = newBTree(7);

  t1->left = t2;
  t1->right = t3;
  t2->left = t4;
  t2->right = t5;
  t3->left = t6;
  t3->right = t7;

  printf("先序遍历: ");
  preorder(t1);
  printf("\n中序遍历: ");
  inorder(t1);
  printf("\n后序遍历: ");
  posorder(t1);
  printf("\n层次遍历: ");
  levelTraverse(t1);
  printf("\n");
  return 0;
}

先序遍历和中序遍历还原二叉树

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <stdlib.h>

/**
 * 补空法创建二叉树
 */

typedef struct BTree {
  char val;
  struct BTree *left, *right;
} BNode, *BTree;

BTree newBTree(char val) {
  BTree b = (BTree) malloc(sizeof(struct BTree));
  b->val = val;
  return b;
}

// 先序遍历
void preorder(BTree tree) {
  if(tree) {
    printf("%c ", tree->val);
    preorder(tree->left);
    preorder(tree->right);
  }
}

// 中序遍历
void inorder(BTree tree) {
  if(tree) {
    inorder(tree->left);
    printf("%c ", tree->val);
    inorder(tree->right);
  }
}

// 后序遍历
void posorder(BTree tree) {
  if(tree) {
    posorder(tree->left);
    posorder(tree->right);
    printf("%c ", tree->val);
  }
}

// 先序遍历和中序遍历还原二叉树
BTree preMidRestore(char *pre, char *mid, int len) {
  if(len == 0) return NULL;
  // 先序遍历中的第一个节点
  char ch = pre[0];
  int index = 0;
  // 中序遍历中找到根节点的左边为左孩子，右边为右孩子
  while(mid[index] != ch) {
    index ++;
  }
  BTree tree = newBTree(ch);
  tree->left = preMidRestore(pre+1, mid, index);
  tree->right = preMidRestore(pre+index+1, mid+index+1, len-index-1);
  return tree;
}

int main(int argc, char *argv[])
{
  char *pre = "1245367";
  char *mid = "4251637";
  BTree tree = preMidRestore(pre, mid, 7);
  preorder(tree);
  return 0;
}

中序遍历和后序遍历还原二叉树

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>

/**
 * 补空法创建二叉树
 */

typedef struct BTree {
  char val;
  struct BTree *left, *right;
} BNode, *BTree;

BTree newBTree(char val) {
  BTree b = (BTree) malloc(sizeof(struct BTree));
  b->val = val;
  return b;
}

// 先序遍历
void preorder(BTree tree) {
  if(tree) {
    printf("%c ", tree->val);
    preorder(tree->left);
    preorder(tree->right);
  }
}

// 中序遍历
void inorder(BTree tree) {
  if(tree) {
    inorder(tree->left);
    printf("%c ", tree->val);
    inorder(tree->right);
  }
}

// 后序遍历
void posorder(BTree tree) {
  if(tree) {
    posorder(tree->left);
    posorder(tree->right);
    printf("%c ", tree->val);
  }
}

// 中序遍历和后序遍历还原二叉树
BTree midPosRestore(char *mid, char *pos, int len) {
  if(len == 0) return NULL;
  // 先序遍历中的第一个节点
  char ch = pos[len-1];
  int index = 0;
  // 中序遍历中找到根节点的左边为左孩子，右边为右孩子
  while(mid[index] != ch) {
    index ++;
  }
  BTree tree = newBTree(ch);
  tree->left = midPosRestore(mid, pos, index);
  tree->right = midPosRestore(mid+index+1, pos+index, len-index-1);
  return tree;
}

int main(int argc, char *argv[])
{
  char *mid = "4251637";
  char *pos = "4526731";
  BTree tree = midPosRestore(mid, pos, 7);
  preorder(tree);
  printf("\n");
  inorder(tree);
  return 0;
}