`
jaychang
  • 浏览: 734592 次
  • 性别: 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;
   cout<<"输入结点索引值i,和结点值data,以0 #结束\n";
   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==0)
  {
    q=q->lChild;
  }
  return q;
}

//插入结点到线索二叉树
bool InsertNode(BiTreeNode *p,int index,char method)
{
  if(method!='l'&&method!='L'&&method!='r'&&method!='R')
  {
     cout<<"命令有误,插入方式为l,L,r,R.\n";
     return false;
  }
  if(point[index]==NULL)     //不存在该结点
  {   
     cout<<"插入的位置无效\n";
     return false;
  }
  if(method=='l'||method=='L')   //插入为poinit[index]所指向结点的左孩子结点O(∩_∩)O~有点拗口
 {
     if(point[index]->lTag==1)   //插入位置的结点无左孩子结点
    {
      p->lChild=point[index]->lChild;
      point[index]->lChild=p;
      p->lTag=1;p->rTag=1;
      point[index]->lTag=0;
     }
     else        //有左孩子结点,需找到point[index]左子树最右下角的结点
     {
       BiTreeNode *s=point[index]->lChild;
       while(s->rTag==0)s=s->rChild;
       p->lChild=point[index]->lChild;
       point[index]->lChild=p;
       s->rChild=p;
       p->lTag=0;p->rTag=1;
     }
     point[index*2]=p;
  }
  if(method=='r'||method=='R')
  {
      if(point[index]->rTag==1)   //无右孩子结点
     {
        p->rChild=point[index]->rChild;
        point[index]->rChild=p;
        p->lChild=point[index];
        point[index]->rTag=0;
        p->rTag=1;p->lTag=1;
      }
     else        //存在有孩子结点,需找到右子树最左下角的结点
     {
        BiTreeNode *s=point[index]->rChild;
        while(s->lChild==0)s=s->lChild;
        p->rChild=point[index]->rChild;
        point[index]->rChild=p;
        p->lChild=point[index];
        p->rTag=0;p->lTag=1;
        s->lChild=p;
     }
     point[index*2+1]=p;
  }
  return true;
}


int main()
{
  char cmd,data;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<<"\n"<<"输入插入结点的值,及插入的位置,插入的方式(l,r or L,R)\n";
     cin>>data>>index>>cmd;
     BiTreeNode *p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
     p->data=data;
     InsertNode(p,index,cmd);
     cout<<"继续吗Y/y?\n";
     cin>>cmd;
  }while(cmd=='Y'||cmd=='y');
  return 0;
}
 
分享到:
评论

相关推荐

    线索二叉树

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

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

    线索二叉树的插入可以通过找到要插入的位置并将新结点插入到该位置来实现。该过程可以分为以下步骤: 1. 找到要插入的位置。 2. 创建一个新结点,并将其插入到要插入的位置。 3. 将新结点的前驱结点和后继结点的...

    线索二叉树的插入,删除

    在线索二叉树中插入节点时,需要考虑以下几点: 1. 如果新插入的节点是叶子节点,那么它将连接到已存在的节点上,同时更新相关线索。如果它是左孩子,那么它的前驱线索应指向其父节点;如果它是右孩子,那么它的后继...

    C++线索二叉树类实现

    在二叉链表的每个节点中增加两个附加指针,称为线索,分为`ltag`和`rtag`,分别表示左孩子指针是否为前驱线索,右孩子指针是否为后继线索。同时,还需要额外的标志位来区分普通指针和线索。 在C++中,我们可以通过...

    线索二叉树(数据结构课设)

    线索二叉树通过在每个节点中添加额外的线索(指针)来解决这个问题,这些线索指向该节点在某种遍历时的前驱或后继节点。这样,我们就可以使用迭代而非递归的方式进行遍历,提高了算法效率。 线索二叉树中的每个节点...

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

    在中序线索二叉树中,新结点的插入可能会影响其前驱和后继结点的线索。插入新结点时,需要检查新结点的父结点和兄弟结点,以确保线索的正确更新。如果新结点是父结点的左孩子,那么父结点的左线索应指向新结点;如果...

    二叉树的线索化(中序线索二叉树)

    在中序线索二叉树中,我们可以快速地从前一个节点找到后一个节点,而无需通过父节点进行跳转。这一过程涉及到对二叉树节点的修改,添加两个额外的指针,称为“前向线索”(in-order predecessor pointer)和“后向...

    c++线索二叉树源代码

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

    数据结构课程设计 线索二叉树

    - **插入**:在已有线索二叉树中插入新的节点,同时更新线索信息,保持线索的正确性。 - **删除**:从线索二叉树中删除指定节点,同样需要更新线索信息。 - **线索化**:将普通二叉树转换为线索二叉树,即在遍历...

    线索二叉树的应用.doc

    例如,在插入结点时,我们需要找到插入结点的前驱和后继结点,然后将其连接起来。在删除结点时,我们需要找到删除结点的前驱和后继结点,然后将其连接起来。 线索二叉树是一种特殊的二叉树,它的结构和性质使得我们...

    数据结构线索二叉树严蔚敏

    线索二叉树通过在二叉树的每个节点中添加额外的线索(thread)指向其前驱或后继节点,使得非递归的遍历方式成为可能,从而提高了查找效率。 在构建线索二叉树时,我们需要在二叉树的叶子节点和非叶子节点上分别处理...

    数据结构 线索二叉树

    线索二叉树是一种特殊的二叉树,它是在普通的二叉链表基础上进行改造,以便在二叉树中方便地进行前序、中序和后序遍历。在标准的二叉链表中,每个节点仅包含指向左孩子和右孩子的指针,但没有直接指向其前驱和后继...

    数据结构课程设计线索二叉树

    在C++或Java等面向对象的语言中,我们可以定义一个`Node`类表示线索二叉树的节点,包含数据、左右孩子指针和前驱后继线索。接着实现`BinaryThreadedTree`类,提供插入、删除、遍历等相关操作。对于每个操作,都需要...

    线索二叉树实验报告.docx

    定义了结构体 `BiThrNode` 表示线索二叉树的节点,包括数据元素 `data`,以及指向左子节点 `lchild`、右子节点 `rchild` 的指针,还有两个枚举类型 `PointerTag` 表示指针类型,`Link` 表示普通指针,`Thread` 表示...

    线索二叉树详解(C语言版).rar

    线索二叉树是二叉树的一种优化形式,通过在节点中添加线索来改善遍历效率。在C语言中,我们可以利用结构体和指针来构建和操作线索二叉树。虽然实现过程比普通二叉树更复杂,但线索二叉树在处理大规模数据时能带来...

    线索二叉树的建立与实现

    在`ThreadTree`这个文件中,可能包含了实现线索二叉树的类定义、节点结构以及相关的插入、删除、遍历等方法。具体实现细节需要查看源代码才能得知。 总结来说,线索二叉树通过引入线索,优化了二叉搜索树的遍历性能...

    遍历和线索二叉树c语言版

    总之,线索二叉树是一种增强二叉树遍历能力的数据结构,通过在节点中添加线索指针,使得非递归遍历成为可能,尤其在处理反向遍历时更为高效。C语言作为一种底层语言,非常适合实现这样的数据结构,通过结构体和指针...

    线索二叉树用c#实现

    在二叉链表的每个节点中,除了原有的左子节点(left)和右子节点(right)指针外,我们还会添加两个新的字段:前驱线索(left_thread)和后继线索(right_thread)。当某个节点没有左子节点时,它的left_thread将...

Global site tag (gtag.js) - Google Analytics