数据结构与算法

树的表示方法

孩子表示法

每个结点设置多个指针域，指针指向子树的根结点。即多重链表表示法
由于每个结点的度不相同，指针域的个数难以统一，通过两种方案解决

方案一

以树的度作为指针域的个数 ——在各个结点的度相差很大时会导致空间的浪费

适用于结点的度相差不大的情况
方案二

再取一个位置用来保存统计出的结点指针域的个数，提高了空间利用效率，但是却浪费了时间。
综上所述

采取数组和单链表综合的方法，把树中的结点采用线性存储结构连成一个数组，并将其作为头指针连接一个由孩子结点构成的链表。

结构定义代码如下

#define MAX_TREE_SIZE 100
typedef struct CTNode   //孩子结点 -> 孩子链表 
{
    int child;
    struct CTNode *next;
} *ChildPtr;
typedef struct  //表头结构 -> 表头数组
{
    TElemType data;
    ChildPtr firstchild;
} CTBox;
typedef struct  //树结构
{
    CTBox nodes [MAX_TREE_SIZE];
    int r, n;   //根的位置和结点数
}CTree;

双亲孩子表示法

由于查找某个结点的双亲需要遍历整个树，复杂度高, 升级为双亲孩子表示法

简单修改：在头指针中加入一个域用于存储该节点双亲的位置，双亲不存在值为-1。

#define MAX_TREE_SIZE 100

typedef struct CTNode  //*孩子结点 -> 孩子链表* 

{

  int child;

  struct CTNode *next;

} *ChildPtr;

typedef struct //*表头结构 -> 表头数组*

{

  TElemType data;

  ChildPtr parent, firstchild;  //*增加一个位置存储双亲的位置*

} CTBox;

typedef struct //*树结构*

{

  CTBox nodes [MAX_TREE_SIZE];

  int r, n;  //*根的位置和结点数*

}CTree;

孩子兄弟表示法

优点：把复杂的树转化成为一颗二叉树

结构定义

typedef struct CSNode

{

  TElemtype data;

  struct CSNode *firstchild, *rightsib; //每一个结点包含三个部分，数据域、长子指针、右兄弟指针

}CSNode, *CSTree;

二叉树的性质总结

性质一

$二叉树的第i层上最多有2^{k-1}个结点$

性质二

$深度为k的二叉树最多有2^{k}-1个结点。(k\ge1)$

性质三

$对任何一个二叉树，若度为2的结点个数是n_2,那么终端结点的个数是(n_2+1)$

性质四

$具有n个结点的完全二叉树的深度是[log_2n]+1 \\其[x]表示不大于x的最大整数$

性质五

$如果一个完全二叉树有n个结点，深度为[log_2n]+1，i是结点的编号(每层从左到右)，那么$ $1.如果i=1，那么i是根节点，没有双亲；如果i>1,那么其双亲是[\frac{i}{2}]$ $2.如果2i>n,那么结点i没有左孩子；否则其左孩子是结点2i$ $3.如果2i+1>n,那么结点没有右孩子，否则其右孩子是结点(2i+1)$

二叉树的存储结构

顺序存储结构

使用数组，按照二叉树的编号储存二叉树的结点

- 对于完全二叉树，由于编号的严格性，完全二叉树能够体现结点之间逻辑关系
- 对于普通二叉树，不存在的结点设置成 ^ ,但是会导致存储空间的浪费

二叉链表

二叉树的二叉链表的结点结构定义

typedef struct BiTNode 
{
    TElemType data;		//结点数据
    struct BiTNode *lchild, *rchild;		//左右孩子指针
} BiTnode, *BiTree

二叉树的建立

按照前序序列建立二叉树

函数void CreateBitree（ BiTree *T )的描述

将一般二叉树处理成扩展二叉树，并将结点的数据按照前序序列的顺序输入，若数据域为空，那么数据域中输入”#”

代码实现

void CreateBiTree (Bitree *T)
{
    ElemType ch;
    scanf("%c", &ch);
    if(ch == '#')
        *T = NULL;
    else 
    {
		*T = (BiTree)malloc(sizeof(BiTree));
        if(!*T)
        	exit(OVERFLOW);
        (*T)->data = ch;
        //需要依据前序序列的录入顺序
        //使用了递归的调用
        CreateBiTree(&(*T)->lchlid);		//构造左子树
        CreatebiTree(&(*T)->rchild);		//构造右子树
    }
}