博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
线索二叉树
阅读量:4838 次
发布时间:2019-06-11

本文共 5274 字,大约阅读时间需要 17 分钟。

 

 来源:

/*
******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : biThrTree.cpp
/* 功能描述    : 线索二叉树的表示与实现
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : 输入示例与输出结果
/* 
/* e.g. input  : ABD###CE#F###
/* bi-tree     :
/*                 A
/*                / \
/*               B   C
/*              /   /
/*             D   E
/*                  \
/*                   F
/* 
/* inorder thread traverse: D B A E F C
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
******************************************************************************
*/
#include 
<
stdio.h
>
#include 
<
stdlib.h
>
/*
*****************************************************************************
/* 数据类型和常量定义
/*****************************************************************************
*/
#define
 OK           1
#define
 ERROR        0
#define
 OVERFLOW    -2
typedef 
int
 Status;
typedef 
int
 TElemType;
/*
 二叉树的二叉线索存储表示 
*/
typedef 
enum
 PointerTag { Link, Thread }; 
/*
 Link==0: 指针, Thread==1: 线索 
*/
/*
*****************************************************************************
/* 数据结构定义
/*****************************************************************************
*/
typedef 
struct
 BiThrNode {
    TElemType data;
    
struct
 BiThrNode 
*
lchild, 
*
rchild; 
/*
 左右孩子指针 
*/
    PointerTag LTag, RTag;             
/*
 左右标志 
*/
} BiThrNode, 
*
BiThrTree;
/*
*****************************************************************************
/* 全局变量声明
/*****************************************************************************
*/
static
 BiThrNode 
*
pre 
=
 NULL; 
//
保存线索化过程中的前驱结点
/*
*****************************************************************************
/* 函数原型声明
/*****************************************************************************
*/
void
 InThreading(BiThrTree p);
