#树# #二叉树#

二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

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

如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

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

树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
树的结点无左、右之分，而二叉树的结点有左、右之分。

类型

完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。（深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应）
满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。（一棵深度为k，且有2^k-1个节点）
平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树性质

在非空二叉树中，第i层的结点总数不超过 ,i>=1；
深度为h的二叉树最多有个结点(h>=1)，最少有h个结点；
对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
具有n个结点的完全二叉树的深度为
有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，则无右儿子。
给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i[4]

遍历顺序

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

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：

DLR（称为先根次序遍历）；
LDR（称为中根次序遍历）；
LRD （称为后根次序遍历）。

 1 #include<cstdio>
 2 typedef struct node{
 3     char data;
 4     struct node *leftson;
 5     struct node *rightson;
 6 }BiNode,*BiTree;
 7 
 8 void creatBiTree (BiTree & T){//前序建树 
 9     char c;
10     scanf("%c",&c);
11     if(c=='#')T=NULL;
12     else {
13         T = new BiNode;
14         T->data=c;
15         creatBiTree(T->leftson);
16         creatBiTree(T->rightson);
17     }
18 }
19 
20 void preorder (BiTree T){//先序遍历 
21     if(T){
22         printf("%c ",T->data);
23         preorder(T->leftson);
24         preorder(T->rightson);
25     }
26 }
27 
28 void inorder (BiTree T){//中序遍历 
29     if(T){
30         inorder(T->leftson);
31         printf("%c ",T->data);
32         inorder(T->rightson);
33     }
34 }
35 
36 void postorder (BiTree T){//后序遍历 
37     if(T){
38         postorder(T->leftson);
39         postorder(T->rightson);
40         printf("%c ",T->data);
41     }
42 }
43 
44 int depth (BiTree T){//求二叉树深度 
45     int dep=0;
46     int depl=0,depr=0;
47     if(!T)dep=0;
48     else {
49         depl=depth(T->leftson);
50         depr=depth(T->rightson);
51         dep=1+(depl>depr?depl:depr); 
52     }
53     return dep;
54 }
55 
56 int sumleaf (BiTree T){//求叶子节点个数 
57     int sum=0;
58     int l,r;
59     if(T){
60         if((!T->leftson)&&(!T->rightson))sum++;
61         l=sumleaf(T->leftson);
62         sum+=l;
63         r=sumleaf(T->rightson);
64         sum+=r;
65     }
66     return sum;
67 }
68 
69 int main(){
70     BiTree T;
71     creatBiTree(T);
72     preorder (T);printf("
");
73     inorder (T);printf("
");
74     postorder (T);printf("
");
75     printf("%d
",depth(T));
76     printf("%d
",sumleaf(T)); 
77     return 0;
78 }

eg：

（先序） ABC##DE#G##F### （#表示空）