二叉树性质
n 性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）
n 性质2: 深度为k的二叉树至多有2k-1个结点（k>0）
n 性质3: 对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
二叉树的递归遍历源码：分为先序遍历：根 左 右 ；中序遍历：左 根 右；后续遍历：左 右 根
#define _CRT_SECURE_NO_WARNINGS#include#include #include //二叉树节点struct BiNode{ char ch; struct BiNode *lchild; struct BiNode *rchild;};//二叉树的递归遍历先序void recursion(struct BiNode *root){ if (NULL == root){ return; } //再访问左子树 recursion(root->lchild);//printf 先序遍历 //再访问右子树 recursion(root->rchild);// printf 中顺序遍历 //先访问根节点 printf("%c ", root->ch);// printf 后续遍历}void test(){ //二叉树节点 struct BiNode node1 = { 'A', NULL, NULL }; struct BiNode node2 = { 'B', NULL, NULL }; struct BiNode node3 = { 'C', NULL, NULL }; struct BiNode node4 = { 'D', NULL, NULL }; struct BiNode node5 = { 'E', NULL, NULL }; struct BiNode node6 = { 'F', NULL, NULL }; struct BiNode node7 = { 'G', NULL, NULL }; struct BiNode node8 = { 'H', NULL, NULL }; node1.lchild = &node2; node1.rchild = &node6; node2.rchild = &node3; node3.lchild = &node4; node3.rchild = &node5; node6.rchild = &node7; node7.lchild = &node8; //遍历二叉树 recursion(&node1);}int main(){ test(); system("pause"); return EXIT_SUCCESS;}
通过栈实现二叉树的非递归遍历：
见数据结构 栈的实现
#define _CRT_SECURE_NO_WARNINGS#include#include #include #include"SeqStack.h"#include //二叉树节点struct BiNode{ char ch; struct BiNode *lchild; struct BiNode *rchild;};struct Info{ struct BiNode *node; bool flag;};struct Info *CreateInfo(struct BiNode *node,bool flag){ struct Info *info = malloc(sizeof(struct Info)); info->node = node; info->flag = flag; return info;}void nonrecursion(struct BiNode *root){ //初始化stack void *stack = Init_SeqStack(); //1. 先把根节点入stack Push_SeqStack(stack, CreateInfo(root, false)); while (Size_SeqStack(stack) > 0){ //2. 获得stack顶元素 struct Info *info = (struct Info *)Top_SeqStack(stack); Pop_SeqStack(stack); //3. 判断当前节点的flag是否为true,true:直接输出。false:左子树和右子树分别压stack，当前节点二次入stack if(info->flag){ printf("%c ",info->node->ch); free(info); continue; } //右子树入stack if (info->node->rchild != NULL){ Push_SeqStack(stack, CreateInfo(info->node->rchild, false)); } //根节点入stack info->flag = true; Push_SeqStack(stack, info); //左子树入stack if (info->node->lchild != NULL){ Push_SeqStack(stack, CreateInfo(info->node->lchild, false)); } }}void test(){ //二叉树节点 struct BiNode node1 = { 'A', NULL, NULL }; struct BiNode node2 = { 'B', NULL, NULL }; struct BiNode node3 = { 'C', NULL, NULL }; struct BiNode node4 = { 'D', NULL, NULL }; struct BiNode node5 = { 'E', NULL, NULL }; struct BiNode node6 = { 'F', NULL, NULL }; struct BiNode node7 = { 'G', NULL, NULL }; struct BiNode node8 = { 'H', NULL, NULL }; node1.lchild = &node2; node1.rchild = &node6; node2.rchild = &node3; node3.lchild = &node4; node3.rchild = &node5; node6.rchild = &node7; node7.lchild = &node8; nonrecursion(&node1);}int main(){ test(); system("pause"); return EXIT_SUCCESS;}
求二叉数的叶子节点函数：
void caculateLeafNums(struct BiNode *root,int *num){ if (NULL == root){ return; } if (root->lchild == NULL && root->rchild == NULL){ (*num)++; } //遍历左子树 caculateLeafNums(root->lchild, num); //遍历右子树 caculateLeafNums(root->rchild, num);}
二叉树的拷贝、释放、二叉树高度函数：
//拷贝二叉树struct BiNode *copyTree(struct BiNode *root){ if (NULL == root){ return NULL; } //递归拷贝左子树 struct BiNode *lchild = copyTree(root->lchild); //递归拷贝右子树 struct BiNode *rchild = copyTree(root->rchild); //拷贝当前节点 struct BiNode *newnode = malloc(sizeof(struct BiNode)); printf("%c ",root->ch); newnode->ch = root->ch; newnode->lchild = lchild; newnode->rchild = rchild; return newnode;}//释放二叉树内存void freeSpace(struct BiNode *root){ if (NULL == root){ return; } //释放左子树 freeSpace(root->lchild); //释放右子树 freeSpace(root->rchild); //释放根节点 free(root);}//递归遍历void foreach(struct BiNode *root){ if (NULL == root){ return; } printf("%c ",root->ch); foreach(root->lchild); foreach(root->rchild);}//求树的高度int caculateTreeHeight(struct BiNode *root){ if (NULL == root){ return 0; } //求左子树的高度 int lheight = caculateTreeHeight(root->lchild); //求右子树的高度 int rheight = caculateTreeHeight(root->rchild); int height = lheight > rheight ? lheight + 1 : rheight + 1; return height;}