开发者社区> hjzgg> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

先序,中序,后序线索二叉树

简介:
+关注继续查看

//后序线索,这种方法不容易想到
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

struct TREE{
    int    val;
    TREE *ch[2];
    TREE *thread;//该节点的线索的下一个节点 
    TREE(){}
    TREE(int val){
        this->val = val;
        ch[0] = ch[1] = NULL;
        thread = NULL;
    }
};

void buildT(TREE * &T){
    int x;
    scanf("%d", &x);
    if(x == -1) return ;
    
    T = new TREE(x);
    buildT(T->ch[0]);
    buildT(T->ch[1]);
}


void postThread(TREE *T, TREE *pre){
    if(!T) return;
    postThread(T->ch[0], T);
    postThread(T->ch[1], T);
    if(pre){
        if(pre->ch[0] == T && pre->ch[1])//T是左子树 
            T->thread = pre->ch[1]; //T的下一个节点就是它的兄弟节点 
        else //T是右子树
            T->thread = pre;//T的下一个节点就是它 的父亲节点             
    }
}

void printT_pre(TREE *T){//前序打印 
    if(!T) return ;
    printf("%d ", T->val);
    printT_pre(T->ch[0]);
    printT_pre(T->ch[1]);
}

void printT_Thread(TREE *T){//后序线索打印 
    TREE *root = T;
    bool flag = true;//表明T所在的字数没有访问过 
    while(1){
        while(flag && T->ch[0]) T = T->ch[0];
        printf("%d ", T->val);
        if(T->thread->ch[0] == T || T->thread->ch[1] == T)
            flag = false;//如果 T没有兄弟节点了,就一直沿着它的父节点向上走 
        else flag = true;
        T = T->thread;
        if(T == root){//再次回到最顶端父节点时, 结束! 
           printf("%d ", T->val);           
           break;
        }
    }
}

int main(){
    TREE *T = NULL;
    buildT(T);
    printT_pre(T);
    printf("\n");
    postThread(T, NULL);
    printT_Thread(T);
    printf("\n");
    return 0;
}


下面是基本按照同样的套路实现二叉树的先序,中序,后序的线索


//先序线索
#include<stdio.h> 
#include<stdlib.h>
#define Thread 1
#define Tlink 0
typedef struct tree
{
   int d;
   struct tree* lchild;
   struct tree* rchild;
   int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
   int d;
   scanf("%d", &d);
   if(d!=-1)
     {
         T=(TREE)malloc(sizeof(tree));
         T->d=d;
         T->lchild=T->rchild=NULL;
         T->Ltag=T->Rtag=Tlink;
         build_tree(T->lchild);
         build_tree(T->rchild);
     }
} 

TREE pre;

void preThread_tree(TREE p)
{
   if(p)
     {
        if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
        if(!pre->rchild)
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          }
         pre=p;
         if(p->Ltag==Tlink)//考虑到只有一个结点或两个节点情况, 
            preThread_tree(p->lchild);//如果没有 if语句可能出现死循环 
         if(p->Rtag==Tlink)
            preThread_tree(p->rchild);
     }
}

void print_preThr_tree(TREE T)
{
   TREE p=T;
   while(1)
    { 
       while(p->Ltag==Tlink)
         {
             printf("%d ", p->d);
             p=p->lchild;
         }
       printf("%d ", p->d);
       p=p->rchild;
       if(p==T) break;
       while(p->Rtag==Thread)
         {
             printf("%d ", p->d);
            p=p->rchild;
         }
       
    }
}

void print_tree(TREE T)
{
    if(T)
     {
        printf("%d ", T->d);
        print_tree(T->lchild);
        print_tree(T->rchild);
     }
}


int main()
{
   TREE T=NULL;
   build_tree(T);
   print_tree(T);//递归先序遍历 
   printf("\n");    
   pre=T;
   preThread_tree(T);//非递归先序遍历 
   pre->rchild=T;
   print_preThr_tree(T);
   return 0;
}


//中序线索
#include<stdio.h> 
#include<stdlib.h>
#define Thread 1
#define Tlink 0
typedef struct tree
{
   int d;
   struct tree* lchild;
   struct tree* rchild;
   int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
   int d;
   scanf("%d", &d);
   if(d!=-1)
     {
         T=(TREE)malloc(sizeof(tree));
         T->d=d;
         T->lchild=T->rchild=NULL;
         T->Ltag=T->Rtag=Tlink;
         build_tree(T->lchild);
         build_tree(T->rchild);
     }
} 

TREE pre;

