数据结构学习——树与二叉树

一、树的定义和基本术语

数据结构学习——树与二叉树

 1. 树是n个结点的有限集合,n=0时,称为空树。任意一棵非空树应满足:

    ①有且仅有一个特定的称为根的结点。

    ②当n>1时,其余结点可分为m个互不相交的有限集合,其中每个集合本身又是一棵树,并且称为根节点的子树

树是递归定义的数据结构

2. 结点的度——结点的分支数

    树的度——各节点的度的最大值

二、树的常见性质

1. 结点数=总度数+1

2. 度为m的树第i层最多有数据结构学习——树与二叉树个结点

3. 具有n个结点的m叉树的最小高度为数据结构学习——树与二叉树

三、二叉树

1. 满二叉树:高度为h,结点数为数据结构学习——树与二叉树

    特点:①结点i的左孩子为2i,结点i的右孩子为2i+1;结点i的父节点为数据结构学习——树与二叉树

               ②不存在度为1的结点

2. 完全二叉树:当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称为满二叉树

    特点:①只有最后两层可能有叶子节点

               ②最多只有一个度为1的结点

               ③结点i的左孩子为2i,结点i的右孩子为2i+1;结点i的父节点为数据结构学习——树与二叉树

3. 二叉排序树

    左子树上所有结点的关键字均小于根节点的关键字;右子树上所有结点的关键字均大与根节点的关键字

4. 平衡二叉树

    树上任一结点的左子树和右子树的深度之差不超过1 

5. 二叉树的性质

    ①设非空二叉树中度为0、1和2的结点个数分别为数据结构学习——树与二叉树数据结构学习——树与二叉树数据结构学习——树与二叉树,则数据结构学习——树与二叉树

        原因:假设树中的总结点数为n,则有数据结构学习——树与二叉树,又因为树的结点数=总度数+1,即数据结构学习——树与二叉树,相减得数据结构学习——树与二叉树

    ②对于完全二叉树,具有n个结点的完全二叉树的高度h为数据结构学习——树与二叉树

四、二叉树的存储结构

1. 顺序存储

二叉树的顺序存储中,一定要把二叉树的结点编号与完全二叉树对应起来,二叉树的顺序存储结构只适合存储完全二叉树

typedef struct{
    ElemType value;     //结点中的数据元素
    bool isEmpty;       //结点是否为空
}TreeNode;

2. 链式存储

struct ElemType{
    int value;
};

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;   //指向左孩子与右孩子
}BiTNode,*BiTree;

//定义一颗空树
BiTree root = NULL;

//插入根节点
root = (BiTree) malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;

//插入新节点
BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;

上述链式存储要想找到指定结点的父结点只能从根开始遍历,解决方法可以在结构体中添加父节点指针

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;   //指向左孩子与右孩子
    struct BiTNode *parent;           //父节点指针
}BiTNode,*BiTree;

五、二叉树的遍历

1. 先序遍历、中序遍历、后序遍历

数据结构学习——树与二叉树

//先序遍历,递归实现
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

2. 二叉树的层序遍历

数据结构学习——树与二叉树

遍历算法思想:

①初始化一个辅助队列

②根结点入队

③若队列非空,则对头结点出队,访问该结点,并将其左右孩子插入队尾

④重复③直至队列为空

//二叉树结点(链式存储)
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//链式队列结点
typedef struct LinkNode{
    BiTNode *data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);           //初始化辅助队列
    BiTree p;
    EnQueue(Q,T);
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL)EnQueue(Q,p->lchild);   //左孩子入队
        if(p->rchild!=NULL)EnQueue(Q,p->rchild);   //右孩子入队
    }
}

六、线索二叉树

1. 中序遍历存在的问题:对二叉树进行遍历时,必须先从根节点出发,若只知道某一分支结点或叶子结点,则不能对树完成遍历

2. 中序线索二叉树:

    n个结点的二叉树,有n+1个空链域。这些空链域可以用来记录前驱、后驱信息

数据结构学习——树与二叉树

使用标志位来定义线索:

    tag==0,指针指向孩子;

    tag==1,指针代表线索。

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;          //左、右线索标志
}ThreadNode,*ThreadTree;
ThreadNode *pre=NULL;

void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;;
    }
    pre=q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        InThread(T);              //中序线索化二叉树 
        if(pre->rchild==NULL)
            pre->rtag=1;          //处理遍历的最后一个结点
    }
}

3. 中序线索二叉树找中序后继

    ①若p->rtag==1,则next=p->rchild

    ②若p->rtag==0,则next=p的右子树中最左下结点(根据中序遍历的特点得出)

 

ThreadNode *FirstNode(ThreadNode *p){
    while(p->ltag==0)p=p->lchild;
    return p;
}

ThreadNode *NextNode(ThreadNode *p){
    if(p->rtag==0) return FirstNode(p->rchild);
    else return p->rchild;
}

//对中序线索二叉树实现中序遍历
void Inorder(ThreadNode *T){
    for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p))
        visit(p);
}

七、树的存储结构

1. 双亲表示法(顺序存储)

数据结构学习——树与二叉树

#define MAX_TREE_SIZE 100             //树中最多结点数
typedef struct{
    ElemType data;                    //树的结点定义
    int parent;                       //双亲的位置域
}PTNode;

typedef struct{
    PTNode nodes[MAX_TREE_SIZE];     //双亲表示
    int n;                            //结点数
}PTree;

优点:查指定结点的双亲很方便

缺点:查指定结点的孩子只能从头遍历

