关于树和二叉树的题目的若干技巧

二叉树的创建常用的写法

把需要插入的数据存储在数组中,然后再把他们使用insert函数一个个插入到二叉树中,并最终返回根节点指针root

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
#include <queue>
#include <cstdio>
#define NULL 0
struct node
{
int data;
struct node* lchild;
struct node* rchild;
};
//insert函数将在二叉树中插入一个数据域为x的新节点
//注意根节点指针root要使用引用,否则插入不会成功
void insert(node* &root , int x)
{
if(root == NULL)
{
root = new node;
root->data =x;
root->lchild = root->rchild = NULL;
return ;
}
if(由二叉树的性质,x应该插在左子树)
{
insert(root->lchild ,x);
}
else
{
insert(root->rchild ,x );
}
}
//创建二叉树
node *Create(int data[] , int n)
{
node* root = new node;
root->data = data[0];
root->lchild = root->rchild = NULL;
for(int i = 1 ; i < n ; ++i)
{
insert(root , data[i]);
}
return root;
}

关于数组表示下的二叉树结构的性质

  1. 数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列
  2. 判断某个节点是否为叶子节点的标志为:该节点(记为root)的左子节点的编号root * 2大于节点总个数n
  3. 判断某个节点是否为空节点的标志为:该节点的下标root大于节点的总个数n

