一、树：
树 ：一种非线性数据结构
树的应用：
操作系统中：用树表示文件目录组织结构
编译系统中: 用树表示源程序语法结构
相关概念常见表示方法：
树有且仅有一个根节点
树的结构定义是一个递归的定义
树可以看做一个集合，每个集合下面又有很多子集合，所以单节点与子树之间可以表示为 T={跟结点，左孩子，右孩子}
-实例：T1 ={A,B,C}
当然，树还可以用括号表示，这样更加容易看
上图可表示为：(A (B(D,E(G) ), C( F(H,J) ) )
还可以通过图形来表示：
基本树语：
结点的度：拥有的子树（也就是说有几个分支）树的度：树中结点度的最大值叶子结点（终端结点）：度为0的结点（没有分支）双亲和孩子：如下图：A是B、C的双亲，B、C是A的孩子。堂兄弟：如下图：双亲在同一层（如E和F）高度（深度）：书中结点最大几层（比如下图为深度：3）
二、二叉树：
二叉树：树的度为2的二叉树（结点最大度为2）。
性质：
第i层最多 2^(i-1)个结点深度为k，最多2^k - 1 个结点叶子结点树为n,度为2的节点数为n2，那么n=n2+1n个结点的二叉树深度：log2n + 1 (log2n不小于log2n的整数)
满二叉树与完全二叉树：
1、满二叉树： 深度为k且含有2^k-1个结点。看图很容易理解。
2、完全二叉树： 每个结点都与所对应的完全二叉树一 一对应，叶子几点只可能出现在最后两层。
二叉树的三种遍历算法：
1、前序遍历：ABDGHCEIF（规则是先是根结点，再前序遍历左子树，再前序遍历右子树）
2、中序遍历：GDHBAEICF（规则是先中序遍历左子树，再是根结点，再是中序遍历右子树）
3、后序遍历：GHDBIEFCA（规则是先后序遍历左子树，再是后序遍历右子树，再是根结点）
三、C语言实现基本操作（三种遍历算法）;
1、定义树的结构体：
typedef struct BTree
{
char data;
struct BTree *lChild;
struct BTree *rChild;
}BinTree;
2、创建树：
输入顺序是先遍历根结点，再遍历左右结点，也就是先序遍历，然后重复把左右孩子当做根节点，重复上诉过程，这就是一个递归过程。这里用“#”表示孩子为空，所以下图中B就表示叶子结点，而C没有左孩子。
这里要求要通过先序遍历输入各结点，如果要创建这个树应该输入：AB##C#D##
BinTree
*CreateTree(BinTree
*p)
{
char ch;
scanf(
"%c",
&ch);
if (ch
== '#')
{
return NULL;
}
p
=(BinTree
*)malloc(sizeof(BinTree));
p
->data = ch;
p
->lChild
= CreateTree(p
->lChild);
p
->rChild
= CreateTree(p
->rChild);
return p;
}
这里有碰到个问题，才发现自己对scanf还是没理解深刻。明明我只输入了（一次性输入了所有字符），char型的ch一次也只能接收一个字符，那么为什么可以实现二叉树的创建呢？
原来scanf输入是把所有的字符都存入了缓冲区，每调用一次scanf就从缓冲区读入一个字符，如果读到回车，scanf就结束。
通过一个程序验证一下：
#include <stdio.h>
int main()
{
char a;
char b;
char c;
printf(
"input a:\n");
scanf(
"%c",&a);
printf(
"input b:\n");
scanf(
"%c",&b);
printf(
"input c:\n");
scanf(
"%c",&c);
printf(
"%c",a);
printf(
"%c",c);
return 0;
}
3、前序遍历：
根结点->左孩子->右孩子
void PreOrder(BinTree
*T)
{
if(T)
{
printf(
"%c",T
->data);
PreOrder(T
->lChild);
PreOrder(T
->rChild);
}
}
4、中序遍历
左孩子->根结点->右孩子
void MidOrder(
BinTree *
T)
{
if (
T)
{
MidOrder(
T->lChild);
printf(
"%c",
T->
data);
MidOrder(
T->rChild);
}
}
4、后序遍历：
左孩子->右孩子->根结点
void LastOrder(
BinTree *
T)
{
if(
T)
{
LastOrder(
T->lChild);
LastOrder(
T->rChild);
printf(
"%c",
T->
data);
}
}
5、复制二叉树;
void Copy(BinTree
*T,BinTree
**newTree)
{
if(T
== NULL)
{
*newTree
= NULL;
return ;
}
else
{
*newTree
= (BinTree
*)malloc(sizeof(BinTree));
(
*newTree)
->data = T
->data;
Copy(T
->lChild,
&(
*newTree)
->lChild);
Copy(T
->rChild,
&(
*newTree)
->rChild);
}
}
这里用了二级指针存放了指针地址，如果不用二级指针，则需要用返回值的形式来返回新树的地址。如下：程序改为了：
BinTree
*Copy(BinTree
*T)
{
if(T
== NULL)
{
newTree
= NULL;
return newTree;
}
else
{
newTree
= (BinTree
*)malloc(sizeof(BinTree));
newTree
->data = T
->data;
newTree
->lChild
=Copy(T
->lChild);
newTree
->rChild
=Copy(T
->rChild);
}
return newTree;
}
6、其他操作：
int Sumleaf(BinTree
*T)
{
int
sum=0,m,n;
if (T)
{
if ((
!T
->lChild)
&& (
!T
->rChild))
{
sum++;
}
m
=Sumleaf(T
->lChild);
sum+=m;
n
=Sumleaf(T
->rChild);
sum+=n;
}
return sum;
}
int Depth(BinTree
*T)
{
int dep
=0,dep1,depr;
if (
!T)
{
dep
=0;
}
else
{
dep1
=Depth(T
->lChild);
depr
=Depth(T
->rChild);
dep
=1+(dep1
>depr
? dep1:depr);
}
return dep;
}
总结：
1、递归的时候一定要注意参数传入：
在这个过程中，遇到最大问题就是在复制二叉树那段代码。因为对二级指针操作不是太熟练，所以递归的时候开始的时候老是提示错误：
expected ‘struct BinTree **’ but argument is of type ‘struct BTree *’
后来不断检查才知道，因为二级指针要传的是地址，第一次传了地址，但是第二次没有加取地址符。
2、注意带 * 号变量指向问题：
带*号变量应该正确的指向方法应该是：（*p)->a 而不应该是*p->a
完整代码：
#include <stdio
.h
>
#include <stdlib
.h
>
typedef struct BTree
{
char
data;
struct BTree
*lChild;
struct BTree
*rChild;
}BinTree;
BinTree
*CreateTree(BinTree
*p)
{
char ch;
scanf(
"%c",
&ch);
if (ch
== '#')
{
return NULL;
}
p
=(BinTree
*)malloc(sizeof(BinTree));
p
->data = ch;
p
->lChild
= CreateTree(p
->lChild);
p
->rChild
= CreateTree(p
->rChild);
return p;
}
int Sumleaf(BinTree
*T)
{
int
sum=0,m,n;
if (T)
{
if ((
!T
->lChild)
&& (
!T
->rChild))
{
sum++;
}
m
=Sumleaf(T
->lChild);
sum+=m;
n
=Sumleaf(T
->rChild);
sum+=n;
}
return sum;
}
int Depth(BinTree
*T)
{
int dep
=0,dep1,depr;
if (
!T)
{
dep
=0;
}
else
{
dep1
=Depth(T
->lChild);
depr
=Depth(T
->rChild);
dep
=1+(dep1
>depr
? dep1:depr);
}
return dep;
}
void PreOrder(BinTree
*T)
{
if(T)
{
printf(
"%c",T
->data);
PreOrder(T
->lChild);
PreOrder(T
->rChild);
}
}
void MidOrder(BinTree
*T)
{
if (T)
{
MidOrder(T
->lChild);
printf(
"%c",T
->data);
MidOrder(T
->rChild);
}
}
void LastOrder(BinTree
*T)
{
if(T)
{
LastOrder(T
->lChild);
LastOrder(T
->rChild);
printf(
"%c",T
->data);
}
}
void Copy(BinTree
*T,BinTree
**newTree)
{
if(T
== NULL)
{
*newTree
= NULL;
return ;
}
else
{
*newTree
= (BinTree
*)malloc(sizeof(BinTree));
(
*newTree)
->data = T
->data;
Copy(T
->lChild,
&(
*newTree)
->lChild);
Copy(T
->rChild,
&(
*newTree)
->rChild);
}
}
int main()
{
BinTree
*Tree;
BinTree
*newtree;
printf(
"请以前序遍历的方式输入扩展二叉树，用“#”表示空结点：\n");
Tree
=CreateTree(Tree);
printf(
"前序遍历:\n");
PreOrder(Tree);
printf(
"\n中序遍历:\n");
MidOrder(Tree);
printf(
"\n后序遍历:\n");
LastOrder(Tree);
printf(
"\n叶结点总数：%d\n",Sumleaf(Tree));
printf(
"\n树的层数：%d\n",Depth(Tree));
Copy(Tree,
&newtree);
printf(
"\n复制树后序遍历:\n");
LastOrder(newtree);
return 0;
}
测试： 要创建如下二叉树，并且输出：先/中/后序遍历结果
输入（先序遍历输入）：AB##C#D## 测试结果：
本文参考：http://www.cnblogs.com/liuamin/p/6269950.html
