1.在二叉树第i层上最多有2^(i-1)个结点。
2.深度为k的二叉树最多有2^k-1个结点。
3.度为0的结点个数为n0，度为2的结点个数为n2，则n0 = n2+1 。
4.具有n个结点的完全二叉树的深度为log2^n」+1 。
5.当前结点i，双亲编号 i/2，孩子编号2i，2i+1 。（数组存储）
//链式存储
typedef struct bnode
{
DataType data; //数据域
struct bnode *lchild, *rchild; //指针域
}BNode;一般是通过后序创建二叉树的，即先创建根结点，再创建左子树，最后创建右子树，然后一直递归创建。
//创建二叉树
BNode *CreateBinTree() //创建（先跟，再左，最后右）
{
BNode *tree = NULL;
char ch = ‘0‘;
// fflush(stdin);
ch = getchar();
if (‘#‘ == ch) //（I）
tree = NULL;
else
{
tree = (BNode *)malloc(sizeof(BNode));
tree->data = ch; //创建根结点 （X）
tree->lchild = CreateBinTree(); //创建左子树 （Y）
tree->rchild = CreateBinTree(); //创建右子树 （Z）
}
return tree; //返回根结点 （R）
}
进入CreateBinTree()函数之后，一直先执行语句（Y），也就是创建左子树，先创建（结点：A->B->D），然后遇到 ‘ # ‘ ，进入（I），接着到（R），然后返回结点（Y）
接着执行（Z），创建（结点：E）.................................
由上图可以看出，先序遍历就是，先遍历根结点，在遍历左子树，最后遍历右子树。
//先序遍历
void PreOrder(BNode *tree)
{
if (tree)
{
printf("%c ",tree->data); //遍历根结点
PreOrder(tree->lchild); //遍历左子树
PreOrder(tree->rchild); //遍历右子树
}
return;
} 中序遍历就是先遍历左子树，再遍历根结点，最后遍历右子树。如下图：（红色表示已经遍历了的点）
//中序遍历
void InOrder(BNode *tree)
{
if (tree)
{
InOrder(tree->lchild);
printf("%c ",tree->data);
InOrder(tree->rchild);
}
return;
} 后序遍历，先遍历左子树，再遍历右子树，最后遍历根结点。如下图：（红色表示已经遍历了的点）
//后序遍历
void PostOrder(BNode *tree)
{
if (tree)
{
PostOrder(tree->lchild);
PostOrder(tree->rchild);
printf("%c ",tree->data);
}
return;
}
思路：每次遍历一个结点，就将计数+1 。
//计算结点个数
int count = 0; //全局变量
void CountTree(BNode *tree) //通过中序遍历计算
{
if (tree)
{
CountTree(tree->lchild);
count += 1; //计数
CountTree(tree->rchild);
}
return;
} 思路：树的高度=子树高度+1（见下面的详细分析）。
//计算树高度
int Height(BNode *tree) //树高 = 左子树（>右子树）高度+1 ：从下往上数
{
int hl = 0, hr = 0;
if (tree == NULL)
return 0;
else
{
hl = Height(tree->lchild);
hr = Height(tree->rchild);
if (hl > hr)
return hl+1;
else
return hr+1;
}
}这里数的高度等于子树高度+1，比如：只有一个根结点，即直接进入if()语句，return 0，将0+1，树的高度就是1 。
程序首先执行到（D）左子树的（#），获得一个返回值（D：hl = 0），接着执行到（D）的右子树（#），又获得一个返回值（D：hr = 0） 。
此时比较hl和hr的大小，将较大的数字+1，返回给（B：hl）。经过比较后（B：hl = 1）。
然后执行到（E）左子树（#），得到（E：hl = 0） 。
接着向右执行到（G）的左子树，这里不仔细分析了，简单写一下结果。
（G：hl = 0），（G：hr = 0）此时返回hl，hr中较大数+1给（E：hr），所以（E：hr = 1）。
此时返回到了结点（E），它需要往上层返回。
此时（E：hl = 0），（E：hr = 1）。所以（B：hr = 2） 。
（B：hl = 1），（B：hr = 2），所以（A：hl = 3）。
接着执行到（C）左子树（#），得到一个返回值（C：hl = 0）。
继续右执行，当达到（F）左子树（#），又得到一个返回值（F：hl = 0）。
再执行右边，得到（F：hr = 0）。比较后返回1给（C：hr），所以（C：hr = 1）。
因为（C：hl = 0），（C：hr = 1），所以返回一个2给(A：hr)，所以（A：hr = 2）。
最后，（A：hl = 3），（A：hr = 2），所以A将返回一个4给调用它的函数。
整个函数执行完毕！得到树的高度为：4 。
思想：这个就和创建二叉树的思路差不多，只不过将需要你输入权值那个步骤，变成了直接从另外一颗树上获取权值。
//复制二叉树
BNode *CopyTree(BNode *tree) //后序遍历思想：先复制左，再复制右，然后返回根结点。
{
BNode *ltree = NULL,*rtree = NULL,*root = NULL;
if (tree == NULL)
return NULL;
ltree = CopyTree(tree->lchild); //复制左子树
rtree = CopyTree(tree->rchild); //复制右子树
root = (BNode *)malloc(sizeof(BNode)); //复制根结点
root->data = tree->data;
root->lchild = ltree;
root->rchild = rtree;
return root;
} 思路：定义一个数组，LevNum[1]保存第一层所以结点个数，LevNum[2]保存第二层所有结点个数.................
然后每深入一层Lev+1，当从下层退回上层的时候，将相当于自动Lev-1了。
//每层结点个数
void LevCount(BNode *tree, int Lev, int LevNum[])
{
if (tree)
{
++LevNum[Lev]; //计数
LevCount(tree->lchild, Lev+1,LevNum);
LevCount(tree->rchild, Lev+1,LevNum);
}
return;
} //二叉树
//二叉树的性质：
/*
1.在二叉树第i层上最多有2^(i-1)个结点。
2.深度为K的二叉树最多有2^K-1个结点。
3.度为0的结点个数为n0，度为2的结点个数为n2，则n0 = n2+1 。
4.具有n个结点的完全二叉树的深度为log2^n」+1 。
5.双亲编号 i/2，孩子编号2i，2i+1 。
*/
/*
Name: 二叉树
Copyright: 供交流
Author: Jopus
Date: 12/02/14 09:43
Description: dev-cpp 5.5.3
*/
#include <stdio.h>
#include <stdlib.h>
#define Max 100
typedef char DataType;
/*
//顺序存储
//定义结构体
typedef struct node
{
DataType data[Max];
int n;
}LTree;
*/
//链式存储
typedef struct bnode
{
DataType data;
struct bnode *lchild, *rchild;
}BNode;
//创建二叉树
BNode *CreateBinTree() //按后序创建（先跟，再左，最后右）
{
BNode *tree = NULL;
char ch = ‘0‘;
// fflush(stdin);
ch = getchar();
if (‘#‘ == ch)
tree = NULL;
else
{
tree = (BNode *)malloc(sizeof(BNode));
tree->data = ch;
tree->lchild = CreateBinTree(); //创建左子树
tree->rchild = CreateBinTree(); //创建右子树
}
return tree;
}
//先序遍历
void PreOrder(BNode *tree)
{
if (tree)
{
printf("%c ",tree->data);
PreOrder(tree->lchild);
PreOrder(tree->rchild);
}
return;
}
//中序遍历
void InOrder(BNode *tree)
{
if (tree)
{
InOrder(tree->lchild);
printf("%c ",tree->data);
InOrder(tree->rchild);
}
return;
}
//后序遍历
void PostOrder(BNode *tree)
{
if (tree)
{
PostOrder(tree->lchild);
PostOrder(tree->rchild);
printf("%c ",tree->data);
}
return;
}
//计算结点个数
int count = 0; //全局变量
void CountTree(BNode *tree) //通过中序遍历计算
{
if (tree)
{
CountTree(tree->lchild);
count += 1; //计数
CountTree(tree->rchild);
}
return;
}
//计算树高度
int Height(BNode *tree) //树高 = 左子树（>右子树）高度+1 ：从下往上数
{
int hl = 0, hr = 0;
if (tree == NULL)
return 0;
else
{
hl = Height(tree->lchild);
hr = Height(tree->rchild);
if (hl > hr)
return hl+1;
else
return hr+1;
}
}
//复制二叉树
BNode *CopyTree(BNode *tree) //后序遍历思想：先复制左，再复制右，然后返回根结点。
{
BNode *ltree = NULL,*rtree = NULL,*root = NULL;
if (tree == NULL)
return NULL;
ltree = CopyTree(tree->lchild); //复制左子树
rtree = CopyTree(tree->rchild); //复制右子树
root = (BNode *)malloc(sizeof(BNode)); //复制根结点
root->data = tree->data;
root->lchild = ltree;
root->rchild = rtree;
return root;
}
//每层结点个数
void LevCount(BNode *tree, int Lev, int LevNum[])
{
if (tree)
{
++LevNum[Lev]; //计数
LevCount(tree->lchild, Lev+1,LevNum);
LevCount(tree->rchild, Lev+1,LevNum);
}
return;
}
//主函数
int main()
{
BNode *tree = NULL,*root = NULL;
int LevNum[100] = {0};
printf("输入>>:");
tree = CreateBinTree(); //创建二叉树
printf("先序：");
PreOrder(tree); //先序遍历
printf("\n中序：");
InOrder(tree); //中序遍历
printf("\n后序：");
PostOrder(tree); //后序遍历
CountTree(tree); //计算结点数
printf("\n结点数：%d",count);
printf("\n树高：%d",Height(tree));
root = CopyTree(tree); //复制二叉树
printf("\n复制后根结点：%c 提示：复制成功",root->data);
LevCount(tree, 1, LevNum); //每层结点数
printf("\n每层结点数：\n");
for (int i = 1; LevNum[i]!= 0; ++i)
printf("第%d层：%d\n",i,LevNum[i]);
return 0;
} Press any key to continue . . .
二叉树的创建与遍历&二叉树的高度&二叉树每层结点个数&复制二叉树
原文：http://blog.csdn.net/jopus/article/details/19109495
