你的位置:首页 > 软件开发 > Java > 线索二叉树

线索二叉树

发布时间:2016-05-28 13:00:11
1. 基本概念 在链式存储中,发现二叉链表中存在大量的空指针,如果利用这些空指针指向其直接前驱或后继的指针,则可以更方便地运用某些二叉树操作算法。二叉树的线索化,是为了加快查找结点前驱和后继的速度。 在有N个结点的二叉树中,存在N+ ...

线索二叉树

1. 基本概念

      在链式存储中,发现二叉链表中存在大量的空指针,如果利用这些空指针指向其直接前驱或后继的指针,则可以更方便地运用某些二叉树操作算法。二叉树的线索化,是为了加快查找结点前驱和后继的速度。

      在有N个结点的二叉树中,存在N+1个空指针。每个叶结点有2个空指针,度为1的结点有1个空指针,总的空指针为2N0+N1,又有N0=N2+1,所以总的空指针为N0+N1+N2+1=N+1。

      二叉树线索化规则:若无左子树,令lchild指向其前驱结点;若无右子树,令rchild指向其后继结点。如图,增加两个标志域,用来表明当前指针指向左右结点还是前驱后继结点。

 线索二叉树

其中标志位含义为:

 线索二叉树

线索二叉树的结点:

private class Node{  int data;  Node lchild, rchild;  int ltag = 0, rtag = 0;}

原标题:线索二叉树

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录