一、二叉树的定义(二叉树是树的特殊一族)
二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点 和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
总结：二叉树的定义有点复杂，看起来定义有点混乱。这没事，主要是利用二叉树的特点办事。(*^__^*) 嘻嘻……
二、二叉树的特点
特点：
每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。（注意：不是都需要两棵子树，而是最多可以是两棵，没 有子树或者有一棵子树也都是可以的。）
左子树和右子树是有顺序的，次序不能颠倒。
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树，下面是完全不同的二叉树：
二叉树的五种基本形态
空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树
只有3个节点的二叉树就有5种形式
完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点位置 完全相同，则这棵二叉树称为完全二叉树。
满二叉树:
一棵深度为k且有2k - 1个结点的二叉树。
满二叉树特点
叶子只能出现在最下一层。
非叶子结点的度一定是2。
在同样深度的二叉树中，满二叉树的结点个数一定最多，同时叶子也是最多。
总结：
1）二叉树是树的特殊一种，节点最多只有两个孩子（左右孩子），左右孩子还是有次序分。
2）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
三、二叉树的代码实现
简单的二叉树代码实现，中心思想是递归调用
|
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
|
#
include
<stdio.h>
#
include
<stdlib.h>
#define OK
0
typedef char ElemType;
typedef
int
Status;
typedef struct BitNode
{
char data;
struct BitNode *lchild,*rchild;
}BitNode, *BitTree;
Status CreateBitTree(BitTree *T)
//中序,先序，后序对树的创建无影响。此处采用中序
{
ElemType e;
scanf(
"%c"
, &e);
if
(
' '
== e){
*T = NULL;
}
else
{
*T = (BitTree)malloc(sizeof(BitNode));
(*T)->data = e;
CreateBitTree(&(*T)->lchild);
//递归调用
CreateBitTree(&(*T)->rchild);
}
return
OK;
}
void
visit(ElemType e,
int
level)
{
printf(
"元素%c位于第%d层\n"
, e, level);
}
Status PreOrderTraverse(BitTree T,
int
level)
//中序遍历，level是层数
{
if
(T){
visit(T->data, level);
PreOrderTraverse(T->lchild, level +
1
);
PreOrderTraverse(T->rchild, level +
1
);
}
return
OK;
}
int
main(){
int
level =
1
;
//层次
BitTree T = NULL;
CreateBitTree(&T);
PreOrderTraverse(T,level);
return
0
;
}
|
四、知识点回顾
二叉树的特点、完全二叉树、满二叉树、满二叉树与完全二叉树的区别、代码的递归思想
本文转自lilin9105 51CTO博客，原文链接：http://blog.51cto.com/7071976/1207703，如需转载请自行联系原作者
