数据结构-树(4)

上一章我们讲解了二叉树的创建和遍历,这一章就可以放开手脚大干一场了

线索二叉树

什么是线索二叉树:二叉链表中有2n个指针域,其中n+1个指针域存放的都是NULL,我们要把这些指针域利用起来,存放节点的前驱和后继。

用处:对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作,以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到,效率低下。在后面的中序查找和平衡二叉树中会非常有用。

结点结构

我们在原有节点的基础上又添加了LeftThread和RightThread两个标志位,因为我们需要区分每个节点的指针域内的指针究竟是指向它的孩子还是指向它的前驱或者后继。虽然增加了空间,但是减少了时间

LeftThread=0, LeftChild指向左孩子
LeftThread=1, LeftChild指向前驱
RightThread=0, RightChild指向右孩子
RightThread=1, RightChild指向后继

//
typedef enum {Link,Thread} PointerTag;

typedef struct Node
{
    char val;
    struct Node *lChild,*rChild;
    PointerTag lThread = Link,rThread = Link;//c11标准才允许初始化
} BiTreeNode,*BiTree;
//

 

二叉树线索化

不同的遍历顺序,每个节点的前驱和后继自然也不一样

中序线索化二叉树

后继:结点标志为1时,其右指针为其后继;结点标志为0时,其右子树最左下结点为其后继。
前驱:结点标志为1时,其左指针为其前驱;结点标志为0时,其左子树最右下结点为其前驱。

//
//pre是一个全局变量,时刻指向当前节点的前驱元素
void inThreadBiTree(BiTree T)
{
    if(T == NULL) return;//空树返回


//中序线索化左子树
    if(T->lChild)//可以不加,前面有判空
        inThredBiTree(T->lChild);



//线索化根节点
    if(!T->lChild)//该节点如果左孩子为NULL
    {
        T->lThread = Thread;//更改标志位
        T->lChild = pre;//左指针指向前驱元素
    }
    if(!pre->rChild)//如果前驱元素的右孩子为NULL
    {
        pre->rThread = Thread;//更改标志位
        pre->rChild = T;//右孩子指向后继元素
    }
    pre = T;//该节点成为下一个节点的前驱元素



//中序线索化右子树
    if(T->rChild)
        inThreadBiTree(T->rChild);
}
//

我们根据下图来看一下上面代码的思路,中序线索化和中序遍历思路一样一样的,我们其实只需要修改中序遍历中的visit也就是访问函数即可,具体来看一下 继续阅读

数据结构-树(3)

二叉树的存储结构

第一篇博客里已经大概讲述了一下连续存储和顺序存储,下面我们再来具体看一下

链式存储

对于二叉树来说,每个节点的度都小于等于二,所以我们在定义节点时并不会造成大量的浪费,我们完全可以用链式结构来存储,同时类比单链表和双向链表,我们可以添加一个指针域来指向它的父节点

//
typedef struct Node{
    char val;
    struct Node *lChid,*rChild;
}BiTreeNode,*BiTree;
//

 

同样类比静态链表,三叉链表也有静态形式

 

连续存储

第一篇博客里讲到了如果要连续存储一棵树需要把它转换成完全二叉树,可以是从普通二叉树转化而来,也可以是一颗普通的树通过孩子兄弟表示法转化成的二叉树转化而来 继续阅读

数据结构-树(2)

树的存储

树中的每个节点之间都有着不同的关系,如双亲,孩子,兄弟等等,我们在存储一棵树的同时也要把他们之间的关系存储进去。下面我们就要介绍四种表示方法:孩子表示法  双亲表示法   双亲孩子表示法   孩子兄弟表示法

孩子表示法

顾名思义,孩子表示法就是在每一个节点中都包含了它的孩子的信息。比如孩子的地址或者下标。

对于所有的树来说,我们都可以用链式存储,但是我们在定义节点的时候会遇到一个问题,这个节点中我们究竟需要几个指针域?一种方法就是,遍历整棵树,求出最大的度,(不知道度的看上一章),在定义节点的时候定义同样数量的的指针域,但是很明显这样会造成大量浪费。

 

同样我们可以用静态链表,也就是数组的方式来表示,但同样也会造成大量浪费,那有没有什么好的办法呢?当然有,有这么一种看着就很牛逼的方法,数组和链表相结合,虽然也有浪费,但是其实浪费是很少的

数据结构=个体+个体关系,我们要对给定的数据进行存储,其实就是存储这两部分,个体和他们之间的关系,我们把每一个个体存放到数组中,同时又对每一个个体添加了一个链表,来存放它和其它个体的关系,也就是存放它的孩子的下标。

继续阅读

数据结构-树(1)

这是一篇讲述概念的博客,但是如果你能看完,那么恭喜你,你已经知道什么是树了

定义:有且只有一个称为根的节点,有若干个互不相交的子树,这些子树本身也是一棵树。通俗来讲树就是由节点和边组成,一个节点只能有一个父节点,但是可以有多个子节点。根节点没有父节点。

专业术语:

  • 度:节点拥有的子树的个数。如1的度为3;4的度为0
  • 路径:从一个节点顺着边走到另一个节点,所经过的节点的顺序就叫做路径
  • 叶节点:没有子节点的节点称为叶子节点(度为零),简称叶节点,也叫终端节点如4,5,6,7
  • 非叶节点(非终端节点):度不为0
  • 双亲:父节点
  • 子孙:以该节点为根节点的所有节点,如:除了1之外都是1的子孙
  • 兄弟:有相同的的父节点,如:5,6
  • 堂兄弟:父节点是兄弟,如:5和7,6和7
  • 深度:从根节点到最底层节点的层数称为深度,根节点是第一层,深度也叫最大层次,或者高。如:该树深度为3

继续阅读