树

树是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树的特点

• 每个节点有零个或多个子节点
• 没有父节点的节点称为根节点
• 每一个非根节点有且只有一个父节点
• 除了根节点外，每个子节点可以分为多个不相交的子树
• 树里面没有环路(cycle)

树的概念

1. 节点的度
   拥有子树数称为节点的度，度为0的节点称为叶子节点或终端节点，度不为0的节点称为非终端节点或分支节点。分支节点也称为内部节点。

   
   

2. 层次和深度
   节点的层次从跟开始定义，根为第一层，根的孩子为第二层。树中节点节点最大层次称为树的深度或高度。

   
   

3. 表示方法：

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)有：

1. 如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]
2. 如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3. 如果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;  
```![1A4F9754-3441-4B45-8C7E-1EC235434D35.jpg](https://img.haomeiwen.com/i5888175/849a044dc846194f.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

[数据结构导读目录](https://www.jianshu.com/p/01da5d30330c)