层序遍历的典型代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LayerOrder(node* root)
{
queue<node*> q;
q.push(root);
while(!q.empty())
{
node* now == q.front();
q.pop();
printf("%d" , now->data);
if(now->lchild != NULL)
q.push(now->lchild);
if(now->rchild != NULL)
q.push(now->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
struct node
{
int data;
int layer;
node* lchild;
node* rchild;
} ;
void LayerOrder(node* root)
{
queue<node*> q;
root->layer = 1;
q.push(root);
while(!q.empty())
{
node* now = q.front();
q.pop();
printf("%d" , now->data);
if(now->lchild)
{
now->lchild->layer = now->layer+1;
q.push(now->lchild);
}
if(now->rchild)
{
now->rchild->layer = now->layer+1;
q.push(now->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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#define MAX 1000
#define NULL 0
struct node
{
int data;
node* lchild;
node* rchild;
};
int pre[MAX] , in[MAX];
void findRoot(int[] in , int x)
{
for(int i = 0 ; i < MAX ; ++i)
{
if(x == in[i])
return i;
}
return -1;
}
void createTree(node* root , int begin , int end , int[] pre , int[] in)
{
root = new node;
root->data = pre[0];
root->lchild = NULL;
root->rchild = NULL;
index = findRoot(in , root->data);
if(index != begin)//此处应当检测是否存在左子树序列
createTree(root->lchild , begin , index-1 , pre , in);
if(index != end)//检测是否存在右子树序列
createTree(root->rchild , index+1 , end , pre , in);
}
node* create(int preL , int preR , int inL , int inR)
{
if(preL > preR)//临界条件
{
return NULL;
}
node* root = new node;
root->data = pre[preL];
int k;
for(k = inL ; k <= inR ; k++)
{
if(in[k] == pre[preL])
break;
}
int numLeft = k - inL;//左子树的节点个数
//左子树的先序区间是[pre+1 , preL+numLeft] , 中序区间是[inL , k-1]
//返回左子树根节点地址,赋值给root的左指针
root->lchild = create(preL+1 , preL+numLeft , inL , k-1);
//同理
root->rchild = create(preL+numLeft+1 , preR , k+1 , inR);
return root;
}

树的遍历

子节点个数不限,且子节点没有先后次序的树

树的静态写法

1
2
3
4
5
struct node
{
int data;
int child[maxn];
}Node[maxn];

由于子节点数目的不可预知性,且用maxn会超过空间限制,所以最好使用vector

1
2
3
4
5
struct node
{
int data;
vector child;
}Node[maxn];

当需要建立一个节点的时候,就按顺序从数组中取出一个下标即可,例如:

1
2
3
4
5
6
int index = 0;
int newNode()
{
Node[index].child.clear()//清空子节点
return ++index;
}

树的先根遍历

1
2
3
4
5
6
7
8
void preOrder(int root)//递归边界的巧妙
{
printf("%d" , Node[root].data);
for(int i = 0; i < Node[root].child.size() ; ++i)
{
preOrder(Node[root].child[i]);
}
}

树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void LayerOrder(int root)
{
queue<int> Q;
Q.push(root);
while(!Q.empty())
{
int top = Q.front();
printf(" %d " , Node[top].data);
Q.pop();
for(int i = 0 ; i < Node[top].child.size() ; ++i)
{
Q.push(Node[top].child[i]);
}
}
}

同样的。如果需要对节点的层号进行求解,只需要在结构体中加一个layer变量即可

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
struct node
{
int data;
int layer;
vector<int> child;
}Node[maxn];
//从而层序遍历如下
void LayerOrder(int root)
{
queue<int> Q;
Q.push(root);
Node[root].layer = 1;
while(!Q.empty())
{
int top =Q.front();
printf("%d" , Node[top].data);
Q.pop();
for(int i =0 ; i < Node[top].child.size(); ++i)
{
int child = Node[top].child[i];//当前节点的第i个子节点的编号
Node[child].layer = Node[top].layer+1;
Q.push(child);
}
}
}

从树的遍历看DFS和BFS:

  1. 对于所有的DFS问题,都可以将其化成树的形式,DFS就相当于对树进行的先根遍历
  2. 对于所有的BFS问题,都可以将其化成树的形式,此时相当于对树进行层序遍历

二叉查找树

首先明确:二叉查找树是一颗有序的二叉树

1
2
3
4
5
6
struct node
{
int data;
node* lchild;
node* rchild;
};

查找操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void search(node* root , int x)
{
if(root == NULL)
{
printf("search failed\n");
return;
}
if(x == root->data)
printf("%d\n" , root->data);
else if(x < root->data)
search(root->lchild , x);
else if(x > root->data)
search(root->rchild , x);
}

插入操作

对于一个二叉查找树来说,当查找失败时,该处一定是节点需要插入的地方

insert 函数将在二叉树中插入一个数据域为x的新节点,Attention:参数root要加引用&,因为涉及到对树进行修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert(node* &root , int x)
{
if(root == NULL)
{
root = new node;
root->data = x;
root->lchild = root->rchild = NULL;
return;
}
if(x == root->data)//查找成功,说明节点已经存在,直接返回
return;
else if(x < root->data)
insert(root->lchild , x);
else
insert(root->rchild , x);
}

二叉查找树的建立,类似于一般二叉树的建立过程

1
2
3
4
5
6
7
8
9
10
11
12
13
node* Create(int data[] , int n)
{
node* root = new node();
root->data = data[0];
root->lchild = root->rchild = NULL;
for(int i = 1 ; i < n ; ++i)
{
insert(root , data[i]);
}
return root;
}

此外,还有一个有用的性质:对于二叉查找树进行中序遍历的时候,遍历的结果是有序的

并查集

操作:

  1. 合并:合并俩个集合
  2. 查找:判断俩个元素是否在一个集合中

而并查集的实现只是用到一个数组:

1
int father[N];

father[i] 表示元素i的父亲,而父亲本身也包含在这个集合内的元素, 而当father[i] = i的时候,说明i节点是根节点

并查集的基本操作

初始化:

1
2
3
4
5
6
7
8
//一开始的时候,每个元素都是一个独立的集合
void initial()
{
for(int i = 1 ; i <= N ; ++i)
{
father[i] = i;
}
}

查找:

由于规定了同一个集合只能存在一个根节点,因此查找操作就是对给定的节点寻找他的根节点过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findFather(int x)
{
while(x != father[x])
{
x = father[x];
}
return x;
}
int findFather(int x)
{
if(x == father[x])
return ;
else
return findFather(father[x]);
}

合并

合并是指把俩个集合合并成一个集合。题目中一般给出俩个元素,要求把这俩个元素所在的集合合并。

具体实现:
先判断这俩个集合是否在同一个集合中,而后将其中一个集合的根节点的父亲指向另一个集合的根节点

1
2
3
4
5
6
7
8
9
10
void Union(int a , int b)
{
int faA = findFather(a);
int faB = findFather(b);
if(faA != faB)
{
father[faB] = faA;
}
}

Attention: 并查集中一定不会出现环,其产生的每个集合一定是一棵树

路径压缩(优化查找父亲节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int findFather(int x)
{
int a =x ;
while(x != father[x])
x = father[x];
//到这里,x存放的是根节点,下面把路径上的所有节点的father都改成根节点
while(a != father[a])//重新开始搜索,并修改父亲
{
int z = a;//z用来暂存前驱
a = father[a];
father[z] = x;
}
return x;
}

热评文章