二叉树
第一题：二叉树叶子结点个数
[问题描述]
编写递归算法，计算二叉树中叶子结点的数目。
[输入]
一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照先序序列的顺序输入该结点的内容。对下图，其输入序列为ABD…EH…CF.I…G…。
[输出]
该二叉树叶子节点个数
[存储结构]
采用二叉链表存储。
[算法的基本思想]
创建二叉树：采用递归的方法建立一颗二叉树，再用递归的方法进行叶子节点的计数
#include <stdio.h> #include <malloc.h> #define NULL 0 typedef struct BTNode{ char a; struct BTNode *lchild; struct BTNode *rchild; }BTNode, *node; node createBTNode(node p){ //创建树,按照先序遍历 char x; scanf("%c", &x); if(x == '.'){ //是否满足为空树的情况 p = NULL; } else{ p = (node)malloc(sizeof(BTNode)); p->a = x; p->lchild = createBTNode(p->lchild); p->rchild = createBTNode(p->rchild); } return p; } int count =0; //count用来计数 void num(node p){ //递归遍历，记录叶子节点个数 if(p){ if((p->lchild == NULL) && (p->rchild) == NULL) count++; num(p->lchild); num(p->rchild); } } int main(){ printf("请输入树："); node p = createBTNode(p); num(p); printf("叶子节点个数为：%d", count); }
结果演示：
结果与分析:
优点：通过递归函数简洁明了的完成了实验要求，时间复杂度：O(n)，空间复杂度：O(n)，n为创建树的结点个数。
第二题：二叉树先序序列查找
[问题描述]
编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。
[输入]
一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照先序序列的顺序输入该结点的内容。对下图，其输入序列为ABD…EH…CF.I…G…，再输入数字K。
[输出]
位于先序遍历的第K个位置的结点
[存储结构]
采用二叉链表存储。
[算法的基本思想]
创建二叉树：采用递归的方法建立一颗二叉树，再通过递归的方式得到先序序列中第K个位置的元素
#include<stdio.h> #include<malloc.h> #define NULL 0 typedef struct BTNode{ char a; struct BTNode *lchild; struct BTNode *rchild; }BTNode, *node; node createBTNode(node &p){ //创建二叉树 char x; scanf("%c", &x); if (x == '.'){ p = NULL; } else{ p = (node)malloc(sizeof(BTNode)); p->a = x; p->lchild = createBTNode(p->lchild); p->rchild = createBTNode(p->rchild); } return p; } char pre[100]; //创建字符串数组，存储先序生成的序列 int i = 0;//计数器 void visit(node p) { //将先序序列存入字符串数组 pre[i] = p->a; i++; } void preorder(node p){ //先序遍历 if(p != NULL){ visit(p); preorder(p->lchild); preorder(p->rchild); } } int main(){ printf("请输入树："); node p = createBTNode(p); preorder(p); printf("请输入先序遍历查找的K位置元素："); int k; scanf("%d", &k); printf("先序遍历K位置元素：%c", pre[k - 1]); }
结果演示：
结果与分析:
优点：通过递归实现先序遍历，在先序遍历的同时将数据内容存入字符串，通过字符下标便可以查找元素，缺点：需要先将树的全部进行先序遍历，而且需要开辟新的空间用于存储字符串，时间复杂度：O(n)，空间复杂度：O(n)，n为创建树的结点个数。
第三题：非递归构造二叉树 + 层次遍历
[问题描述]
任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。要求：使用非递归算法的算法实现。
[输入]
一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD…EH…CF.I…G…。
[输出]
进行遍历后得到的序列
[存储结构]
采用二叉链表存储。
[算法的基本思想]
采用栈的存储结构实现非递归的方法先序序列创建二叉树，再使用队列的存储结构实现非递归的层次遍历
#include<stdio.h> #include<malloc.h> #define NULL 0 #define MAXSIZE 10 typedef struct BTNode{ char a; int flag; //flag=0左子树没有设置；flag=1左子树设置，右子树没有设置；flag=2出栈条件 struct BTNode *lchild; struct BTNode *rchild; }BTNode, *node; node createBTNode(node p){ //创建二叉树，非递归算法 BTNode *stack[MAXSIZE]; //定义栈 int top = -1; //初始化栈 p = (node)malloc(sizeof(BTNode)); //创建根节点 char x; scanf("%c", &x); p->a = x; p->flag = 0; stack[++top] = p; //根结点进栈 while(top != -1){ char x; scanf("%c", &x); if(x == '.'){ //“.”空结点的表示方式 if(stack[top]->flag == 0){ stack[top]->flag = 1; stack[top]->lchild = NULL; } else if(stack[top]->flag == 1){ stack[top]->flag = 2; stack[top]->rchild = NULL; } } else{ node q = (node)malloc(sizeof(BTNode)); q->a = x; q->flag = 0; if(stack[top]->flag == 0){ //先插左子树 stack[top]->lchild = q; stack[top]->flag = 1; stack[++top] = q; } else if(stack[top]->flag == 1){ //判断是否满足插入右子树的条件 stack[top]->rchild = q; stack[top]->flag = 2; stack[++top] = q; } } while(stack[top]->flag == 2){ //判断是否满足出栈条件，满足则连续出栈 top--; } } return p; } void showBTNode(node p){ //使用非递归，层次遍历进行实现 BTNode *queue[MAXSIZE]; int front = 0; int rear = 0; queue[rear++] = p; //根结点入队 while(front != rear){ if(queue[front]->lchild != NULL){ queue[rear++] = queue[front]->lchild; } if(queue[front]->rchild != NULL){ queue[rear++] = queue[front]->rchild; } printf("%c", queue[front]->a); front++; } } int main(){ printf("请输入树："); node p = createBTNode(p); printf("层次遍历结果为："); showBTNode(p); }
结果演示：
结果与分析:
优点：使用栈的存储结构实现了，非递归的二叉树创建，同时使用队列的数据结构实现了层次遍历，缺点代码难度较高，不易理解时间复杂度：O(n)，空间复杂度：O(n)。
心得
- 因为树可以通过递归定义自身内容，所以解决树的数据结构问题通常也可以通过递归的函数来实现。
- 递归的算法可以使得代码简洁明了，在写递归函数时要明确结束条件，掌握递归函数的执行次序。
- 很多树的操作都可基于遍历的思想经行改变，例如第二题中使用先序遍历的思想，只需修改，visit()函数，便可以实现想要的功能。
- 通过手写栈的存储结构可以代替树的创建时的递归函数，要注意在第三题中需要设置flag的特殊二叉树结构体，方便判断是否每个点都被访问过，方便点插入位置，与出栈条件的判断。
- 通过队列的结构体，进行非递归的树的层次遍历。
