【二叉树遍历算法应用】------补录

0.二叉树结点的链式存储结构

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>typedef char TElemType;//树中元素基本类型为char类型//二叉树结点链式存储结构（二叉链表）
typedef struct BiNode
{TElemType data;//数据域struct BiNode* lchild, * rchild;//左，右孩子指针
}BiNode,*BiTree;
//BiNode：用来定义结点类型
//BiTree：用来定义树类型

1.复制二叉树

int CopyBiTree(BiTree b,BiTree* newb)

注意：原本存在的树只是会遍历，不会被修改，故传入一级指针
但要复制成的新树，应传入结点指针的地址，即二级指针，因为要修改结点指针的值（指向新开辟的结点空间）

1.1算法步骤：

（1）返回条件：当前根结点为空，注意复制完空结点之后再返回
（2）当前结点非空，申请新结点空间并复制根结点
（3）递归复制左子树（注意传入New树待修改指针的地址）
（4）递归复制右子树（注意传入New树待修改指针的地址）

//1.先序复制二叉树      (万变不离其宗，就是先序遍历算法的变种)
//注意：原本存在的树只是会遍历，不会被修改，故传入一级指针
//但要复制成的新树，应传入结点指针的地址，即二级指针，因为要修改结点指针的值（指向新开辟的结点空间）
int CopyBiTree(BiTree b,BiTree* newb)
{//[1]返回条件：当前根结点为空，注意复制完空结点之后再返回if (b == NULL){(*newb) = NULL;//易错1：忘记复制空结点return 0;}//[2]当前结点非空，申请新结点空间，复制根结点(*newb) = (BiNode*)malloc(sizeof(BiNode));if (!(*newb)){printf("内存分配失败！\n");exit(-1);}(*newb)->data = b->data;//[3]递归复制左子树CopyBiTree(b->lchild, &((*newb)->lchild));//注意传入New树待修改指针的地址//[4]递归复制右子树CopyBiTree(b->rchild, &((*newb)->rchild));
}

2.计算二叉树的深度

• 深度回顾：指从头结点开始到最远的叶子结点，路径上的结点数【注意：包括头结点】

int DepthBiTree(BiTree b)

注意：只进行遍历，不会修改树的结构，故传入一级指针

2.1算法步骤：

（1）返回条件：当前根结点为空,返回0
（2）递归计算左子树的深度记为m
（3）递归计算右子树的深度记为n
（4）返回子树的深度：即m和n中的较大值，并加1
加1是因为子树根结点要算上；
返回较大值是因为深度 应该是最远路径上的结点总数，

//2.计算二叉树深度  (树的深度：指从头结点开始到最远的叶子结点，路径上的结点数【注意：包括头结点】)
//注意：只进行遍历，不会修改树的结构，故传入一级指针
int DepthBiTree(BiTree b)
{//[1]返回条件：当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的深度记为mint m = DepthBiTree(b->lchild);//[3]递归计算右子树的深度记为nint n = DepthBiTree(b->rchild);//[4]返回子树的深度：即m和n中的较大值，并加1//加1是因为子树根结点要算上return (m > n) ? m + 1 : n + 1;
}

3.计算二叉树中结点总数

int NodeCount(BiTree b)

3.1算法步骤：

（1）返回条件：当前根结点为空,返回0
（2）递归计算左子树的结点总数记为m
（3）递归计算右子树的结点总数记为n
（4）返回子树的结点总数：即m和n之和，并加1
加1是因为子树根结点要算上

//3.计算二叉树中结点总数
int NodeCount(BiTree b)
{//[1]返回条件：当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的结点总数记为mint m = NodeCount(b->lchild);//[3]递归计算右子树的结点总数记为nint n = NodeCount(b->rchild);//[4]返回子树的结点总数：即m和n之和，并加1//加1是因为子树根结点要算上return m + n + 1;
}

4.计算二叉树中叶子结点总数

• 回顾叶子结点：左子树和右子树均为空的结点，一般在完全二叉树的最下面

int LeadCountBiTree(BiTree b)

4.1算法步骤

（1）返回条件1：当前根结点为空,返回0
（2）返回条件2：当前结点为叶子结点，返回1
两个返回条件缺一不可
（3）递归计算左子树和右子树的叶子结点总数记为m和n
（4）返回子树的叶子结点总数：即m和n之和

