二叉树

定义

二叉树（Binary Tree）是一种特殊的树。
特点：
1.每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）。
2.二叉树的子树有左右之分，其次序不能任意颠倒。

五种基本形态

---

性质

性质1
第i层上至多有2^i-1个结点（i>=1)。
性质2
深度为K的二叉树至多有2^k-1个结点。
性质3
对于任何一棵二叉树T，如果其终端结点数为，度为2的结点为，则=+1

拓展

完全二叉树和满二叉树是树的两种特殊形态的二叉树
一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。

满二叉树.
深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一 一对应时，称之为完全二叉树。
完全二叉树
性质4
具有n个结点的完全二叉树的深度为[ ]+1。
性质5
如果对一棵有n个结点的完全二叉树（其深度为[ ]+1）的结点按层序编号（从第1层到第[ ]+1层，每一层从左到右），则对任一结点i（1<=i<=n），有

1.如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲Parent(i)是结点[i/2]。

2.如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子Lchild(i)是结点2i。

3.如果2i+1>n，则结点i无右孩子；否则其右孩子Rchild(i)是结点2i+1。

---

二叉树两种存储结构

1.顺序存储结构
仅适用于完全二叉树。最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2^k-1的一维数组。
2.链式存储结构
设计不同的结点结构可构成不同形式的链式存储结构。二叉树的链表中的结点至少包含3个域：数据域和左、右指针域。
拓展：线索链表

---

拓展

遍历二叉树
线索二叉树

---

遍历二叉树
以下是二叉树链式存储结构，以及先序、中序、后序递归遍历输出结点的代码。
前期就先把代码放这了，后期就放到我的GitHub上去

#include <iostream>
#include <cmath>    /* 包含OVERFLOW */
#include <malloc.h> /* 包含malloc()函数 */


using namespace std;

typedef char TElemType; //二叉树结点内部数据类型 


/* 链式存储二叉树结构定义 */
typedef struct BiTNode
{
    TElemType data; //数据域
    struct BiTNode *lchild, *rchild; //指针域
} BiTNode, *BiTree;
 

/* #表示空，以先序序列构造二叉树 */
void CreateBiTree(BiTree *T)
{
    TElemType ch;
    cin>>ch;
    if(ch=='#')
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);    //继续构建左孩子结点
        CreateBiTree(&(*T)->rchild);    //继续构建右孩子结点 
    }
}
/* 先序序列输出 */ 
void PreOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    cout<<T->data;
    PreOrderTraverse(T->lchild);    //遍历左子树
    PreOrderTraverse(T->rchild);    //遍历右子树 
}
/* 中序序列输出 */ 
void InOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    InOrderTraverse(T->lchild);     //遍历左子树
    cout<<T->data;
    InOrderTraverse(T->rchild);     //遍历右子树 
}
/* 后序序列输出 */ 
void PostOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    PostOrderTraverse(T->lchild);   //遍历左子树
    PostOrderTraverse(T->rchild);   //遍历右子树
    cout<<T->data; 
}
/* 判断二叉树是否为空 */
bool IsEmpty(BiTree T)
{
    if(T != NULL)
        return false;
    else
        return true;
}
/* 销毁二叉树 */
bool DestroyBiTree(BiTree *T)
{
    BiTree lchild, rchild;  //临时保存左右孩子结点 
    if(*T == NULL)
        return false;
    lchild = (*T)->lchild;      //临时保存左孩子结点 
    rchild = (*T)->rchild;      //临时保存右孩子结点 
    (*T) = NULL;    //将被销毁结点内容提前赋值为NULL 
    free(*T);   //销毁当前结点,销毁后地址内容不会改变 
    DestroyBiTree(&lchild); //销毁左孩子结点 
    DestroyBiTree(&rchild); //销毁右孩子结点 
    return true;
}

int main()
{
    /* 测试用例1  abc##d##e#f## */
    /* 测试用例2  abcd#####*/
    BiTree T;
    CreateBiTree(&T);
    cout<<"先序序列为:";
    PreOrderTraverse(T);
    putchar('\n');
    cout<<"中序序列为:";
    InOrderTraverse(T);
    putchar('\n');
    cout<<"后序序列为:";
    PostOrderTraverse(T);
    putchar('\n');
    
    if(IsEmpty(T) == true)
        cout<<"二叉树为空!\n";
    else
        cout<<"二叉树不为空!\n";
    if(DestroyBiTree(&T) == true)
        cout<<"二叉树销毁成功!\n";
    if(IsEmpty(T) == true)
        cout<<"二叉树为空!\n";
    else
        cout<<"二叉树不为空!\n";
    return 0;
}