精华内容
下载资源
问答
  • 前驱节点,指的是以中序遍历,遍历二叉树,某一个节点的前一个节点,被称为其前驱节点。 也就是,某一节点的左子树的右子节点的右子节点的右节点。。。 特殊情况,如果是二叉搜索树,则前驱节点是按从小到大的顺序,...

    前驱节点

    何为前驱节点?
    前驱节点,指的是以中序遍历,遍历二叉树,某一个节点的前一个节点,被称为其前驱节点。
    也就是,某一节点的左子树的右子节点的右子节点的右节点。。。

    特殊情况,如果是二叉搜索树,则前驱节点是按从小到大的顺序,比其前面一个节点。

    思路:

    如果node.left != null;
    则循环,node.left.right.right.right…直至为空,则找到了其前驱节点。

    如果node.left == null;
    如果node.parent == null;则没有前驱
    如果node.parent != null;则前驱节点为node.parent.parent.parent…;
    终止条件:node在parent的右子树中

    public static TreeNode preNode(TreeNode root)
    	{
    		if(root == null) return null;
    		
    		TreeNode node = root.left;
    		
    		if(node != null) {
    			while(node.right != null) {
    				node = node.right;
    			}
    			return node;
    		}else {
    			while(node.parent != null && node == node.parent.left) {
    				node = node.parent;
    			}
    			//来到这里包含两种情况:
    			//node.parent == null
    			//node = node.parent.right
    			
    			return node.parent;
    		}
    	}
    	
    

    后继节点

    中序遍历的某一节点的后一个节点,被称为后继节点
    参照前驱节点,不难写成后继节点

    思路:

    如果node.right != null;
    则循环,node.right.left.left.left…直至为空,则找到了其后继节点。

    如果node.right == null;
    如果node.parent == null;则没有后继
    如果node.parent != null;则后继节点为node.parent.parent.parent…;
    终止条件:node在parent的左子树中

    public static TreeNode postNode(TreeNode root) {
    		if(root == null) return null;
    		
    		TreeNode node = root.right;
    		if(node != null) {
    			while(node.left != null)
    			{
    				node = node.left;
    			}
    			return node;
    		}else {
    			while(node.parent != null && node == node.parent.right)
    			{
    				node = node.parent;
    			}
    			
    			return node.parent;
    		}
    	}
    
    展开全文
  • 线索二叉树的运算 1.查找某结点*p在指定次序下的前趋和后继结点 (1)在中序线索二叉树中,查找结点*p的中序后继结点  在中序线索二叉树中,查找结点*p的中序后继结点分两种情形: ①若*p的右子树空(即p->rtag...

    转自文库

     

    线索二叉树的运算

    1.查找某结点*p在指定次序下的前趋和后继结点
    (1)在中序线索二叉树中,查找结点*p的中序后继结点
      在中序线索二叉树中,查找结点*p的中序后继结点分两种情形:
    ①若*p的右子树空(即p->rtag为Thread),则p->rchild为右线索,直接指向*p的中序后继。
      【例】下图的中序线索二叉树中,结点D的中序后继是A。


           
    ②若*p的右子树非空(即p->rtag为Link),则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩子开始,沿该孩子的左链往下查找,直至找到一个没有左孩子的结点为止,该结点是*p的右子树中"最左下"的结点,即*P的中序后继结点。
      【例】上图的中序线索二叉树中:
    A的中序后继是F,它有右孩子;
    F的中序后继是H,它无右孩子;
    B的中序后继是D,它是B的右孩子。  
      在中序线索二叉树中求中序后继结点的过程可【参见动画演示】,具体算法如下:

    BinThrNode*InorderSuccessor(BinThrNode *p)
          {//在中序线索树中找结点*p的中序后继,设p非空
             BinThrNode *q;
             if (p->rtag==Thread) //*p的右子树为空
                  Return p->rchild; //返回右线索所指的中序后继
             else{
                  q=p->rchild;//从*p的右孩子开始查找
                  while (q->ltag==Link)
                       q=q->lchild;//左子树非空时,沿左链往下查找
                  return q;//当q的左子树为空时,它就是最左下结点
                 }//end if
          }


        该算法的时间复杂度不超过树的高度h,即O(h)。

     

    (2)在中序线索二叉树中查找结点*p的中序前趋结点
      中序是一种对称序,故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称。具体情形如下:
    ①若*p的左子树为空,则p->1child为左线索,直接指向*p的中序前趋结点;
      【例】上图所示的中序线索二叉树中,F结点的中序前趋结点是A
    ②若*p的左子树非空,则从*p的左孩子出发,沿右指针链往下查找,直到找到一个没有右孩子的结点为止。该结点是*p的左子树中"最右下"的结点,它是*p的左子树中最后一个中序遍历到的结点,即*p的中序前趋结点。
      【例】上图所示中序线索二叉树中,结点E左子树非空,其中序前趋结点是I
      在中序线索二叉树中求中序前趋结点的过程可【参见动画演示】,具体算法如下:
       

    BinThrNode *Inorderpre(BinThrNode *p)
          {//在中序线索树中找结点*p的中序前趋,设p非空
             BinThrNode *q;
            if (p->ltag==Thread) //*p的左子树为空
                  return p->lchild; //返回左线索所指的中序前趋
             else{
                  q=p->lchild;//从*p的左孩子开始查找
                  while (q->rtag==Link)
                       q=q->rchild;//右子树非空时,沿右链往下查找
                  return q;//当q的右子树为空时,它就是最右下结点
                 }//end if
          }


      由上述讨论可知:对于非线索二叉树,仅从*p出发无法找到其中序前趋(或中序后继),而必须从根结点开始中序遍历,才能找到*p的中序前趋(或中序后继)。线索二叉树中的线索使得查找中序前趋和中序后继变得简单有效。

     

    (3)在后序线索二叉树中,查找指定结点*p的后序前趋结点
      在后序线索二叉树中,查找指定结点*p的后序前趋结点的具体规律是:
    ①若*p的左子树为空,则p->lchild是前趋线索,指示其后序前趋结点。
       【例】在下图所示的后序线索二叉树中,H的后序前趋是B,F的后序前趋是C。

     

    ②若*p的左子树非空,则p->lchild不是前趋线索。由于后序遍历时,根是在遍历其左右子树之后被访问的,故*p的后序前趋必是两子树中最后一个遍历结点。
      当*p的右子树非空时,*p的右孩子必是其后序前趋
      【例】在上图所示的后序线索二叉树中,A的后序前趋是E;
      当*p无右子树时,*p的后序前趋必是其左孩子
      【例】在上图所示的后序线索二叉树中,E的后序前趋是F

     

    (4)在后序线索二叉树中,查找指定结点*p的后序后继结点
      具体的规律:
    ①若*p是根,则*p是该二叉树后序遍历过程中最后一个访问到的结点。*p的后序后继为空
    ②若*p是其双亲的右孩子,则*p的后序后继结点就是其双亲结点
      【例】上图所示的后序线索二叉树中,E的后序后继是A。
    ③若*p是其双亲的左孩子,但*P无右兄弟,*p的后序后继结点是其双亲结点
      【例】上图所示的后序线索二叉树中,F的后序后继是E。
    ④若*p是其双亲的左孩子,但*p有右兄弟,则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点,它是该子树中"最左下的叶结点"
      【例】上图所示的后序线索二叉树中,B的后序后继是双亲A的右子树中最左下的叶结点H
     

    注意:
    F是孩子树中"最左下"结点,但它不是叶子。
      由上述讨论中可知:在后序线索树中,仅从*p出发就能找到其后序前趋结点;要找*p的后序后继结点,仅当*p的右子树为空时,才能直接由*p的右线索p->rchild得到。否则必须知道*p的双亲结点才能找到其后序后继。因此,如果线索二叉树中的结点没有指向其双亲结点的指针,就可能要从根开始进行后序遍历才能找到结点*P的后序后继。由此,线索对查找指定结点的后序后继并无多大帮助

    展开全文
  • 数据结构笔记——线索二叉树前驱/后继

    千次阅读 多人点赞 2020-05-30 21:17:44
    二、中序线索二叉树中找中序前驱 三、先序线索二叉树找先序后继 四、先序线索二叉树找先序前驱 五、后序线索二叉树找后序前驱 六、后序线索二叉树找后序后继 七、总结 一、中序线索二叉树找中序后继 在中序...

    目录

    一、中序线索二叉树找中序后继

    二、中序线索二叉树中找中序前驱

    三、先序线索二叉树找先序后继

    四、先序线索二叉树找先序前驱

    五、后序线索二叉树找后序前驱

    六、后序线索二叉树找后序后继

    七、总结

    一、中序线索二叉树找中序后继

    在中序线索二叉树中找到指定结点*p的中序后继next

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

    ②若p->rtag == 0

    //找到以P为跟的子树中,第一个被中序遍历的结点
    ThreadNode *Firstnode(ThreadNode *p){
        //循环找到最左下结点(不一定是叶子结点)
        while(p->ltag == 0)
            p = p->lchild;
        return p;
    }
    
    //在中序线索二叉树中找到结点p的后继结点
    ThreadNode *Nextnode(ThreadNode *p){
        //右子树中最左下结点
        if(p->rtag == 0)
            return Firstnode(p->rchild);
        else
            return p->rchild;
    }
    
    //对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)  空间复杂度O(1)
    void Inorder(ThreadNode *T){
        for(ThreadNode *p = Firstnode(T);p != NULL; p = Nextnode(p))
            visit(p);
    }

    二、中序线索二叉树中找中序前驱

    在中序线索二叉树中找到指定结点*p的中序前驱pre

    ①若p->ltag == 1,则pre = p->lchild

    ②若p->ltag == 0

    //找到以P为跟的子树中,最后一个被中序遍历的结点
    ThreadNode *Lastnode(ThreadNode *p){
        //循环找到最右下结点(不一定是叶子结点)
        while(p->rtag == 0)
            p = p->rchild;
        return p;
    }
    
    //在中序线索二叉树中找到结点p的前驱结点
    ThreadNode *Prenode(ThreadNode *p){
        //左子树中最右下结点
        if(p->ltag == 0)
            return Lastnode(p->lchild);
        else
            return p->lchild;
    }
    
    //对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)  空间复杂度O(1)
    void RevInorder(ThreadNode *T){
        for(ThreadNode *p = Lastnode(T);p != NULL; p = Prenode(p))
            visit(p);
    }

    三、先序线索二叉树找先序后继

    在先序线索二叉树中找到指定结点*p的先序后继next

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

    ②若p->rtag == 0

    四、先序线索二叉树找先序前驱

    在先序线索二叉树中找到指定结点*p的先序前驱pre

    ①若p->ltag == 1,则next = p->lchild

    ② 若p->ltag = 0

    前提:改用三叉链表可以找到父节点

    ①如果能找到p的父节点,且p是左孩子

    ②如果能找到p的父节点,且p是右孩子,其左兄弟为空

    ③如果能找到p的父节点,且p是右孩子,其左兄弟非空

    ④如果p是根结点,则p没有先序前驱

    五、后序线索二叉树找后序前驱

    在后序线索二叉树中找到指定结点*p的后序前驱pre

    ①若p->ltag == 1,则pre = p->lchild

    ②若p->ltag == 0

    六、后序线索二叉树找后序后继

    在后序线索二叉树中找到指定结点*p的后序后继next

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

    ②若p->rtag == 0

    前提:改用三叉链表可以找到父节点

    ①如果能找到p的父节点,且p是右孩子

    ②如果能找到p的父节点,且p是左孩子,且右兄弟为空

    ③如果能找到p的父节点,且p是左孩子,且右兄弟非空

    ④如果p是根节点,则p没有后序后继

    七、总结

    展开全文
  • 树是一种典型的数据结构(逻辑结构),可以用来描述分支结构,属于一种分层、非线性结构。树的定义是递归的,因此树是一种递归的数据结构。每个结点有唯一的前驱结点,有一个或多个后继结点。(nnn个节点有n−1n-1n...

    在这里插入图片描述

    树是一种典型的数据结构(逻辑结构),可以用来描述分支结构,属于一种分层、非线性结构。树的定义是递归的,因此树是一种递归的数据结构。每个结点有唯一的前驱结点,有一个或多个后继结点。( n n n个节点有 n − 1 n-1 n1条边)

    基本术语:

    1. :结点的子结点的个数;
    2. 树的度:树种最大的度数;
    3. 分支结点:度大于 0 0 0的结点;
    4. 叶子结点:度为 0 0 0的结点;
    5. 结点层次:根结点为第一层,往下递增;
    6. 结点高度:从叶结点开始自底向上逐层累加;
    7. 结点深度:从根结点自顶向下逐层累加;
    8. 树的高度(深度):树中结点的最大层数;
    9. 有序树:从左到右,子树有序;交换子结点位置树不同;
    10. 无序树:交换子结点后树是相同的;
    11. 路径:两个结点之间所经过的节点序列,不包含边;路径是自上而下的(树的分支是有向的:从双亲指向孩子);
    12. 路径长度:路径上经历的边的数量;
    13. 森林:m棵互不相交的树的集合;

    性质:

    1. 树中的结点数=所有结点度数(等价于所有的非根结点数) + 1 +1 +1

    2. 度为 m m m的树中第 i i i层至多有: m i − 1 m^{i-1} mi1个结点

    二叉树的性质
    3. 高度为 h h h m m m叉树至多有 ( m h − 1 ) / ( m − 1 ) (m^h-1)/(m-1) (mh1)/(m1)个结点

    1. 具有 n n n个结点的 m m m叉树的最小高度为 l o g m ( n ( m − 1 ) + 1 ) log_m(n(m-1)+1) logm(n(m1)+1)(向上取整)

    在这里插入图片描述

    二叉树:

    五种基本形态:空树、根节点、根节点-左子树、根节点-右子树、根节点-左子树-右子树

    二叉树 vs 度为2的有序树:

    1. 二叉树可以为空,度为2的有序树至少有3个结点
    2. 二叉树孩子结点有左右之分,度为2的有序树的孩子结点次序是相对的(一个结点的时候,不区分左右)

    特殊二叉树:

    1. 满二叉树:高度为 h h h,含有 2 h − 1 2^h-1 2h1个结点(公式 ( m h − 1 ) / ( m − 1 ) (m^h-1)/(m-1) (mh1)/(m1) m = 2 m=2 m=2),每一层都有最多结点,最后一层全是叶子结点。结点 i i i:左孩子 2 i 2i 2i,右孩子 2 i + 1 2i+1 2i+1;孩子结点 i i i存在,双亲编号为 i / 2 i/2 i/2 取整数满二叉树

    2. 完全二叉树:高度为 h h h,有 n n n个结点的二叉树,当且仅当每个结点高度为 h h h满二叉树中编号 1 − n 1-n 1n的结点一一对应(不能产生错位,即满二叉树的子集)。

    完全二叉树

    • i ≤ n / 2 i\le n/2 in/2,则结点 i i i为分支结点,否则为叶子结点;( i = n / 2 i=n/2 i=n/2为最后一个结点的双亲结点,比该结点的双亲结点小,则为分支结点(1、2、3、4、5),大则为叶子结点(7、8、9、10、11、12))
    • 叶子结点只可能在层次最大的两层上出现。对于最大层次的叶子结点(8、9、10、11、12),都一此排在左边位置上。
    • 度为 1 1 1的结点若存在,则可能有一个,且是编号最大的分支结点(6),并且孩子结点一定是左结点。
    1. 二叉排序树:一棵二叉树,若树非空则具有性质——对任意结点存在左子树或又子树,则其左子树上左右关键字均小于该结点,右子树上所有结点的关键字均大于该结点。

    排序二叉树

    1. 平衡二叉树:树上任意结点(非根节点)的左子树和右子树的深度之差不超过 1 1 1(蓝色)。

      平衡二叉树

    二叉树性质:

    1. 非空二叉树的叶子结点数等于度为 2 2 2的结点数 + 1 +1 +1,即 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1。( n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0+n1+n2
    2. 非空二叉树上第 k k k层上至多有 2 ( k − 1 ) 2^(k-1) 2(k1)个结点( k ≥ 0 k\geq0 k0
    3. 高度为 h h h的二叉树至多有 2 h − 1 2^h-1 2h1个结点( h ≥ 0 h\geq0 h0

    性质1
    性质2

    展开全文
  • 主要介绍了C语言数据结构之线索二叉树及其遍历的相关资料,为了加快查找节点的前驱和后继。对二叉树的线索化就是对二叉树进行一次遍历,在遍历的过程中检测节点的左右指针是否为空,如果是空,则将他们改为指向前驱和...
  • 数据结构--二叉树--详解

    万次阅读 多人点赞 2021-03-19 01:16:44
    树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点,称为根结点,根节点没有...
  • 中序线索二叉树找中序后继: 在中序线索二叉树中找到指定结点*p的中序后继next 1.若p->tag=1,则next=p->rchild 2.若p->tag=0,则next=p的右子树中最左下结点。 //找到以p为根的子树中,第一个被中序遍历的...
  • 线索二叉树应用实验 实验...线索二叉树是为了快速求解二叉树中结点在指定次序下的前驱和后继而将二叉链表中空的左右孩子指针分别改为指向其前驱和后继结点而得到的结构反映了运算对数据结构的设计的影响因此首先要了解
  • 文章目录二叉树遍历原理二叉树遍历方法前序遍历中序遍历中序遍历算法后序遍历后续遍历算法层序遍历二叉树遍历的性质 ...二叉树的遍历次序不同于线性结构,最多也就是从头到尾,循环,双向等简单的遍历方式。树的结
  • 在这里插入代码片 ```#include <stdio.h>... // 前驱线索->左孩子、后继线索->右孩子 struct ThreadNode *lchild, *rchild; // tag为0表示孩子,tag为1表示线索 int ltag, rtag; }
  • 二叉树的概念以及特性2.1 二叉树的概念2.2两种特殊的二叉树2.3二叉树的性质2.4二叉树的存储2.5二叉树的基本操作2.5.1前序遍历2.5.2 中序遍历2.5.3 后序遍历2.5.4 层序遍历3.二叉树的基本操作3.1 获取二叉树中节点个...
  • 该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode {DataType data; struct ...
  • 数据结构——线索二叉树 指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)。 请看图6-10-2,我们把这棵二叉树进行中序遍历后,将所有的空指针域...
  • 数据结构与算法(二叉树) 树型结构是一种重要的非线性结构,在我们的客观世界和现实生活中大量存在。 在计算机领域也常用到树形结构。例如编译程序中用树表示源程序语法结构,数据库系统中用树组织信息等等。 我们...
  • 数据结构二叉树实现及部分操作

    千次阅读 2017-12-02 22:35:13
    二叉树之前,我们先来看看树的定义树:由N(N>=0)个结点构成的集合。 对N>1的树: 1、有一个特殊的结点,称为根结点,根节点没有前驱结点 2、除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、...
  • 数据结构 - 二叉树 - 面试中常见的二叉树算法题

    万次阅读 多人点赞 2018-01-17 21:16:09
    数据结构 - 二叉树 - 面试中常见的二叉树算法题 数据结构是面试中必定考查的知识点,面试者需要掌握几种经典的数据结构:线性表(数组、链表)、栈与队列、树(二叉树、二叉查找树、平衡二叉树、红黑树)、图。 ...
  • 数据结构——二叉树

    千次阅读 2019-07-18 10:26:32
    二叉树的顺序表示 Lineartree.c #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define NIL 0 //初始化二叉树时使用 //判断函数的返回值时使用 ...
  • 数据结构学习之:线索二叉树线索二叉树1、线索二叉树概述1.1 线索二叉树的使用背景1.2线索二叉树创建原理2、线索二叉树代码实现2.1 线索二叉树创建 线索二叉树 1、线索二叉树概述 1.1 线索二叉树的使用背景 对于一颗...
  • 参考: 大话数据结构 http://blog.csdn.net/luckyxiaoqiang/article/details/7518888 一、相关概念 二、二叉树相关问题
  • C语言 数据结构 树和二叉树

    千次阅读 2018-02-06 18:29:01
    因此存储结构的设计是一个非常灵活的过程,一个存储结构设计是否合理,取决于数据结构的运算是否简单、方便、时间空间复杂度低。一定要注意原则:适合就好。不是越复杂越好。   孩子表示法思路: 把每个节点...
  • 二叉树的线索化的目的就是为了方便二叉树节点的遍历和访问,那么既然要遍历,那么也就说明有顺序,也就是前后,但是既然提到了线索化,那么还是会很好奇线索化后某个节点的前驱节点、后继节点应该怎么取获取。...
  • 内容: 1、二叉树的建立 2、二叉树的中序线索化...结构: #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; typedef char Elemtype; typedef enum { Link,Thread //枚举型,Link默认值为0,Th...
  • 数据结构-二叉树

    2020-08-17 13:12:47
    数据结构 二叉树 二叉树 二叉树(BinaryTree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,...
  • 目录 序章 树 树的定义 树的基本术语 ...二叉树的储存结构 顺序储存结构 二叉树的链式储存结构 二叉树的遍历 创建二叉树 序章 先来了解一下树形结构的特点 树 树的定义 定义:树是...
  • C语言数据结构 中序二叉树 前言: 线索二叉树主要是为了解决查找结点的线性前驱与后继不方便的难题。它只增加了两个标志性域,就可以充分利用没有左或右孩子的结点的左右孩子的存储空间来存放该结点的线性前驱结点与...
  • 数据结构---二叉树的详解

    万次阅读 多人点赞 2017-02-24 21:44:02
    Time:2017/2/221、名词解释树是使用了递归定义的数据结构,树的子树还是树,其结构如下图所示: 度:结点拥有的子树数目,例如上图结点A的度为3,结点E的度为0 叶子或终端结点:度为0的结点(没有子树的结点) 树的...
  • 文章目录一.树与二叉树1.1树的基本概念1.1.1树的定义1.1.2基本术语1.1.3树的性质1.2二叉树的概念...树是一种递归的数据结构,它既作为一种逻辑结构,也是一种分层结构,具有如下特点: 树的根结点没有前驱,除根结
  • 线索二叉树前驱/后继 一、中序线索二叉树 1.【问】如何找到一个指定结点的中序后继,即找到指定结点*p的 中序后继 next ​ ①若p->rtag==1,则 next = p->rchild ​ ②若p->rtag==0,p必有右孩子 ​ ...
  • 基本操作4.1 先序建立二叉树4.2 求树的深度4.3 寻找中序前驱4.3.1 辅助全局变量4.3.2 访问结点4.3.3 遍历4.4 main函数4.5 测试4.5.1 二叉树结构4.5.2 测试结果5.小结 1.头文件及类型定义 #include<stdio.h> #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,536
精华内容 5,414
关键字:

数据结构二叉树的前驱

数据结构 订阅