以二叉链表表示二叉树,建立一棵二叉树(算法5.3); 2.输出二叉树的中序遍历结果(算法5.1); 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度(算法5.5); 6.统计二叉树的叶结点个数;完整代码
时间: 2024-05-22 11:08:34 浏览: 133
erchashubianli.rar_用二叉链表 进行 二叉树 遍历
好的,以下是回答您的问题:
1. 以二叉链表表示二叉树,建立一棵二叉树的算法(算法5.3):
建立一棵二叉树需要使用递归方法,首先需要定义一个二叉树的结构体:
```
typedef struct BiTNode{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
```
然后,我们可以编写建立二叉树的递归函数:
```
void CreateBiTree(BiTree *T){
int ch;
scanf("%d", &ch);
if(ch == -1){ // 如果输入-1,则表示该节点为空
*T = NULL;
}else{
*T = (BiTree)malloc(sizeof(BiTNode));
if(!(*T)){
exit(-1); // 内存申请失败
}
(*T)->data = ch; // 为该节点赋值
CreateBiTree(&(*T)->lchild); // 递归建立左子树
CreateBiTree(&(*T)->rchild); // 递归建立右子树
}
}
```
2. 输出二叉树的中序遍历结果(算法5.1):
中序遍历是指先访问左子树,再访问根节点,最后访问右子树。可以使用递归实现中序遍历:
```
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild); // 遍历左子树
printf("%d ", T->data); // 输出根节点
InOrderTraverse(T->rchild); // 遍历右子树
}
}
```
3. 输出二叉树的前序遍历结果:
前序遍历是指先访问根节点,再访问左子树,最后访问右子树。同样可以使用递归实现:
```
void PreOrderTraverse(BiTree T){
if(T){
printf("%d ", T->data); // 输出根节点
PreOrderTraverse(T->lchild); // 遍历左子树
PreOrderTraverse(T->rchild); // 遍历右子树
}
}
```
4. 输出二叉树的后序遍历结果:
后序遍历是指先访问左子树,再访问右子树,最后访问根节点。同样可以使用递归实现:
```
void PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild); // 遍历左子树
PostOrderTraverse(T->rchild); // 遍历右子树
printf("%d ", T->data); // 输出根节点
}
}
```
5. 计算二叉树的深度(算法5.5):
二叉树的深度是指从根节点到最远叶子节点的距离。可以使用递归求解:
```
int TreeDepth(BiTree T){
int depth = 0;
if(T){
int left_depth = TreeDepth(T->lchild); // 求解左子树的深度
int right_depth = TreeDepth(T->rchild); // 求解右子树的深度
depth = 1 + (left_depth > right_depth ? left_depth : right_depth); // 取左右子树深度较大值+1即为整棵二叉树的深度
}
return depth;
}
```
6. 统计二叉树的叶结点个数:
叶结点是指没有子节点的节点,可以使用递归统计:
```
int CountLeaves(BiTree T){
if(!T){ // 如果是空树,则叶结点个数为0
return 0;
}else if(!T->lchild && !T->rchild){ // 如果是叶结点,则返回1
return 1;
}else{ // 否则继续递归统计左右子树中的叶结点个数
return CountLeaves(T->lchild) + CountLeaves(T->rchild);
}
}
```
完整代码如下:
阅读全文