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;
}