什么是二叉树?

二叉树

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2n+1。深度为k的完全二叉树，至少有2^（k-1)个节点，至多有2^k-1个节点。

一、定义

二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

二、基本概念

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——如图(a)；

(2)只有一个根结点的二叉树——如图(b)；

(3)只有左子树——如图(c)；

(4)只有右子树——如图(d)；

(5)完全二叉树——如图(e)。

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

三、相关术语

树的结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；

祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的深度：树中最大的结点层

结点的度：结点子树的个数

树的度： 树中最大的结点度。

叶子结点：也叫终端结点，是度为 0 的结点；

分枝结点：度不为0的结点；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；[3]

四、二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过 , i>=1；

(2) 深度为h的二叉树最多有 个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I>1，则其父结点的编号为I/2；

如果2I<=N，则其左儿子（即左子树的根结点）的编号为2I；若2I>N，则无左儿子；

如果2I+1<=N，则其右儿子的结点编号为2I+1；若2I+1>N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2n，n)/(n+1)。

(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i[4]

五、存储结构

(1）顺序存储方式

1  typenode=record

2  data:datatype

3  l,r:integer;

4  end;

5  vartr:array[1n]ofnode;

(2)链表存储方式，如：

1  typebtree=^node；

2  node=record

3  data:datatye;

4  lchild,rchild:btree;

5  end;

六、辨析

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：

1 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

2 树的结点无左、右之分，而二叉树的结点有左、右之分。

七、遍历顺序

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

先序遍历

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树，C语言代码如下：

1  voidXXBL(treeroot){

2  //DoSomethingwithroot

3  if(root->lchild!=NULL)

4  XXBL(root->lchild);

5  if(root->rchild!=NULL)

6  XXBL(root->rchild);

7  }

中序遍历

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树，C语言代码如下

1  voidZXBL(treeroot)

2  {

3  if(root->lchild!=NULL)

4  ZXBL(root->lchild);//DoSomethingwithroot

5  if(root->rchild!=NULL)

6  ZXBL(root->rchild);

7  }

后序遍历

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根，C语言代码如下

1  voidHXBL(treeroot){

2  if(root->lchild!=NULL)

3  HXBL(root->lchild);

4  if(root->rchild!=NULL)

5  HXBL(root->rchild);//DoSomethingwithroot

6  }

层次遍历

即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）

线索二叉树

线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉线索链表，链表作为二叉树的存储结构，叫做其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。

线索二叉树的存储结构

在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。

在后序线索树中找到结点的后继分三种情况：

若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

数据结构定义为：

/二叉线索存储表示/typedefenum{Link,Thread}PointerTag;/ Link(0)：指针，Thread(1)：线索/typedefstruct BiThrNode{ TElemType data;struct BiThrNode lchild,rchild;/左右孩子指针/PointerTag LTag,RTag;/ 左右标志 /}BiThrNode,BiThrTree;

八、实现演示

范例二叉树：

A

B C

D E

此树的顺序结构为：ABCD##E

int main()
{

nodep=newnode;

nodep=head;

head=p;

stringstr;

cin >>str;

creat(p,str,0)//默认根节点在str下标0的位置

return 0;

}

//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置

int main()

{

node p = newnode;

node p = head;

head = p;

string str;

cin >> str;

creat(p, str, 0)//默认根节点在str下标0的位置

return 0;

}

//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置。

void creat(node p, string str, int r)

{  

p->data = str[r];

if (str[r  2 + 1] == '#' || r  2 + 1 > strsize() - 1)p->lch = NULL;

else

{

p->lch = newnode;

creat(p->lch, str, r  2 + 1);

}

if (str[r  2 + 2] == '#' || r  2 + 2 > strsize() - 1)p->rch = NULL;

else

{

p->rch = newnode;

creat(p->rch, str, r  2 + 2);

}

}

共有5种，如下图所示：

二叉树简介：

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

先介绍一下树：
1树的定义
树是一种常见的非线性的数据结构。树的递归定义如下：
树是n(n>0)个结点的有限集，这个集合满足以下条件：
⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；
⑵除根外，其余的每个结点都有且仅有一个前件；
⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；
2、结点的分类
在树中，一个结点包含一个元素以及所有指向其子树的分支。结点一般分成三类
⑴根结点：没有前件的结点。在树中有且仅有一个根结点。
⑵分支结点：除根结点外，有后件的结点称为分支结点。分支结点亦是其子树的根；
⑶叶结点：没有后件的结点称为树叶。由树的定义可知，树叶本身也是其父结点的子树。
根结点到每一个分支结点或叶结点的路径是唯一的。
3、有关度的定义
⑴结点的度：一个结点的子树数目称为该结点的度。显
然，所有树叶的度为0。
⑵树的度：所有结点中最大的度称为该树的度。4、树的深度（高度）
树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。
5、有序树和无序树
按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。
 6、树的表示方法
树的表示方法一般有两种：
  ⑴自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。
 ⑵括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式
（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））
7、树的存储结构一般有两种
⑴静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标
⑵动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成
下面是有关二叉树的内容：
二叉树的概念
二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。
1、二叉树的递归定义和基本形态
二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：
⑴有一个特定的结点称为根；
⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；
由上述定义可以看出，二叉树和树是两个不同的概念
⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；
⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。
2、二叉树的两个特殊形态
⑴满二叉树： 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。可以验证具有n个叶结点的满二叉树共有2n-1个结点。
⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树
3、二叉树的三个主要性质
性质1：在二叉树的第i（≥1）层上，最多有2i-1个 结点
证明：我们采用数学归纳法证明：当i=1时只有一个根结点，即2i-1=20=1，结论成立。假设第k(i=k)层上最多有2k-1个结点，考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点，因此在第k+1层上最多有2．2k-1=2(k+1)-1=2i，结论成立。综上所述，性质1成立。
性质2：在深度为k(k≥1)的二叉树中最多有2k-1个 结点。
证明：由性质1，在二叉树第i层上最多有2i-1个结点，显然，第1层¨第k层的最多结点数为 个结点。证毕。
性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。
证明：设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0+n1+n2 （1）
由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。设 b为二叉树的前件个数，n=b+1（2）
所有这些前件同时又为度为1和度为2的结点的后件。因此又有b=n1+2n2 (3)
我们将（3）代入（2）得出n=n1+2n2+1 (4)
比较（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1
4、普通有序树转换成二叉树
普通树为有序树T，将其转化成二叉树T’的规则如下：
⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；
⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；
⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；
由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。
5、二叉树的存储结构
将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括
⑴一个数据域（data）；
⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。
满二叉树和完全二叉树一般采用顺序存储结构
对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：
⑴值域： data
⑵左指针域： lch
⑶右指针域： rch
这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点
6、二叉树的遍历
二叉树遍历的定义：按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。
二叉树遍历的顺序：如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。
前序遍历的规则如下：
若二叉树为空，则退出。否则
⑴访问处理根结点；
⑵前序遍历左子树；
⑶前序遍历右子树；
特点：由左而右逐条访问由根出发的树支 （回溯法的基础）
中序遍历的规则：
若二叉树为空，则退出；否则
⑴中序遍历左子树；
⑵访问处理根结点；
⑶中序遍历右子树；
后序遍历的规则如下：
若二叉树为空，则退出；否则
⑴后序遍历左子树；
⑵后序遍历右子树；
⑶访问处理根结点；
特点：可统计任一个结点为根的子树的情况（例如子树的权和，最优策略的选择（博弈数））

void CrtBT(BitTree &T,char pre[],char ino[],int ps,int is,int n)/递归算法构造函数，建立二叉链表/ { int k; if(n==0) T=NULL;

共有5种，如下图所示：

二叉树简介：

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

#include<stdioh>
int main()
{
   int a[256];
   int i;
   for(i=1;i<256;i++){
      a[i]=i;
   }
   printf("7的父节点%d\n",a[7/2]);
   printf("2的左孩子是%d\n",a[22]);
   printf("2的右孩子是%d\n",a[22+1]);
   getchar();
   return 0;    
}

#include<stdioh> #include<stdlibh> struct BiTNode stack[100]; struct BiTNode//定义结构体 { char data; struct BiTNode lchild,rchild; }; void later(struct BiTNode &p) //前序创建树 { char ch; scanf("%c",&ch); if(ch==' ') p=NULL; else { p=(struct BiTNode )malloc(sizeof(struct BiTNode)); p->data=ch; later(p->lchild); later(p->rchild); } } void print(struct BiTNode p) //前序遍历（输出二叉树） { int i=-1; while(1) { while(p!=NULL) { stack[++i]=p->rchild;/printf("ok？\n");/ printf("%c",p->data); p=p->lchild; } if(i!=-1) { p=stack[i]; i--; } else return; } } void main()//主函数 { struct BiTNode p,t; later(p); print(p); }

---