一、树的结构与定义
树的结构：树结构是一种重要的非线性的数据结构，是以分支关系定义的层次结构
树的定义：树是n（n>=0）个节点的有限集，分为空树与非空树
非空树：（1）有且仅有一个称之为root的节点；
（2）除root节点以外的其余节点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为root的子树；
二叉树的定义：是n>=0个结点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树：
（1）有且仅有一个称之为根的结点；
（2）除根节点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树与右子树，且T1和T2本身都是二叉树；
二叉树与树具有一样的递归性质，区别如下：
（1）二叉树每个结点至多有两个子树（即二叉树中不存在度大于2的结点）
（2）二叉树的子树具有左右之分，其次序不能任意颠倒；
我觉得最重要的是掌握二叉树的遍历：
先序遍历
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树
1 void PreOrderTravel(node t[], int x) 2 {//先序遍历t[x]为根结点的树t 3 cout << t[x].name << " "; 4 if(t[x].lch!=-1) PreOrderTravel(t, t[x].lch); 5 if(t[x].rch!=-1) PreOrderTravel(t, t[x].rch); 6 } View Code
中序遍历
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
1 void InOrderTravel(node t[], int x) 2 {//中序遍历t[x]为根结点的树t 3 if(t[x].lch!=-1) InOrderTravel(t, t[x].lch); 4 cout << t[x].name << " "; 5 if(t[x].rch!=-1) InOrderTravel(t, t[x].rch); 6 } View Code
后序遍历
（1）后序遍历左子树
（2）后续遍历右子树
（3）访问根结点
1 void PostOrderTravel(node t[], int x) 2 {//后序遍历t[x]为根结点的树t 3 if(t[x].lch!=-1) PostOrderTravel(t, t[x].lch); 4 if(t[x].rch!=-1) PostOrderTravel(t, t[x].rch); 5 cout << t[x].name << " "; 6 } View Code
当然还有老师讲的层次遍历：
从上到下，从左到右
1 void levelOrderTraverse(node t[], int x) 2 {//层次遍历t[x]为根结点的树t 3 int tmp; 4 queue<int> q; 5 q.push(x); //根结点所在下标入栈 6 7 while(!q.empty()){ 8 tmp = q.front(); 9 q.pop(); 10 if(tmp!=-1){ 11 cout << t[tmp].name << " "; 12 q.push(t[tmp].lch); 13 q.push(t[tmp].rch); 14 } 15 } 16 } View Code
本周作业分析将会在另外一篇博文发出。
https://www.cnblogs.com/JeffKing11/p/10810543.html
感觉本章学的内容好难啊...但是还是能慢慢接受，果然老师说得对，本章较之前的章节难...（笑容逐渐消失.jpg）
本章学习到了怎么样去用STL模板，第一次接触，感觉还是不太习惯，发现本章对之前的学过的内容有所需求，需要自己去复习前面的知识，于是又觉得开始吃力了，但是依然坚持着自己打代码，自己能做出来的题能拿2/3的分都已经觉得自己很有进步了（可能老师给的题目比之前简单？？）反正就是能够自己看书，然后对着题目进行分析，从主函数开始一步一步的扩展，然后再写其他函数，从而完成每一道题。
基本达成上次的目标，希望下周能够继续的，坚持着能打完完完整整的，靠自己的一道题目吧（就是自己能有所创新的什么的吧）虽然不及大佬们打得好，打的简便，但是，还是希望自己能渐渐熟练起来，对于指针的用法还是有一些生疏，本周要继续加油。
转载于:https://www.cnblogs.com/JeffKing11/p/10800474.html
