数算---二叉树

树结构

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为节点）按分支关系组织起来的结构，很象自然界中的树那样。

一棵树（tree）是由 n（n > 0） 个元素构成的有限集合：

1. 每个元素称为节点（node）。
2. 有一个特定的节点，称为根节点或根（root）；
3. 除根节点外，其余节点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）。

4. 只有根节点的也是一棵树。下图中为一般树：

   
   树结构

如上图所示，一棵树有它的高度、深度和层数。

• 层： 根节点为第一层，最远叶子节点所在位置为最大层数。如果某一个节点位于第L层，则其子节点位于第L+1层。
• 深度：根节点为1，层数越大，深度越深，相等于层数。
• 高度：高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数。除根节点以外的同一层子节点的高度可能不一样，这取决于子节点下的最远叶子节点的深度。
• 节点的度：节点的度等于节点拥有子树的个数。如图中的根节点的度为3，B节点的度为2，D节点的度为3。
• 树的度：树的度是树内各节点度的最大值，上图中树的度应该是3。
• 叶子：度为0的节点称为叶子节点或终端节点，例如K,J,F...
• 非终端节点：终端节点和根节点之外树内部节点都是非终端节点。
• 有序树和⽆序树:如果将树的结点的各⼦树看成从左到右是有次序的(即不能互换)则称为该树为有序树, 否则是⽆序树。就像赌神家五房太太一样，从大到小是有顺序的。

二叉树（Binary Tree）

二叉树：每个节点最多只能有两棵子树，且有左右之分。逻辑上二叉树有五种基本形态：

1. 空二叉树。
2. 只有一个根节点的二叉树。
3. 只有左子树的二叉树。
4. 只有右子树的二叉树。

5. 完全二叉树。

   
   二叉树形态

满二叉树
如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0（叶子节点）的节点在同一层上，则这棵二叉树为满二叉树。

满二叉树
完全二叉树
深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。
完全二叉树
特性：最远的叶子节点只可能存在在最大两层中，像满二叉树那样所有叶子节点都在最大的一层中。

二叉树特性：

• 在二叉树的第 i 层上最多有 2^(i - 1) 个节点。
• 深度为 k 的二叉树最多有（2^k） - 1 个节点（k >= 1）。
• 对于任何一棵二叉树T，如果其叶子节点个数为m，度为2的节点个数为n，则m = n + 1。
• 具有n个节点的完全二叉树深度为 （log2(n)）+ 1;
• 对具有n个节点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树的所有节点从1开始编号，则对于任意的序号为i的节点有:
  A.如果i>1，那么序号为i的节点的双亲节点序号为i/2；
  B.如果i=1，那么序号为i的节点为根节点，无双亲节点；
  C.如果2i<=n，那么序号为i的节点的左孩子节点序号为2i；
  D.如果2i>n，那么序号为i的节点无左孩子；
  E.如果2i+1<=n，那么序号为i的节点右孩子序号为2i+1；
  F.如果2i+1>n，那么序号为i的节点无右孩子。

二叉树的遍历

可根据根节点的访问顺序以及不通同的规则分为以下四种方式：
1、前序遍历
规则：若二叉树为空，则空操作返回；否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。先左后右。

2、中序遍历
规则：若二叉树为空，则空操作返回；否则从根节点（注意不是先访问根节点），中序遍历根节点的左子树，然后再访问根节点，最后中序遍历右子树。

3、后序遍历
规则：若二叉树为空，则空操作返回；否则从左到右先叶子节点的方式遍历左右子树，最后访问根节点。

4、层序遍历
规则：若二叉树为空，则空操作返回；否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，从左到右的顺序对节点逐个访问。

链表实现二叉树

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

#pragma mark--二叉树构造
int indexs = 1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;
//字符串构建字符数组，T[0]为字符串长度
Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

#pragma mark--二叉树基本操作

typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode  /* 结点结构 */
{
    CElemType data;        /* 结点数据 */
    struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;

/*7.1 打印数据*/
Status visit(CElemType e)
{
    printf("%c ",e);
    return OK;
}

/* 7.2 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
    *T=NULL;
    return OK;
}

/* 7.3 销毁二叉树
 初始条件: 二叉树T存在。
 操作结果: 销毁二叉树T
 */
void DestroyBiTree(BiTree *T)
{
    if(*T)
    {
        /* 有左孩子 */
        if((*T)->lchild)
            DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
        
        /* 有右孩子 */
        if((*T)->rchild)
            DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
        
        free(*T); /* 释放根结点 */
        
        *T=NULL; /* 空指针赋0 */
    }
}
#define ClearBiTree DestroyBiTree

/*7.4 创建二叉树
 按前序输入二叉树中的结点值(字符),#表示空树;
 */
void CreateBiTree(BiTree *T){
    
    CElemType ch;
    
    //获取字符
    ch = str[indexs++];
    
    //判断当前字符是否为'#'
    if (ch == '#') {
        *T = NULL;
    }else
    {
        //创建新的结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        //是否创建成功
        if (!*T) {
            exit(OVERFLOW);
        }
        
        /* 生成根结点 */
        (*T)->data = ch;
        /* 构造左子树 */
        CreateBiTree(&(*T)->lchild);
        /* 构造右子树 */
        CreateBiTree(&(*T)->rchild);
    }
    
}


/*
 7.5 二叉树T是否为空;
 初始条件: 二叉树T存在
 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE
 */
Status BiTreeEmpty(BiTree T)
{
    if(T)
        return FALSE;
    else
        return TRUE;
}

/*
 7.6 二叉树T的深度
 初始条件: 二叉树T存在
 操作结果: 返回T的深度
 */
int BiTreeDepth(BiTree T){
    
    int i,j;
    if(!T)
        return 0;
    
    //计算左孩子的深度
    if(T->lchild)
        i=BiTreeDepth(T->lchild);
    else
        i=0;
    
    //计算右孩子的深度
    if(T->rchild)
        j=BiTreeDepth(T->rchild);
    else
        j=0;
    
    //比较i和j
    return i>j?i+1:j+1;
}

/*
 7.7 二叉树T的根
 初始条件: 二叉树T存在
 操作结果: 返回T的根
 */
CElemType Root(BiTree T){
    if (BiTreeEmpty(T))
        return Nil;
    
    return T->data;
}

/*
 7.8 返回p所指向的结点值;
 初始条件: 二叉树T存在，p指向T中某个结点
 操作结果: 返回p所指结点的值
 */
CElemType Value(BiTree p){
    return p->data;
}

/*
 7.8 给p所指结点赋值为value;
 初始条件: 二叉树T存在，p指向T中某个结点
 操作结果: 给p所指结点赋值为value
 */
void Assign(BiTree p,CElemType value)
{
    p->data=value;
}

#pragma mark--二叉树遍历
/*
 7.8  前序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 前序递归遍历T
 */

void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
    PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}


/*
 7.9  中序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 中序递归遍历T
 */
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild); /* 中序遍历左子树 */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}

/*
 7.10  后序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 中序递归遍历T
 */
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */
    PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}


//测试代码
    BiTree T;
    CElemType e1;
    
    InitBiTree(&T);
    
    StrAssign(str,"ABDH#K###E##CFI###G#J##");
    
    CreateBiTree(&T);
    printf("二叉树是否为空%d(1:是 0:否),树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    
    e1=Root(T);
    printf("二叉树的根为: %c\n",e1);
    
    printf("\n前序遍历二叉树:");
    PreOrderTraverse(T);
    
    printf("\n中序遍历二叉树:");
    InOrderTraverse(T);
    
    printf("\n后序遍历二叉树:");
    PostOrderTraverse(T);
    
    printf("\n");