首页 > 代码库 > 数据结构——树笔记1

数据结构——树笔记1

树属于非线性数据结构,它是一种层次结构:如果存在前驱节点,则是唯一
的,如果存在后继节点,则可以是多个。即树的元素之间是一对多的关系。
树是由n个节点构成的有限集合T,如果n = 0,则是空树,如果n不等于0,则
一个非空树,有且只有一个根结点root,如果n>1,则除了根结点外,其余节
点又可以划分为有限集T1,T2......Tm 其中每个有限集有是一棵树。称为子
树subtree.
树的存储结构
    双亲表示法
 孩子表示法
 孩子兄弟表示法(二叉树表示法)

森林:M棵互不相交的树的集合。

二叉树:
    二叉树的特点是每个节点至多只有两颗子树,并且二叉树的子树有左右之
 分,它的次序不能任意颠倒。
   
    二叉树的特点:
     在二叉树的第i层上至多有2的i-1次方个节点
  深度为k的二叉树至多有2的k次方-1个节点
  如果一颗二叉树的终端节点的数目为i,深度为2的节点数目为j,则i=j+1
  
 满二叉树:深度为k且节点数目为2的k次方-1的二叉树
 完全二叉树:只有在最下面一层的右边缺少若干个节点的满二叉树
 
 二叉树的存储结构:
     按顺序储存,即使用一组连续的储存单元,自上而下,自左而右的储存,每
  个空节点也会占用一个储存单元。这样的储存方式只适合完全二叉树,因为
  会浪费大量空间。
  
  链式储存结构:二叉树的节点至少包括三个域,数据域和指向左右子树的指
  针域,有时候也增加一个指向双亲的指针域来方便指向节点的双亲。
  
 二叉树的遍历:以一定的规则将非线性的节点排列成线性序列
     先序遍历二叉树:
      先访问根结点,再先序遍历左子树,最后先序遍历右子树
  中序遍历二叉树
      先中序遍历左子树,在访问根结点,最后中序遍历右子树
  后序遍历二叉树
      先后序遍历左子树,在后序遍历右子树,最后访问根结点
  
  在已知两种遍历的情况下可以得出原二叉树的形状,这两种遍历可以是先序
  和后序,也可以是中序和后序

// 二叉树的初始化
void Init_BitTree(BiTree * T)
{
    *T = NULL;
    
    return;
}

// 销毁二叉树
void Destroy_BitTree(BiTree * T)
{
    if ((*T)->lchild)
        Destroy_BitTree(&((*T)->lchild));
    if ((*T)->rchild)
        Destroy_BitTree(&((*T)->rchild));
    free(*T);
    *T = NULL;
    
    return;
}

// 二叉树的插入,通过判断LR的值,判断插入选择 
int Insert_Child(BiTree p, int LR, BiTree c)
{
    if (p)   // p指向的二叉树非空
    {
        if (0 == LR)
        {
            c->rchild = p->lchild;  // p原来的左子树称为c的右子树
            p->lchild = c;          // 子树c作为p的左子树 
        }
        else
        {
            c->rchild = p->rchild;
            p->rchild = c;
            return 1;
        } 
    } 
    
    return 0;
}

// 返回二叉树e的左孩子节点的元素值
int Left_Child(BiTree T, int e)
{
    BiTree p;
    if (T)           // 当二叉树T不为空时
    {
        p = Point(T, e);   // p是元素值e的节点的指针 
        if (p && p->lchild)  // 如果p的节点不为空,且p的左孩子节点存在  
            return p->lchild->data;   // 返回左孩子节点的元素值 
    } 
    
    return 0;
}

// 返回二叉树e的右孩子节点的元素值
int Right_Child(BiTree T, int e)
{
    BiTree p;
    if (T)           // 当二叉树T不为空时
    {
        p = Point(T, e);   // p是元素值e的节点的指针 
        if (p && p->rchild)  // 如果p的节点不为空,且p的左右孩子节点存在  
            return p->rchild->data;   // 返回右孩子节点的元素值 
    } 
    
    return 0;
}

// 在二叉树中寻找元素值为e的节点,此处假定该二叉树的节点元素值各不相同,如果找到返回该节点的地址,否则返回NULL 
BiTree Point(BiTree T, int e)
{
    if (e == T->data)
    {
        return T;
    }
    else
    {
        if (T->lchild != NULL)
            Point(T->lchild, e);
        if (T->rchild != NULL)
            Point(T->rchild, e);
    }
    
    return NULL;
}

// 删除子树操作,根据LR的值选择删除的是左子树还是右子树
int Delete_Child(BiTree p, int LR)
{
    if (p)          // 判断p不空
    {
        if (0 == LR)
            Destroy_BitTree(&(p->lchild));
        else
            Destroy_BitTree(&(p->rchild));
        return 1;
     } 
     
     return 0;
}

 

数据结构——树笔记1