爱华网二叉树，是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树。
排序二叉树_二叉树 -简介
二叉树在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的i-1次方个结点；深度为k的二叉树至多有2^(k)-1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为，度为2的结点数为，则=+1。
排序二叉树_二叉树 -辨析
二叉树是树的一种特殊情形？，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：
1.树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2.树的结点无左、右之分，而二叉树的结点有左、右之分。
排序二叉树_二叉树 -树
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前驱。以下具体地给出树的定义及树的数据结构表示。
树的定义
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且，这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度――也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度――组成该树各结点的最大层次，其深度为3；
3.森林――指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
4.有序树――指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
排序二叉树_二叉树 -二叉树
基本形态
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树――(a)；
(2)只有一个根结点的二叉树――(b)；
(3)只有左子树――(c)；
(4)只有右子树――(d)；
(5)完全二叉树――(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
重要概念
(1)完全二叉树――若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树――除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)深度――二叉树的层数，就是深度。
性质
(1)在二叉树中，第i层的结点总数不超过2^(i-1)；
(2)深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
(3)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4)具有n个结点的完全二叉树的深度为int（log2n）+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则如果I>1，则其父结点的编号为I/2；
如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
(6)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i
存储结构
(1）顺序存储方式
typenode=record
data:datatype
l,r:integer;
end;
vartr:array[1..n]ofnode;
(2)链表存储方式，如：
typebtree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;
实现
范例二叉树：
A
BC
DE
此树的顺序结构为：ABCD##E
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
intmain()
{
node*p=newnode;
node*p=head;
head=p;
stringstr;
cin>>str;
creat(p,str,0)//默认根节点在str下标0的位置
return0;
}
//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置
voidcreat(node*p,stringstr,intr)
{
p->data=str[r];
if(str[r*2+1]=='#'||r*2+1>str.size()-1)p->lch=NULL;
else
{
p->lch=newnode;
creat(p->lch,str,r*2+1);
}
if(str[r*2+2]=='#'||r*2+2>str.size()-1)p->rch=NULL;
else
{
p->rch=newnode;
creat(p->rch,str,r*2+2);
}
}
二叉树
二叉树很像一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的"双亲"，结点的后趋结点称为该结点的"子女"或"孩子"，同一结点的"子女"之间互称"兄弟"。
普通树转二叉树，一般采用左“子女”右“兄弟”的方式来转化。
转化规则：
普通树为有序树T，将其转化成二叉树T’如下：
⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；
⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；
⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；
由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。
还有一种比较有趣的方法
1）在树的所有兄弟结点上添加一条水平线
2）删去所有除左子树之外的所有父到子之间的树枝或者说成删去父结点到除最左陔子之外的所有其它孩子之间的树枝。
3）将添加的水平线顺时间转动45度。
刚开始是
..0
/|
000
增加上水平线
...0
./|
0--0--0
删除父到子除最左之外的所有树枝
...0
./
0-0-0
再将连线转动45度成为最终的二叉树为
.......0
..../
..0
....
......0
........
..........0
即在任一个结点上除了左子树外，左子树的右边的兄弟将全部连接成为左子树的右子树举例如
二叉树
..A
/|
BCD
应上面我说的除左子树外，左子树的右兄弟都连接成他的子。成为A为根，B是他的左子不变，C成为B的右子树D又连成C的右子树，结果为
......A
..../
..B
....
......C
........
..........D
完成
注：“.”为空格。
完全二叉树
对满二叉树，从第一层的结点(即根)开始，由下而上，由左及右，按顺序结点编号，便得到满二叉树的一个顺序表示。据此编号，完全二叉树定义如下：一棵具有n个结点，深度为K的二叉树，当且仅当所有结点对应于深度为K的满二叉树中编号由1至n的那些结点时，该二叉树便是完全二叉树。
排序二叉树_二叉树 -二叉树遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD（称为后根次序遍历）。
(1)先序遍历
首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树，C语言代码如下：
1
2
3
4
5
6
7
8
voidXXBL(tree*root)
{
//DoSomethingwithroot
if(root->lchild!=NULL)
XXBL(root->lchild);
if(root->rchild!=NULL)
XXBL(root->rchild);
}
(2)中序遍历
首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树，C语言代码如下
1
2
3
4
5
6
7
8
voidZXBL(tree*root)
{
if(root->lchild!=NULL)
ZXBL(root->lchild);
//DoSomethingwithroot
if(root->rchild!=NULL)
ZXBL(root->rchild);
}
(3)后序遍历
首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根，C语言代码如下
1
2
3
4
5
6
7
8
voidHXBL(tree*root)
{
if(root->lchild!=NULL)
HXBL(root->lchild);
if(root->rchild!=NULL)
HXBL(root->rchild);
//DoSomethingwithroot
}
（4）层次遍历
即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）
特殊的二叉树
1.完全二叉树
CompleteBinaryTree
若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。
2.满二叉树
FullBinaryTree
一个高度为h的二叉树包含正是2^h-1元素称为满二叉树。
6线索二叉树
编辑
线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉线索链表，链表作为二叉树的存储结构，叫做其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。
线索二叉树的存储结构
线索二叉树的存储结构
在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。
在后序线索树中找到结点的后继分三种情况：
若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。
数据结构定义为：
1
2
3
4
5
6
7
/*二叉线索存储表示*/
typedefenum{Link,Thread}PointerTag;/*Link(0)：指针，Thread(1)：线索*/
typedefstructBiThrNode
{TElemTypedata;
structBiThrNode*lchild,*rchild;/*左右孩子指针*/
PointerTagLTag,RTag;/*左右标志*/
}BiThrNode,*BiThrTree;
排序二叉树_二叉树 -线索二叉树
线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉线索链表，链表作为二叉树的存储结构，叫做其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。
线索二叉树的存储结构
线索二叉树的存储结构
在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。
在后序线索树中找到结点的后继分三种情况：
若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。
数据结构定义为：
1
2
3
4
5
6
7
/*二叉线索存储表示*/
typedefenum{Link,Thread}PointerTag;/*Link(0)：指针，Thread(1)：线索*/
typedefstructBiThrNode
{TElemTypedata;
structBiThrNode*lchild,*rchild;/*左右孩子指针*/
PointerTagLTag,RTag;/*左右标志*/
}BiThrNode,*BiThrTree;
