《数据结构》第五章--树与二叉树，我们脱离了线性结构的苦海，来到树这个非线性结构的迷雾森林，学习了半个多月，是不是现在还转不过弯来？无论是各种各样的树的遍历方法，还是期末百分之九十九会考的哈夫曼树的最优wpl，都把我们无限眩晕。所以，我们应该怎么过把树这种数据结构过关呢？答案是--晕过去。
皮一下，下面进入正题，开始小结。老规矩，上图，字不好看，请挑选食用。
以上就是我的课堂笔记，不过有许多基本的知识还没有在上面，现在补充一下。
1、树和二叉树是一类具有层次关系的非线性数据结构；总结了一些二叉树容易忘记混淆的基本术语：（1）结点的度：结点拥有的子树树；（2）树的度：树的度是树内各结点度的最大值；（3）层次：结点的层次从根开始定义起，根为第一次，跟单孩子为第二层，以此类推；（4）有序树和无序树：树中结点的个子树从左到右是有次序的（即不能互换）则称为有序树 ，否则为无序树。
2、二叉树的两种特殊形态：满二叉树和完全二叉树。满二叉树是指除了叶子结点，其他结点都是有两个度的二叉树，即一棵深度为k，且有2^k-1个节点的树是满二叉树；完全二叉树是指对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；
3、树的遍历我们学了四种，即先序遍历，中序遍历，后序遍历和层次遍历，前三个遍历方法俗称深搜，最后一个则为广搜，四者的时间复杂度都为O（n）；
4、二叉树有两种存储表示：顺序存储和链式存储。顺序存储更适用于完全二叉树。而链式存储又称为二叉链表，链式存储是二叉树的常用存储方式。
5、树的存储结构有很多种，不过孩子兄弟表示对于树和森林都适用；
6、树的性质及其他特征在上图中有，在此就不多赘述了。
再来谈谈解题，选一个我们上机的题吧--7-2 深入虎穴 (30 分)
其实这题和老师课上讲的思路大抵是一致的，可是到了真刀真枪上战场的时候就GG了，发现自己总是在函数实现上出现问题，虽然停留在本层去解决问题，但是底层的函数如何实现没搞好也是不行的，在上机课的时候跟着老师一步一步走，我觉得还是很有成·成效的，不过有些地方讲的太快，而后又没有去留意，就出现了自己看不懂自己代码的情况。。。
以下是完整代码：
#include <iostream> #include <queue> using namespace std; typedef struct { int doors;//门的数量 int *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 i,j,x,n; cin>>n; bool *vi= new bool[n+1];//查找根节点 for(i=1;i<n+1;i++) { vi[i]=false; } a=new node[n+1];//为a数组申请空间 for(i=1;i<n+1;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下标往下搜索 int x,j; queue<int> q;//定义用于存放待访问的门的编号的队列 q.push(root);//根编号入队 while(!q.empty()){//当队列不为空，x=出队 x=q.front(); q.pop(); for(j=1;j<=a[x].doors;j++) q.push(a[x].p[j]);//x后面的门号入队 } return x; }
我好像没有达到上次立下来的目标（flag），不过这周就开始把题独立做一遍，还有在其他地方做一些比较经典的题目。
嗯，就这样，拜拜~