//4.计算二叉树中叶子结点总数(叶子结点：左子树和右子树均为空的结点，一般在完全二叉树的最下面)
int LeadCountBiTree(BiTree b)
{//[1]返回条件1：当前根结点为空,返回0if (b == NULL){return 0;}//[2]返回条件2：当前结点为叶子结点，返回1if (b->rchild == NULL && b->lchild == NULL){return 1;}//[3]递归计算左子树和右子树的叶子结点总数记为m和nint m = LeadCountBiTree(b->lchild);int n = LeadCountBiTree(b->rchild);//[4]返回子树的叶子结点总数：即m和n之和return m+n;
}

5.整体代码实现

• 样例树：应输入序列
  abc##de###fg#h###
• 复制后新树的先序序列为：
  abcdefgh
• 深度：4
• 结点总数：8
• 叶子结点总数：3
  

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>typedef char TElemType;typedef struct BiNode
{TElemType data;struct BiNode* lchild, * rchild;
}BiNode,*BiTree;//.先序遍历
bool PreOrderTraverse(BiTree b)
{if (b == NULL){return true;}printf("%c", b->data);//根PreOrderTraverse(b->lchild); //左PreOrderTraverse(b->rchild); //右}//先序建立整树
bool CreateBiTree(BiTree * b)
{//[0]TElemType ch;scanf_s("%c", &ch);if (ch == '#'){(*b) = NULL;}else{(*b) = (BiNode*)malloc(sizeof(BiNode));if (!(*b)){printf("内存分配失败！\n");exit(-1);}(*b)->data = ch;//根CreateBiTree(&((*b)->lchild)); //左CreateBiTree(&((*b)->rchild));//右}return true;
}//1.先序复制二叉树      (万变不离其宗，就是先序遍历算法的变种)
//注意：原本存在的树只是会遍历，不会被修改，故传入一级指针
//但要复制成的新树，应传入结点指针的地址，即二级指针，因为要修改结点指针的值（指向新开辟的结点空间）
int CopyBiTree(BiTree b,BiTree* newb)
{//[1]返回条件：当前根结点为空，注意复制完空结点之后再返回if (b == NULL){(*newb) = NULL;//易错1：忘记复制空结点return 0;}//[2]当前结点非空，申请新结点空间，复制根结点(*newb) = (BiNode*)malloc(sizeof(BiNode));if (!(*newb)){printf("内存分配失败！\n");exit(-1);}(*newb)->data = b->data;//[3]递归复制左子树CopyBiTree(b->lchild, &((*newb)->lchild));//注意传入New树待修改指针的地址//[4]递归复制右子树CopyBiTree(b->rchild, &((*newb)->rchild));
}//2.计算二叉树深度  (树的深度：指从头结点开始到最远的叶子结点，路径上的结点数【注意：包括头结点】)
//注意：只进行遍历，不会修改树的结构，故传入一级指针
int DepthBiTree(BiTree b)
{//[1]返回条件：当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的深度记为mint m = DepthBiTree(b->lchild);//[3]递归计算右子树的深度记为nint n = DepthBiTree(b->rchild);//[4]返回子树的深度：即m和n中的较大值，并加1//加1是因为子树根结点要算上return (m > n) ? m + 1 : n + 1;
}//3.计算二叉树中结点总数
int NodeCount(BiTree b)
{//[1]返回条件：当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的结点总数记为mint m = NodeCount(b->lchild);//[3]递归计算右子树的结点总数记为nint n = NodeCount(b->rchild);//[4]返回子树的结点总数：即m和n之和，并加1//加1是因为子树根结点要算上return m + n + 1;
}//4.计算二叉树中叶子结点总数(叶子结点：左子树和右子树均为空的结点，一般在完全二叉树的最下面)
int LeadCountBiTree(BiTree b)
{//[1]返回条件1：当前根结点为空,返回0if (b == NULL){return 0;}//[2]返回条件2：当前结点为叶子结点，返回1if (b->rchild == NULL && b->lchild == NULL){return 1;}//[3]递归计算左子树和右子树的叶子结点总数记为m和nint m = LeadCountBiTree(b->lchild);int n = LeadCountBiTree(b->rchild);//[4]返回子树的叶子结点总数：即m和n之和return m+n;
}int main()
{BiTree T;CreateBiTree(&T);PreOrderTraverse(T);printf("\n");BiTree NewT;CopyBiTree(T,&NewT);PreOrderTraverse(NewT);printf("NewT的深度为：%d\n", DepthBiTree(NewT));printf("NewT的结点总数为：%d\n", NodeCount(NewT));printf("NewT的叶子结点总数为：%d\n", LeadCountBiTree(NewT));return 0;
}