数据结构(3)-树和二叉树的遍历
树
树是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树的特点
- 每个节点有零个或多个子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
- 树里面没有环路(cycle)
树的概念
-
节点的度
拥有子树数称为节点的度，度为0的节点称为叶子节点或终端节点，度不为0的节点称为非终端节点或分支节点。分支节点也称为内部节点。
-
层次和深度
节点的层次从跟开始定义，根为第一层，根的孩子为第二层。树中节点节点最大层次称为树的深度或高度。
-
表示方法：
3.1. 双亲表示法：
每个节点中，附设一个指示器指示其双亲节点到链表中的位子。
3.2. 孩子表示法：
3.3. 孩子双亲表示法：
把每个节点的孩子排列起来，以单链表作为存储结构，则n个节点有n个孩子，如果是叶子节点次单链表为空，然后n个头指针又组成一个线性表
3.4. 孩子兄弟表示法
二叉树
二叉树的5大性质
性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）。
性质2：深度为k的二叉树至多有2k-1个结点（k>=1）。
性质3：对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1.
性质4：具有n个结点的完全二叉树深度为[log2n]+1 ([x]表示不 大于 x的最大整数)。
性质5：如果对一颗有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），对任意一个结点i(1<=i<=n)有：
- 如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]
- 如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
- 如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。
二叉树的存储结构
二叉树的遍历
前序遍历
规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树
递归：
void ProOrderTraverse(Tree T){
if(T == null){
return;
}
printf(“%c”,T-data);
ProOrderTraverse(T->lchild);
ProOrderTraverse(T->rchild);
}
非递归:
if (root == NULL)
return;
BTNode* p = root;
stack<BTNode*> s;
while (!s.empty() || p)
{
if (p)
{
cout << setw(4) << p->data;
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
s.pop();
p = p->rchild;
}
}
cout << endl;
中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树
递归：
void ProOrderTraverse(Tree T){
if(T == null){
return;
}
ProOrderTraverse(T->lchild);
printf(“%c”,T-data);
ProOrderTraverse(T->rchild);
}
非递归
//空树
if (root == NULL)
return;
//树非空
BTNode* p = root;
stack<BTNode*> s;
while (!s.empty() || p)
{
if (p)
{
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
s.pop();
cout << setw(4) << p->data;
p = p->rchild;
}
}
后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点
递归
void ProOrderTraverse(Tree T){
if(T == null){
return;
}
ProOrderTraverse(T->lchild);
ProOrderTraverse(T->rchild);
printf(“%c”,T-data);
}
非递归
先左子树，后右子树，再根节点。后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。直接看代码，代码中有详细的注释。
if (root == NULL)
return;
stack<BTNode*> s;
//pCur:当前访问节点，pLastVisit:上次访问节点
BTNode* pCur, *pLastVisit;
//pCur = root;
pCur = root;
pLastVisit = NULL;
//先把pCur移动到左子树最下边
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
while (!s.empty())
{
//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
pCur = s.top();
s.pop();
//一个根节点被访问的前提是：无右子树或右子树已被访问过
if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
{
cout << setw(4) << pCur->data;
//修改最近被访问的节点
pLastVisit = pCur;
}
/*这里的else语句可换成带条件的else if:
else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
*/
else
{
//根节点再次入栈
s.push(pCur);
//进入右子树，且可肯定右子树一定不为空
pCur = pCur->rchild;
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
}
}
cout << endl;
```
[数据结构导读目录](https://www.jianshu.com/p/01da5d30330c)
