< div id=”article_content” class=”article_content clearfix”>
二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。
树的术语：
| Name |
Function |
| 路径 |
顺着连接点的边从一个节点走向另一个节点，所经过的节点的顺序排列就称为路径。 |
| 根 |
树顶端的节点就称为根，一棵树只有一个根，如果要把一个节点和边的集合定义为树，那么从根到其他任何一个节点都必须有一条路径。 |
| 父节点 |
每个节点（除了根）都恰好有一条边向上连接到另一个节点，上面的节点就称为下面节点的“父节点”。 |
| 子节点 |
每个节点都可能有一条或多条边向下连接其他节点，下面的这些节点就称为它的“子节点”。 |
| 叶节点 |
没有子节点的节点称为“叶子节点”或简称“叶节点”。树只能有一个根，但是可以有很多叶节点 |
| 子树 |
每个节点都可以作为子树的根，它和它所有的子节点，子节点的子节点等都含在子树中。 |
| 访问 |
当程序控制流程到达某个节点的时候，就称为“访问”这个节点，通常是为了在这个节点处执行某种操作，例如查看节点某个数据字段的值或者显示节点。 |
| 遍历 |
遍历树意味着要遵循某种特定的顺序访问树中的所有节点。 |
| 层 |
一个节点的层数是指从根开始到这个节点有多少“代”。 |
| 关键字 |
可以看到，对象中通常会有一个数据域被指定为关键字值。这个值通常用于查询或者其他操作。 |
| 二叉树 |
如果树中的每个节点最多只能有两个子节点，这样的树就称为“二叉树”。 |
满二叉树：在一棵二叉树中，如果所有分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下层，这样的树叫做满二叉树
如：
根据满二叉树的定义，得到其特点为：
- 叶子只能出现在最下一层。
- 非叶子结点度一定是2.
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树：若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都是依次排列在该层最左边的位置上，则称为完全二叉树。
如：
满二叉树与完全二叉树的区别：满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满，并没有满。 结合完全二叉树定义得到其特点：
- 叶子结点只能出现在最下一层和次下层（满二叉树继承而来）
- 最下层叶子结点一定集中在左 部连续位置。
- 倒数第二层，如有叶子节点，一定出现在右部连续位置。
- 同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。
一般二叉树的性质：
- 左节点下标是其父节点的二倍，右节点的下标是其父节点的二倍加一（左节点加一）。
- 第n层的节点个数最多为2n-1。
- 前n层的节点个数最多为2n-1。
- 对于任何一棵非空的二叉树,如果叶节点个数为n0，度数为2的节点个数为n2，则有: n0 = n2 + 1。
4的证明：在一棵二叉树中，除了叶子结点（度为0）之外，就剩下度为2(n2)和1(n1)的结点了。则树的结点总数为T = n0+n1+n2;在二叉树中结点总数为T，而连线数为T-1.所以有：n0+n1+n2-1 = 2*n2 +n1;最后得到n0 = n2+1;
完全二叉树的性质：
- 具有n个结点的完全二叉树的深度为log2n+1.
证明： 满二叉树是完全二叉树，对于深度为k的满二叉树中结点数量是2k-1 = n，完全二叉树结点数量肯定最多2k-1,同时完全二叉树倒数第二层肯定是满的（倒数第一层有结点，那么倒是第二层序号和满二叉树相同），所以完全二叉树的结点数最少大于少一层的满二叉树，为2k-1-1。
根据上面推断得出： 2k-1-1< n=<2k\-1，因为结点数Nn为整数那么n<=2k\-1可以推出n<=2k ,n>2(k-1)-1可以推出 n>=2k-1,所以2k-1k 。即可得k-1<=log2n
- 如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有
- 如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下取整
- 如果2i>n那么节点i没有左孩子，否则其左孩子为2i
- 如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1
在上图中验证 第一条：
当i=1时，为根节点。当i>1时，比如结点为7，他的双亲就是7/2= 3；结点9双亲为4. 第二条：
结点6, 6* 2 = 12>10，所以结点6无左孩子，是叶子结点。结点5，5*2 = 10，左孩子是10,结点4，为8. 第三条：
结点5，2*5+1>10,没有右孩子，结点4，则有右孩子。 二叉树可以用数组建立也可以用结构体建立。
数组建立二叉树：//前序遍历方式建立二叉树
1
2
3
4
5
6
7
8
9
10
11
12
| char s[MAXn];
void scan(int n)
{
char c;
cin>>c;
s[n]=c;
if(c!='#')
{
scan(n*2);
scan(n*2+1);
}
}
|
结构体建立二叉图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| struct node{
node *l;
node *r;
char c;
node()
{
l=r=NULL;
}
};
void scan(node *& root)
{
char c;
cin>>c;
if(c!='#')
{
root=new node;
root->c=c;
scan(root->l);
scan(root->r);
}
}
|
上述二种代码输入： HDB#A##C##G#FE###
构造出的二叉图如下：
数组二叉树的遍历：
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
| void qian(int n)
{
if(s[n]!='#')
{
cout<<s[n];
qian(n*2);
qian(n*2+1);
}
return ;
}
void zhong(int n)
{
if(s[n]=='#')
return;
zhong(n*2);
cout<<s[n];
zhong(n*2+1);
return ;
}
void hou(int n)
{
if(s[n]!='#')
{
hou(n*2);
hou(n*2+1);
cout<<s[n];
}
return ;
}
|
结构体二叉树遍历：
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
| void qian(node *root)
{
if(root)
{
cout<<root->c;
qian(root->l);
qian(root->r);
}
}
void zhong(node *root)
{
if(root)
{
zhong(root->l);
cout<<root->c;
zhong(root->r);
}
}
void hou(node *root)
{
if(root)
{
hou(root->l);
hou(root->r);
cout<<root->c;
}
}
|
数组二叉树遍历代码：
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
| #include <cstdio>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
char s[MAXn];
void scan(int n)
{
char c;
cin>>c;
s[n]=c;
if(c!='#')
{
scan(n*2);
scan(n*2+1);
}
}
void qian(int n)
{
if(s[n]!='#')
{
cout<<s[n];
qian(n*2);
qian(n*2+1);
}
return ;
}
void zhong(int n)
{
if(s[n]=='#')
return;
zhong(n*2);
cout<<s[n];
zhong(n*2+1);
return ;
}
void hou(int n)
{
if(s[n]!='#')
{
hou(n*2);
hou(n*2+1);
cout<<s[n];
}
return ;
}
int main()
{
scan(1);
qian(1);
cout<<endl;
zhong(1);
cout<<endl;
hou(1);
cout<<endl;
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
72
73
74
| #include <cstdio>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
struct node{
node *l;
node *r;
char c;
node()
{
l=r=NULL;
}
};
void scan(node *& root)
{
char c;
cin>>c;
if(c!='#')
{
root=new node;
root->c=c;
scan(root->l);
scan(root->r);
}
}
void qian(node *root)
{
if(root)
{
cout<<root->c;
qian(root->l);
qian(root->r);
}
}
void zhong(node *root)
{
if(root)
{
zhong(root->l);
cout<<root->c;
zhong(root->r);
}
}
void hou(node *root)
{
if(root)
{
hou(root->l);
hou(root->r);
cout<<root->c;
}
}
int main()
{
node *root;
scan(root);
qian(root);
cout<<endl;
zhong(root);
cout<<endl;
hou(root);
cout<<endl;
return 0;
}
|