void inorThread_tree(TREE p)
{
   if(p)
     {
         if(p->Ltag==Tlink)//当只有一个结点的时候,要加上这句话 
           inorThread_tree(p->lchild);
        if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
        if(!pre->rchild)
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          }
         pre=p;
         if(p->Rtag==Tlink)
           inorThread_tree(p->rchild);
     }
}

/*
上述代码可以简化如下,pre的初值为NULL就好  
void inorThread_tree(TREE p)
{
   if(p)
     {  
        inorThread_tree(p->lchild);
        if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
        if(pre && !pre->rchild)
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          }
         pre=p;  
         inorThread_tree(p->rchild);
     }
}
*/

void print_tree(TREE T){
    if(T)
     {
        print_tree(T->lchild);
        printf("%d ", T->d);
        print_tree(T->rchild);
     }
}

void print_inorThr_tree(TREE T)
{
   TREE p=T;
   while(1)
    {
       while(p->Ltag==Tlink)
         p=p->lchild;
       printf("%d ", p->d);
       while(p->Rtag==Thread)
         {
             p=p->rchild;
             printf("%d ", p->d);
         }
       p=p->rchild;
       if(p==T)
         break;
    }
}

int main()
{
   TREE T=NULL;
   build_tree(T);
   print_tree(T);//递归中序遍历 
   printf("\n");    
   pre=T;
   inorThread_tree(T);//非递归中序遍历 
   pre->rchild=T;
   pre->Rtag=0;//保证只有一个结点的情况 
   print_inorThr_tree(T);
   return 0;
}

131644465322704.png


//后序线索
#include<stdio.h> 
#include<stdlib.h>
#define Thread 1
#define Tlink 0
typedef struct tree
{
   int d;
   struct tree* lchild;
   struct tree* rchild;
   struct tree* rrchild;
   int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
   int d;
   scanf("%d", &d);
   if(d!=-1)
     {
         T=(TREE)malloc(sizeof(tree));
         T->d=d;
         T->lchild=T->rchild=NULL;
         T->Ltag=T->Rtag=Tlink;
         build_tree(T->lchild);
         build_tree(T->rchild);
     }
} 

TREE pre;

void postThread_tree(TREE p)
{
   if(p)
     {
         if(p->Ltag==Tlink)
            postThread_tree(p->lchild);
         if(p->Rtag==Tlink)
            postThread_tree(p->rchild);
         
         if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
         if(!pre->rchild )
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          } else {
              pre->rrchild=p;
          }
          pre=p;
     }
}

void print_postThr_tree(TREE T)
{
   TREE p=T;
   while(p->Ltag==Tlink)
      p=p->lchild;
   while(1)
    { 
       printf("%d ", p->d);
       if(p==T)
         break; 
       if(p->Rtag == Thread)
            p=p->rchild;
       else 
               p=p->rrchild;
    }
}

void print_tree(TREE T)
{
    if(T)
     {
        print_tree(T->lchild);
        print_tree(T->rchild);
        printf("%d ", T->d);
     }
}


int main()
{
   TREE T=NULL;
   build_tree(T);
   print_tree(T);//递归后序遍历 
   printf("\n");    
   pre=T;
   postThread_tree(T);//非递归后序遍历 
   pre->rchild=T;
   pre->Rtag = Thread; 
   print_postThr_tree(T); 
   return 0;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
二叉树的先序、中序、后序遍历
二叉树的先序、中序、后序遍历
0 0
先序、中序、后序遍历确定唯一树
快速学习先序、中序、后序遍历确定唯一树
0 0
【C++】二叉树的遍历:前序、中序、后序、层序
【C++】二叉树的遍历:前序、中序、后序、层序
0 0
【小白学算法】8.二叉树的遍历,前序、中序和后序
【小白学算法】8.二叉树的遍历,前序、中序和后序
0 0
二叉树中序非递归遍历
二叉树中序非递归遍历 二叉树中序非递归遍历
0 0
二叉树前中序得后序
学妹问了就随手写一下…… 1: /* 2: * 自己写的,以前C++写过,找不到了,学妹问我,就再写了一次 3: * 二叉树前中序得后序 4: */ 5: public class PostOrder { 6: 7: public st...
424 0
根据二叉树的前序和中序求后序 .
周六面试,关于二叉树的题,题目是: 在一棵二叉树总,前序遍历结果为:ABDGCEFH,中序遍历结果为:DGBAECHF,求后序遍历结果。   今天再CSDN上居然发现了原题,记录下来:   在面试的过程中,发现有几家公司都喜欢考这样的一道题,就是在一棵二叉树中,已知这棵二叉树的前序和中序遍历结果,要求写出后序遍历结果。
616 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载