2. 孩子表示法(顺序+链式存储)

数据结构学习——树与二叉树

struct CTNode{
    int child;                   //孩子结点在数组中的位置
    struct CTNode *next;         //下一个孩子
};


typedef struct{
    ElemType data;
    struct CTNode *firstChild;   //第一个孩子
}CTBox;

typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;                     //结点数和根的位置
}CTree;

3. 孩子兄弟表示法

数据结构学习——树与二叉树

typedef struct CSNode{
    ElemType data;                            //数据域
    struct CSNode *firstchild,*nextsibling;   //第一个孩子和右兄弟指针
}CSNode,*CSTree;

八、树和森林的遍历

1. 树的先根遍历(深度优先遍历)

    若树非空,先访问根结点,再依次对每棵子树进行先根遍历

数据结构学习——树与二叉树

2. 树的后根遍历(深度优先遍历)

数据结构学习——树与二叉树

3. 树的层次遍历(广度优先遍历)

    与二叉树的层次遍历类似

九、二叉排序树

1. 啥叫二叉排序树

    左子树结点值 < 根节点值 < 右子树结点值

    对二叉排序树进行中序遍历,可以得到一个递增的有序序列

2. 二叉排序树的查找

typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree

BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){
        if(key>T->key) T=T->rchild;
        else T=T->lchild;
    }
    return T;
}

//递归实现
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL)
        return NULL;
    if(T->key==key)
        return T;
    else if(T->key<key)
        return BSTSearch(T->rchild,key);
    else
        return BSTSearch(T->lchild,key);
}

3. 二叉树的插入操作

int BST_Insert(BSTree T,int key){
    while(T!=NULL){
        if(key>T->key) 
            T=T->rchild;
        else if(key<T->key) 
            T=T->lchild;
        else 
            return 0;
    }
    T=(BSTNode *)malloc(sizeof(BSTNode));
    T->key=key;
    T->lchild=T->rchild=NULL;
    return 1;
}

//递归实现
int BSTInsert(BSTree T,int key){
    if(T==NULL){
        T=(BSTNode *)malloc(sizeof(BSTNode));
        T->key=key;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    if(T->key==key)
        return 0;
    else if(T->key>key)
        return BSTInsert(T->lchild,key);
    else
        return BSTInsert(T->rchild,key);
}

4. 二叉排序树的构造

void CreateBST(BSTree T,int str[],int n){
    T=NULL;
    int i=0;
    while(i<n){
        BSTInsert(T,str[i]);
        i++;
    }
}

5. 二叉排序树的删除

    ①若被删除结点是叶子结点,则直接删除,不会破坏二叉排序树的性质

    ②若删除结点只有一棵左子树或右子树,则让其子树代替该结点成为其父节点的子树即可

    ③若结点有左、右两棵子树,则令该结点的直接后继(右子树的最左下结点)代替该结点即可

十、平衡二叉树

1. 平衡二叉树

    树上任一结点的左子树和右子树的高度之差不超过1

    结点的平衡因子=左子树高-右子树高

typedef struct AVLNode{
    int key;              //数据域
    int balance;          //平衡因子
    struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

2. 平衡二叉树的插入(解决不平衡问题)

    在插入操作中,只要将最小不平衡子树调整平衡,则其他祖先结点都会恢复平衡

    调整最小不平衡子树:

    ①LL,在A的左孩子的左子树中插入导致不平衡

    LL平衡旋转。向右进行旋转操作,将A的左孩子代替B向右上旋转代替A成为根结点,A结点成为B的右子树的根结点,B的原右子树作为A结点的左子树

数据结构学习——树与二叉树

    ②RR,在A的右孩子的右子树中插入导致不平衡

    RR平衡旋转。向左进行旋转操作,将A的右孩子B像左上旋转代替A成为根节点,将A结点向左下旋转成为B的左子树的根节点,而B的原左子树作为A结点的右子树

数据结构学习——树与二叉树

 

    ③LR,在A的左孩子的右子树中插入导致不平衡

    以插入到C(B结点的右孩子)的左子树中为例:

    LR平衡旋转(先左后右双旋转)。先将A结点的左孩子B的右子树的根节点C向左上旋转提升到B结点的位置,然后再把C结点向右上旋转提升到A结点的位置

数据结构学习——树与二叉树

    ④RL,在A的右孩子的左子树中插入导致不平衡

     RL平衡旋转(先右后左双旋转)。先将A结点的右孩子B的左子树的根节点C向右上旋转提升到B结点的位置,然后再把C结点向左上旋转提升到A结点的位置

    数据结构学习——树与二叉树

十一、哈夫曼树

1. 结点的带权路径长度:从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积

    树的带权路径长度:树中所有叶结点的带权路径长度之和。数据结构学习——树与二叉树

数据结构学习——树与二叉树

    哈夫曼树定义:在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称为最优二叉树

2. 哈夫曼树的构建

    ①将n个结点分别作为n棵仅含一个结点的二叉树,构成森林F;

    ②构造一个新结点,从F中选取两棵根节点权值最小的树作为新结点的左、右子树,并将新结点的权值置为左、右子树上根节点的权值之和;

    ③从F中删除刚才选出的两棵树,同时将新得到的树加入F中;

    ④重复②和③,直至F中只剩下一棵树

    哈夫曼树的结点总数为2n-1

 

 

 

 

 

 

 

上一篇:数据结构——计算节点个数和二叉树高度(C语言版)


下一篇:4.3.1二叉树的遍历