`
jaychang
  • 浏览: 734600 次
  • 性别: Icon_minigender_1
  • 来自: 嘉兴
社区版块
存档分类
最新评论

二叉树中序线索化及查找某一结点的前驱,后继结点

阅读更多
#include<iostream>

using namespace std;

#define MAX 1500

//二叉树定义
typedef struct BiTreeNode{
  char data;
  BiTreeNode *lChild;
  BiTreeNode *rChild;
  int lTag,rTag;
}BiTreeNode;

//全局变量
BiTreeNode *pre =NULL;
BiTreeNode *point[MAX+1]; //构建二叉树时辅助,用于定位子节点

//构建二叉树
BiTreeNode *CreateBiTree()
{
  BiTreeNode *root=(BiTreeNode *)malloc(sizeof(BiTreeNode));
  int i,j;char data;
  cin>>i>>data;
  while(i!=0&&data!='#')
  {
    BiTreeNode *newNode=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    newNode->data=data;
    newNode->lTag=0;newNode->rTag=0;
    newNode->lChild=NULL;newNode->rChild=NULL;
    point[i]=newNode; 
    if(i==1)    //为二叉树根节点
    {
      root=point[1];
    }
    else
    {
      j=i/2;
     if(i%2==0)   //为左孩子结点
     {
        point[j]->lChild=newNode;
      }
      else
     {
        point[j]->rChild=newNode;
      }
     }
     cin>>i>>data;
  }
  return root;
}

//中序线索化二叉树,pre初始化为NULL
void Inthread(BiTreeNode *root)
{
  if(root!=NULL)
  {  
     Inthread(root->lChild);
     if(root->lChild==NULL)
     {
      root->lTag=1;root->lChild=pre;
     }
     if(pre!=NULL&&pre->rChild==NULL)
     {
      pre->rTag=1;pre->rChild=root;
     }
     pre=root;
     Inthread(root->rChild);
  }
}


//查找结点p的前驱结点
BiTreeNode *InPre(BiTreeNode *p)
{
  if(p->lTag==1)return p->lChild;
  BiTreeNode *q=p->lChild;
  if(q==NULL){
     cout<<"无前驱结点\n";
     return NULL;
  }
  while(q->rTag!=1)
  {
    q=q->rChild;
  }
  return q;
}

//查找结点p的后继结点
BiTreeNode *InSub(BiTreeNode *p)
{
  if(p->rTag==1)return p->rChild;
  BiTreeNode *q=p->rChild;
  if(q==NULL){
     cout<<"无后继结点\n";
     return NULL;
  }
  while(q->lTag!=1)
  {
    q=q->lChild;
  }
  return q;
}


int main()
{
  char cmd;int index;
  do{
     BiTreeNode *root=CreateBiTree();
     Inthread(root);
     cout<<"输入您要查找的结点,序号index\n";
     cin>>index;
     BiTreeNode *nodePre=InPre(point[index]);
     BiTreeNode *nodeSub=InSub(point[index]);
     if(nodePre!=NULL)
        cout<<"结点"<<index<<"的前驱结点的值为"<<nodePre->data<<"\n";
     if(nodeSub!=NULL)
       cout<<"结点"<<index<<"的后继结点的值为"<<nodeSub->data<<"\n";
     cout<<"继续吗Y/y?\n";
     cin>>cmd;
  }while(cmd=='Y'||cmd=='y');
  return 0;
}
 
分享到:
评论

相关推荐

    中序线索化二叉树指定结点的前驱

    中序线索化是将非线索二叉树转化为线索二叉树的过程,目的是为了方便在不使用栈的情况下进行中序遍历,特别是在查找某个结点的前驱和后继时。本程序专注于中序线索化二叉树并确定指定结点的前驱。 中序线索化的基本...

    寻找中序线索化二叉树指定结点的后继.zip

    中序线索化二叉树是一种特殊形式的二叉搜索树,它通过添加线索来帮助在树中进行快速的中序遍历,特别是找到某个节点的前驱和后继节点。这个主题“寻找中序线索化二叉树指定结点的后继”将深入探讨如何在已线索化的...

    寻找中序线索化二叉树指定结点的前驱.zip

    在压缩包文件"寻找中序线索化二叉树指定结点的前驱.swf"中,很可能是包含了一个交互式的演示或教学资源,用来直观展示如何在中序线索化二叉树中找到特定节点的前驱节点。通过观看这个SWF文件,学习者可以更好地理解...

    中序线索化二叉树的非递归算法.doc

    2. 线索化二叉树:线索化二叉树是一种特殊的二叉树结构,其中每个结点的左右子树指针被修改为指向前驱和后继结点,以便于快速遍历二叉树。 3. 栈的应用:在该算法中,我们使用栈来存储左子树的结点,以便在遍历过程...

    数据结构-3期(KC002) 中序线索二叉树中查找后继结点.docx

    本文将深入探讨一种特定的数据结构——中序线索二叉树,并重点解析如何在其中寻找一个结点的后继结点。 首先,我们需要理解二叉树的基本概念。二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,通常称为...

    线索二叉树

    通过前序序列创建线索二叉树 1:中序遍历 2:查找节点前驱后继 3:插入节点 4:删除节点 0:退出

    lab09 11.doc

    题目要求:由先序遍历序列建立二叉树的二叉链表,中序线索化二叉树并找出结点的前驱和后继。 步骤一:新建工程,新建一个头文件,命名为 thread.h,一个源文件命名为thread.cpp 步骤二: 在thread.h中编辑代码,...

    数据结构5.10二叉树线索链表存储结构

    在二叉树的线索化过程中,这些空指针被用于存放前驱和后继结点的信息,从而提高了二叉树的遍历效率。 #### 三、结点结构 为了实现线索链表,每个结点除了原有的数据域和左右子树指针外,还需要增加两个标志位 `...

    中序线索化

    - **线索二叉树**:对一个二叉树进行线索化处理后得到的一种特殊形式的二叉树,其中一些原本为NULL的指针被用来指向其“前驱”或“后继”节点。 - **中序线索化**:按照中序遍历的顺序对二叉树进行线索化处理。 ###...

    二叉树遍历序列.cpp

    二叉树遍历序列.cpp

    线索二叉树的建立、删除、插入、恢复线索

    线索二叉树是一种特殊的二叉树,它的每个结点都带有指向其前驱和后继结点的指针,这些指针称为线索。线索二叉树可以分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。在本文中,我们将讨论中序线索二叉树的...

    线索二叉树的应用.doc

    中序线索二叉树是一种特殊的二叉树,它的结点结构中除了存储数据外,还存储了指向其前驱和后继结点的指针。这种结构可以使得我们在遍历二叉树时,可以快速地找到某个结点的前驱和后继结点,从而提高了遍历效率。 ...

    数据结构和算法Flash动画演示

    单链表结点的删除,单链表结点的插入,图的深度优先遍历,基数排序,堆排序,头插法建单链表,寻找中序线索化二叉树指定结点的前驱,寻找中序线索化二叉树指定结点的后继,尾插法建表,希儿排序,开放定址法建立散...

    数据结构二叉树的线索本.ppt

    4. **查找后继结点**:在中序线索树中,给定值为x的结点,若无右子树,后继为后继线索所指结点;若有右子树,后继为其右子树中最左下的结点。 5. **查找直接前驱**:在后序线索树中,给定结点p,其直接前驱q是所有以...

    第7章树和二叉树第9讲- 线索二叉树.pptx

    线索二叉树的概念是通过遍历二叉树的结果是一个结点的线性序列,然后修改空链域改为存放指向结点的前驱和后继结点的地址。这样,线索二叉树可以提高遍历二叉树的效率。 线索二叉树的存储结构是在结点的存储结构上...

    线索化二叉树C实现代码

    在构建线索化二叉树的过程中,根据遍历顺序,利用这两个线性表可以快速找到前驱和后继结点。这种策略需要额外的存储空间,但在某些情况下,如当二叉树很大且不便于内存映射时,可能会更实用。 **C语言实现** 下面是...

    数据结构线索树与树和森林PPT学习教案.pptx

    数据结构中的线索树是一种特殊的二叉树结构,用于在非递归方式下实现二叉树的遍历,尤其是便于查找结点的前驱和后继。线索二叉树的概念源于遍历二叉树时得到的结点线性序列,通过在结点中添加额外的标志域来指示结点...

    c++线索二叉树源代码

    在普通的二叉查找树中,我们通常只能通过指针找到左右子节点,但在线索二叉树中,我们可以从前向后(前驱线索)和从后向前(后继线索)遍历节点,使得在非递归情况下也能进行中序、前序和后序遍历。 线索二叉树的...

    线索二叉树运算的课程设计

    线索二叉树是一种特殊的二叉树数据结构,它通过在二叉链表的空指针域中存储指向结点在特定遍历顺序下的前驱和后继结点的指针,从而方便快速的遍历。在本课程设计中,重点在于实现中序线索二叉树的建立、插入、删除...

Global site tag (gtag.js) - Google Analytics