/*
******************************************************************************
/* <FUNC>
/* 函数名   : Visit
/* 功能     : 打印节点数据
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
******************************************************************************
*/
Status Visit(TElemType e)
{
    printf(
"
%c
"
, e);
    
return
 OK;
}
/*
******************************************************************************
/* <FUNC>
/* 函数名   : InOrderTraverse_Thr
/* 功能     : 中序遍历二叉线索树
/* 参数     : -
/* 返回值   : -
/* 备注     : 中序遍历二叉线索树T的非递归算法, T指向头结点, 头结点的左链lchild指向根结点
/* 作者     : <xxx>
/* </FUNC>
******************************************************************************
*/
Status InOrderTraverse_Thr(BiThrTree T, Status (
*
Visit)(TElemType e)) {
    BiThrNode 
*
=
 T
->
lchild;          
//
p指向根结点
    
while
 (p 
!=
 T) {                   
//
空树或遍历结束时, p==T
        
while
 (p
->
LTag 
==
 Link) p 
=
 p
->
lchild;
        
if
 (
!
Visit(p
->
data)) 
return
 ERROR; 
//
访问其左子树为空的结点
        
while
 (p
->
RTag 
==
 Thread 
&&
 p
->
rchild 
!=
 T) {
            p 
=
 p
->
rchild; Visit(p
->
data);  
//
访问后续结点
        }
        p 
=
 p
->
rchild;
    }
    
return
 OK;
}
/*
******************************************************************************
/* <FUNC>
/* 函数名   : InOrderThreading
/* 功能     : 中序线索化二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 中序遍历二叉树T, 并将其中序线索化, Thrt指向头结点
/* 作者     : <xxx>
/* </FUNC>
******************************************************************************
*/
Status InOrderThreading(BiThrTree 
&
Thrt, BiThrTree T) {
    
if
 (
!
(Thrt 
=
 (BiThrTree)malloc(
sizeof
(BiThrNode)))) exit(OVERFLOW);
    Thrt
->
LTag 
=
 Link; Thrt
->
RTag 
=
 Thread;  
//
建立头结点
    Thrt
->
rchild 
=
 Thrt;                     
//
右指针回指
    
if
 (
!
T) Thrt
->
lchild 
=
 Thrt;             
//
右二叉树为空, 则左指针回指
    
else
 {
        Thrt
->
lchild 
=
 T; pre 
=
 Thrt;
        InThreading(T);                      
//
中序遍历进行中序线索化
        pre
->
rchild 
=
 Thrt;  pre
->
RTag 
=
 Thread; 
//
最后一个结点线索化
        Thrt
->
rchild 
=
 pre;
    }
    
return
 OK;
}
/*
******************************************************************************
/* <FUNC>
/* 函数名   : InThreading
/* 功能     : 中序线索化
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
******************************************************************************
*/
void
 InThreading(BiThrTree p) {
    
if
 (p) {
        InThreading(p
->
lchild);  
//
左子树线索化
        
if
 (
!
p
->
lchild) { p
->
LTag 
=
 Thread; p
->
lchild 
=
 pre; } 
//
前驱线索
        
if
 (
!
pre
->
rchild) { pre
->
RTag 
=
 Thread; pre
->
rchild 
=
 p; } 
//
后继线索
        pre 
=
 p;                   
//
保持pre指向p的前驱
        InThreading(p
->
rchild);  
//
右子树线索化
    }
}
/*
******************************************************************************
/* <FUNC>
/* 函数名   : CreateBiTree
/* 功能     : 创建二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 前序方式创建
/* 作者     : <xxx>
/* </FUNC>
******************************************************************************
*/
Status CreateBiTree(BiThrTree 
&
T)
{
    
char
 ch 
=
 getchar();
    
if
(
'
#
'
 
==
 ch) T 
=
 NULL;
    
else
 {
        
if
(
!
(T 
=
 (BiThrNode 
*
)malloc(
sizeof
(BiThrNode)))) exit(OVERFLOW);
        T
->
data 
=
 ch;             
//
生成根结点
        T
->
LTag 
=
 Link;
        T
->
RTag 
=
 Link;
        CreateBiTree(T
->
lchild);  
//
构造左子树
        CreateBiTree(T
->
rchild);  
//
构造右子树
    }
    
return
 OK;
}
/*
******************************************************************************
/* <FUNC>
/* 函数名   : main
/* 功能     : 测试函数
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
******************************************************************************
*/
void
 main()
{
    BiThrTree ThrT 
=
 NULL;    BiThrTree T 
=
 NULL;
    CreateBiTree(T);
    
//
中序遍历二叉树并线索化
    
if
 (OK 
==
 InOrderThreading(ThrT, T)) printf(
"
InOrder Threading Finished!\n
"
);
    
//
中序遍历线索二叉树
    printf(
"
InOrder Thread Traverse: 
"
);
    InOrderTraverse_Thr(ThrT, Visit);
    printf(
"
\n
"
);
}

转载于:https://www.cnblogs.com/heyonggang/p/3292440.html

你可能感兴趣的文章
陈欧体程序员版And各种版本
查看>>
OC基本语法——NSArray
查看>>
C#:桥接模式
查看>>
ORA-01747: user.table.column, table.column 或列说明无效
查看>>
C++回调函数(callback)的使用
查看>>
HDU 6142【最小割+不会做***】
查看>>
过滤器 & 装饰者模式
查看>>
Springboot整合mybatisPlus实现分页
查看>>
Spring框架(第二天)
查看>>
图片处理
查看>>
poj1406
查看>>
[BZOJ1468]Tree
查看>>
3.RapidIO串行物理层的包传输过程
查看>>
结对编程项目作业4
查看>>
Java基础加强总结(一)——注解(Annotation)
查看>>
嵌入式开发
查看>>
主席树修正
查看>>
DAL层与BLL层的设计原则
查看>>
WCF ria 远程服务器返回:Not Found
查看>>
github 在ubuntu 使用--解决冲突,创建分支
查看>>