一、学习小结
这是第五章的思维导图，本章主要学习了二叉树的性质，遍历，以及哈夫曼树，理解上没有太大的问题，但在具体应用上总会出现大大小小的问题，所以仍然需要加强练习。
二、题目
（1）List Leaves
题目大意: 通过输入节点数以及每个节点的左儿子和右儿子，从上到下打印出叶节点。
题目关键：要理解输入的第几行就是代表该节点的值为几。例如样例输入中第0行的1 -代表值为0的节点左孩子的值为1，即指向第1行，右孩子为空（-1）
树模型如下:
代码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> int flag=0;//用于判断结果输出格式的 struct NodeInf{//树的节点信息，左右儿子下标 int LeftIndex; int RightIndex; }; struct BinTreeNode{//树节点 int Element;//编号 struct BinTreeNode* Left; struct BinTreeNode* Right; }; int FindTreeHead(int book[],int n)//查找树根 { for(int i=0;i<n;i++) if(book[i]==0) return i; } void CreBinTreeAndPriLeaves(int treehead,struct NodeInf nodeinf[])//层序创建树，同时输出叶子 { struct BinTreeNode* BinTree;//树 struct BinTreeNode* Temp; struct BinTreeNode* Queue[15]; int head=0,tail=0; BinTree=(struct BinTreeNode*)malloc(sizeof(struct BinTreeNode)); BinTree->Element=treehead; Queue[tail++]=BinTree; while(head<tail){ if(nodeinf[Queue[head]->Element].LeftIndex!=-1){ Temp=(struct BinTreeNode*)malloc(sizeof(struct BinTreeNode)); Temp->Element=nodeinf[Queue[head]->Element].LeftIndex; Queue[head]->Left=Temp; Queue[tail++]=Temp; } else{ Queue[head]->Left=NULL; } if(nodeinf[Queue[head]->Element].RightIndex!=-1){ Temp=(struct BinTreeNode*)malloc(sizeof(struct BinTreeNode)); Temp->Element=nodeinf[Queue[head]->Element].RightIndex; Queue[head]->Right=Temp; Queue[tail++]=Temp; } else{ Queue[head]->Right=NULL; } if(Queue[head]->Left==NULL&&Queue[head]->Right==NULL){//判断是否为叶子 if(flag) printf("%c",' '); printf("%d",Queue[head]->Element); flag=1; } head++; } putchar(' '); return; } int main() { int n; char ch; struct NodeInf nodeinf[10];//存储节点信息 int treehead;//树根 int book[10];//标记是别人儿子的节点，则未标记的就为树根 memset(book,0,sizeof(book)); scanf("%d",&n); for(int i=0;i<n;i++){//题目的节点信息是按照节点编号来的，即0到n-1，题目没说出来...... getchar(); scanf("%c",&ch); if(ch-'0'>=0&&ch-'0'<=9){ nodeinf[i].LeftIndex=ch-'0'; book[ch-'0']=1; } else nodeinf[i].LeftIndex=-1; getchar(); scanf("%c",&ch); if(ch-'0'>=0&&ch-'0'<=9){ nodeinf[i].RightIndex=ch-'0'; book[ch-'0']=1; } else nodeinf[i].RightIndex=-1; } treehead=FindTreeHead(book,n);//找树根 CreBinTreeAndPriLeaves(treehead,nodeinf); return 0; }
（2）深入虎穴
这题老师上课较为详细的分析过，使用了构造动态数组的方法
#include <iostream> #include <queue> using namespace std; typedef struct { int doors;//门的数量 int*p;//p指向门的编号 ，把p看作是一个整形数组 }node; int input(node *&a); int find(node*a,int root); int main() { node *a;//定义一个动态整形数组 int i, j, k,root; root=input(a);// 找根 cout<<find(a,root); return 0; } int input(node *&a) { int n,x,i,j; bool *vi; cin>>n; a=new node[n+1];//为a数组申请空间 vi=new bool[n+1]; for(i=1;i<=n;++i)//将VI数组初始化为false { vi[i]=false; } for(i=1;i<=n;++i){ cin>>x; a[i].doors=x; a[i].p=new int[x+1]; for(j=1;j<=x;++j){ cin>>a[i].p[j]; vi[a[i].p[j]]=true; } } //找出根在a数组的下标 for(i=1;i<=n;++i) if(!vi[i]) break; return i; } int find(node*a,int root)//层次遍历 {//从数组a的根 root下标开始往下搜索 queue<int> q;//定义用于存放待访问门的编号的 队列 int x; q.push(root); //根 编号入队 while(!q.empty()){//当队列不空 x=q.front(); q.pop();//x=出队 for(int j=1;j<=a[x].doors;j++){ q.push(a[x].p[j]); } //x后面的门的号码入队 } return x; //答案就是 X }
三、目标达成
上次定下的目标是多多巩固所学知识，多多实践。虽然时间较为匆忙，但还是完成了目标，下次的目标为巩固好二叉树以及哈夫曼树的知识