一棵线索二叉树

[各种面试题] 将一棵普通二叉树转换为一棵线索二叉树

千次阅读 2013-09-19 20:55:13

将一棵普通二叉树转换为一棵线索二叉树（查看定义）。详细说明：树结点除了包含left, right指针外，还包含isLeftThread和isRightThread，初始时isLeftThread和isRightThread都为false。对于left为null的结点，请...


将一棵普通二叉树转换为一棵线索二叉树（查看定义）。

详细说明：树结点除了包含left, right指针外，还包含isLeftThread和isRightThread，初始时isLeftThread和isRightThread都为false。对于left为null的结点，请将left设置为中序遍历该结点的前驱结点，并将isLeftThread设置为true。对于right为null的结点，请将right设置为中序遍历该结点的后继结点，并将isRightThread设置为true。

提示：请尝试使用非递归算法。

第一反应还是中序遍历然后递归，先忽略提示使用非递归吧。

又是对着错的测试用例然后改了下代码才A过。


/*树结点的定义(请不要在代码中定义该结构)
struct TreeNode {
  TreeNode *left, *right;
  bool isLeftThread, isRightThread;
}*/
void inorder(TreeNode* root,TreeNode*& pre,int& preNeedSet);
void convertToThreadedTree(TreeNode *root) {
	if ( !root ) 
		return;
	TreeNode* pre=NULL;
	int preNeedSet=0;
	inorder(root,pre,preNeedSet);
	if (pre&&preNeedSet )
		pre->isRightThread=true;
}
void inorder(TreeNode* root,TreeNode*& pre,int& preNeedSet)
{
	if (!root )
		return;
	inorder(root->left,pre,preNeedSet);
	if ( !root->left )
	{
		root->isLeftThread=true;
		if ( pre )
		{
			root->left = pre;
			
		}
	}
    if ( pre&&preNeedSet )
	{
		pre->isRightThread=true;
		pre->right=root;
	}
	pre=root;
	if (!root->right )
		preNeedSet=1;
    else
        preNeedSet=0;
	inorder(root->right,pre,preNeedSet);
}

收起

展开全文

图解线索二叉树与双向线索二叉树（附源码）

千次阅读 2020-06-09 20:05:21

文章目录线索二叉树的概念线索二叉树的结构二叉树的线索化使用线索二叉树进行遍历双向线索二叉树的概念双向线索二叉树的实现过程双向线索二叉树的遍历 线索二叉树的概念 ...每一棵二叉树上，很多结点都含有未使用的


工科生一枚，热衷于底层技术开发，有强烈的好奇心，感兴趣内容包括单片机，嵌入式Linux，Uboot等，欢迎学习交流！

爱好跑步，打篮球，睡觉。

欢迎加我QQ1500836631（备注CSDN），一起学习交流问题，分享各种学习资料，电子书籍，学习视频等。

文章目录
线索二叉树的概念
线索二叉树的结构
二叉树的线索化
线索二叉树进行遍历
双向线索二叉树的概念
双向线索二叉树的实现过程
双向线索二叉树的遍历
总结

线索二叉树的概念
  当我们对普通的二叉树进行遍历时需要使用栈结构做重复性的操作。线索二叉树不需要如此，在遍历的同时，使用二叉树中空闲的内存空间记录某些结点的前趋和后继元素的位置（不是全部）。这样在算法后期需要遍历二叉树时，就可以利用保存的结点信息，提高了遍历的效率。使用这种方法构建的二叉树，即为“线索二叉树”。
线索二叉树的结构
  每一棵二叉树上，很多结点都含有未使用的指向NULL 的指针域。除了度为2 的结点，度为1 的结点，有一个空的指针域；叶子结点两个指针域都为NULL。
  线索二叉树实际上就是使用这些空指针域来存储结点之间前趋和后继关系的一种特殊的二叉树。线索二叉树中，如果结点有左子树，则lchild 指针域指向左孩子，否则lchild 指针域指向该结点的直接前趋；同样，如果结点有右子树，则rchild 指针域指向右孩子，否则rchild 指针域指向该结点的直接后继。



  LTag 和RTag 为标志域。实际上就是两个布尔类型的变量：

   LTag 值为0 时，表示lchild 指针域指向的是该结点的左孩子；为1 时，表示指向的是该结点的直接前趋结点；

   RTag 值为0 时，表示rchild 指针域指向的是该结点的右孩子；为1 时，表示指向的是该结点的直接后继结点。

  结点结构代码实现：
#define TElemType int//宏定义，结点中数据域的类型
//枚举，Link 为0，Thread 为1
typedef enum PointerTag{
Link,
Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode{
TElemType data;//数据域
struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
PointerTag Ltag,Rtag;//标志域，枚举类型
}BiThrNode,*BiThrTree;

二叉树的线索化
  将二叉树转化为线索二叉树，实质上是在遍历二叉树的过程中，将二叉链表中的空指针改为指向直接前趋或者直接后继的线索。

  线索化的过程即为在遍历的过程中修改空指针的过程。在遍历过程中，如果当前结点没有左孩子，需要将该结点的lchild 指针指向遍历过程中的前一个结点，所以在遍历过程中，设置一个指针（名为pre ），时刻指向当前访问结点的前一个结点。

  代码实现（拿中序遍历为例）：
/**
 * @Description: 中序对二叉树进行线索化
 * @Param: BiThrTree p 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InThreading(BiThrTree p)
{
    //如果当前结点存在
    if (p)
    {
        //递归当前结点的左子树，进行线索化
        InThreading(p->lchild); 
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点pre
        if (!p->lchild)
        {
             //前驱线索
            p->Ltag = Thread;
             //左孩子指针指向前驱
            p->lchild = pre; 
        }
        //如果pre 没有右孩子，右标志位设为1，右指针域指向当前结点。
        if (pre && !pre->rchild)
        {
            //后继线索
            pre->Rtag = Thread;
            //前驱右孩子指针指向后继(当前结点p)
            pre->rchild = p;
        }
        pre = p;                //pre 指向当前结点
        InThreading(p->rchild); //递归右子树进行线索化
    }
}


  注意：中序对二叉树进行线索化的过程中，在两个递归函数中间的运行程序，和之前介绍的中序遍历二叉树的输出函数的作用是相同的。将中间函数移动到两个递归函数之前，就变成了前序对二叉树进行线索化的过程；后序线索化同样如此。

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/qq_16933601/article/details/106478780

线索二叉树进行遍历
  下图中是一个按照中序遍历建立的线索二叉树。其中，实线表示指针，指向的是左孩子或者右孩子。虚线表示线索，指向的是该结点的直接前趋或者直接后继。



  使用线索二叉树时，会经常遇到一个问题，如上图中，结点8的直接后继直接通过指针域获得，为结点5；而由于结点5的度为2 ，无法利用指针域指向后继结点，整个链表断掉了。当在遍历过程，遇到这种问题是解决的办法就是：寻找先序、中序、后序遍历的规律，找到下一个结点。

  在先序遍历过程中，如果结点因为有右孩子导致无法找到其后继结点，如果结点有左孩子，则后继结点是其左孩子；否则，就一定是右孩子。拿上图举例，结点2的后继结点是其左孩子结点4 ，如果结点4不存在的话，就是结点5 。

  在中序遍历过程中，结点的后继是遍历其右子树时访问的第一个结点，也就是右子树中位于最左下的结点。例如上图中结点5，后继结点为结点11，是其右子树中位于最左边的结点。反之，结点的前趋是左子树最后访问的那个结点。

  后序遍历中找后继结点需要分为3 种情况：

  1. 如果该结点是二叉树的根，后继结点为空；

  2. 如果该结点是父结点的右孩子（或者是左孩子，但是父结点没有右孩子），后继结点是父结点；

  3. 如果该结点是父结点的左孩子，且父结点有右子树，后继结点为父结点的右子树在后序遍历列出的第一个结点。

  使用后序遍历建立的线索二叉树，在真正使用过程中遇到链表的断点时，需要访问父结点，所以在初步建立二叉树时，宜采用三叉链表做存储结构。

遍历线索二叉树非递归代码实现：
/**
 * @Description: 中序遍历线索二叉树 非递归
 * @Param: BiThrTree p 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThraverse_Thr(BiThrTree p)
{
    while (p)
    {
        //一直找左孩子，最后一个为中序序列中排第一的
        while (p->Ltag == Link)
        {
            p = p->lchild;
        }
         //此时p指向中序遍历序列的第一个结点（最左下的结点）  
         
        //打印（访问）其左子树为空的结点  
        printf("%c ", p->data); 
        //当结点右标志位为1 时，直接找到其后继结点
        while (p->Rtag == Thread && p->rchild != NULL)
        {
            p = p->rchild;
            //访问后继结点 
            printf("%c ", p->data);
        }
        
        //当p所指结点的rchild指向的是孩子结点而不是线索时，p的后继应该是其右子树的最左下的结点，即遍历其右子树时访问的第一个节点  
        p = p->rchild;
    }
}

完整代码如下：
/*
 * @Description: 线索二叉树
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-05-20 16:31:33
 * @LastEditors: Carlos
 * @LastEditTime: 2020-06-01 20:19:22
 */
#include <stdio.h>
#include <stdlib.h>
#define TElemType char //宏定义，结点中数据域的类型
//枚举，Link 为0，Thread 为1
typedef enum
{
    Link,
    Thread
} PointerTag;
//结点结构构造
typedef struct BiThrNode
{
    //数据域
    TElemType data;                    
    //左孩子，右孩子指针域
    struct BiThrNode *lchild, *rchild; 
    //标志域，枚举类型
    PointerTag Ltag, Rtag;             
} BiThrNode, *BiThrTree;
BiThrTree pre = NULL;
/**
 * @Description: 初始化二叉树
 * @Param: BiTree *T 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void CreateBiTree(BiThrTree *T){
    *T=(BiThrNode*)malloc(sizeof(BiThrNode));
    (*T)->data=1;
    (*T)->lchild=(BiThrNode*)malloc(sizeof(BiThrNode));
    (*T)->rchild=(BiThrNode*)malloc(sizeof(BiThrNode));
   
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiThrNode*)malloc(sizeof(BiThrNode));
    (*T)->lchild->rchild=(BiThrNode*)malloc(sizeof(BiThrNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
   
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiThrNode*)malloc(sizeof(BiThrNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
   
    (*T)->rchild->rchild=(BiThrNode*)malloc(sizeof(BiThrNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
   
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}

/**
 * @Description: 采用前序初始化二叉树  中序和后序只需改变赋值语句的位置即可
 * @Param: BiThrTree *tree 二叉树的结构体指针数组
 * @Return: 无
 * @Author: Carlos
 */
void CreateTree(BiThrTree *tree)
{
    char data;
    scanf("%c", &data);
    if (data != '#')
    {
        if (!((*tree) = (BiThrNode *)malloc(sizeof(BiThrNode))))
        {
            printf("申请结点空间失败");
            return;
        }
        else
        {
            //采用前序遍历方式初始化二叉树
            (*tree)->data = data;          
            //初始化左子树 
            CreateTree(&((*tree)->lchild));
            //初始化右子树 
            CreateTree(&((*tree)->rchild)); 
        }
    }
    else
    {
        *tree = NULL;
    }
}

/**
 * @Description: 中序对二叉树进行线索化
 * @Param: BiThrTree p 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InThreading(BiThrTree p)
{
    //如果当前结点存在
    if (p)
    {
        //递归当前结点的左子树，进行线索化
        InThreading(p->lchild); 
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点pre
        if (!p->lchild)
        {
             //前驱线索
            p->Ltag = Thread;
             //左孩子指针指向前驱
            p->lchild = pre; 
        }
        //如果pre 没有右孩子，右标志位设为1，右指针域指向当前结点。
        if (pre && !pre->rchild)
        {
            //后继线索
            pre->Rtag = Thread;
            //前驱右孩子指针指向后继(当前结点p)
            pre->rchild = p;
        }
        pre = p;                //pre 指向当前结点
        InThreading(p->rchild); //递归右子树进行线索化
    }
}

/**
 * @Description: 中序遍历线索二叉树 非递归
 * @Param: BiThrTree p 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThraverse_Thr(BiThrTree p)
{
    while (p)
    {
        //一直找左孩子，最后一个为中序序列中排第一的
        while (p->Ltag == Link)
        {
            p = p->lchild;
        }
         //此时p指向中序遍历序列的第一个结点（最左下的结点）  
         
        //打印（访问）其左子树为空的结点  
        printf("%c ", p->data); 
        //当结点右标志位为1 时，直接找到其后继结点
        while (p->Rtag == Thread && p->rchild != NULL)
        {
            p = p->rchild;
            //访问后继结点 
            printf("%c ", p->data);
        }
        
        //当p所指结点的rchild指向的是孩子结点而不是线索时，p的后继应该是其右子树的最左下的结点，即遍历其右子树时访问的第一个节点  
        p = p->rchild;
    }
}
int main()
{
    BiThrTree t;
    printf("输入前序二叉树:\n");
    CreateTree(&t);
    // CreateBiTree(&t);
    InThreading(t);
    printf("输出中序序列:\n");
    InOrderThraverse_Thr(t);
    return 0;
}


双向线索二叉树的概念
  在遍历使用中序序列创建的线索二叉树时，对于其中的每个结点，即使没有线索的帮助

下，也可以通过中序遍历的规律找到直接前趋和直接后继结点的位置。也就是说，建立的线索二叉链表可以从两个方向对结点进行中序遍历。线索二叉链表可以从第一个结点往后逐个遍历。但是起初由于没有记录中序序列中最后一个结点的位置，所以不能实现从最后一个结点往前逐个遍历。双向线索链表的作用就是可以让线索二叉树从两个方向实现遍历。
双向线索二叉树的实现过程
  在线索二叉树的基础上，额外添加一个结点。此结点的作用类似于链表中的头指针，数据域不起作用，只利用两个指针域（由于都是指针，标志域都为0 ）。左指针域指向二叉树的树根，确保可以正方向对二叉树进行遍历；同时，右指针指向线索二叉树形成的线性序列中的最后一个结点。

  这样，二叉树中的线索链表就变成了双向线索链表，既可以从第一个结点通过不断地找后继结点进行遍历，也可以从最后一个结点通过不断找前趋结点进行遍历。



代码实现
/**
 * @Description: 建立双向线索链表
 * @Param: BiThrTree *h 结构体指针数组 BiThrTree t 结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThread_Head(BiThrTree *h, BiThrTree t)
{
    //初始化头结点
    (*h) = (BiThrTree)malloc(sizeof(BiThrNode));
    if ((*h) == NULL)
    {
        printf("申请内存失败");
        return;
    }
    (*h)->rchild = *h;
    (*h)->Rtag = Link;
    //如果树本身是空树
    if (!t)
    {
        (*h)->lchild = *h;
        (*h)->Ltag = Link;
    }
    else
    {
        //pre 指向头结点
        pre = *h;        
        //头结点左孩子设为树根结点 
        (*h)->lchild = t; 
        (*h)->Ltag = Link;
        //线索化二叉树，pre 结点作为全局变量，线索化结束后，pre 结点指向中序序列中最后一个结点
        InThreading(t); 
        //链接最后一个节点（最右下角G节点）和头结点
        pre->rchild = *h;
        pre->Rtag = Thread;
        //将头结点的右指针指向中序序列最后一个节点
        (*h)->rchild = pre;
    }
}

双向线索二叉树的遍历
  双向线索二叉树遍历时，如果正向遍历，就从树的根结点开始。整个遍历过程结束的标志是：当从头结点出发，遍历回头结点时，表示遍历结束。
/**
 * @Description: 中序正向遍历双向线索二叉树
 * @Param: BiThrTree h 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThraverse_Thr(BiThrTree h)
{
    BiThrTree p;
    //p 指向根结点
    p = h->lchild; 
    while (p != h)
    {
        //当ltag = 0 时循环到中序序列的第一个结点。
        while (p->Ltag == Link) 
        {
            p = p->lchild;
        }
        //显示结点数据，可以更改为其他对结点的操作
        printf("%c ", p->data); 
        
        //如果当前节点经过了线索化，直接利用该节点访问下一节点
        while (p->Rtag == Thread && p->rchild != h)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        //如果没有线索化或者跳出循环，说明其含有右子树。p 进入其右子树
        p = p->rchild; 
    }
}

  逆向遍历线索二叉树的过程即从头结点的右指针指向的结点出发，逐个寻找直接前趋结点，结束标志同正向遍历一样：
/**
 * @Description: 中序逆方向遍历线索二叉树 和正向的区别在于 p = p->rchild 。逆向遍历我们要一直访问到右子树的最后一个。
 * @Param: BiThrTree h 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThraverse_Thr(BiThrTree h)
{
    BiThrTree p;
    p = h->rchild;
    while (p != h)
    {
        while (p->Rtag == Link)
        {
            p = p->rchild;
        }
        printf("%c", p->data);
        //如果lchild 为线索，直接使用，输出
        while (p->Ltag == Thread && p->lchild != h)
        {
            p = p->lchild;
            printf("%c", p->data);
        }
        p = p->lchild;
    }
}

  完整代码如下
/*
 * @Description: 双向线索二叉树的遍历
 * @Version: V1.0
 * @Autor: Carlos
 * @Date: 2020-06-01 20:46:38
 * @LastEditors: Carlos
 * @LastEditTime: 2020-06-01 21:17:23
 */
#include <stdio.h>
#include <stdlib.h>
//宏定义，结点中数据域的类型
#define TElemType char 
//枚举，Link 为0，Thread 为1
typedef enum
{
    Link,
    Thread
} PointerTag;
//结点结构构造
typedef struct BiThrNode
{
    //数据域
    TElemType data;    
    //左孩子，右孩子指针域                
    struct BiThrNode *lchild, *rchild; 
    //标志域，枚举类型
    PointerTag Ltag, Rtag;             
} BiThrNode, *BiThrTree;
BiThrTree pre = NULL;
/**
 * @Description: 采用前序初始化二叉树  中序和后序只需改变赋值语句的位置即可
 * @Param: BiThrTree *tree 二叉树的结构体指针数组
 * @Return: 无
 * @Author: Carlos
 */
void CreateTree(BiThrTree *tree)
{
    char data;
    scanf("%c", &data);
    if (data != '#')
    {
        if (!((*tree) = (BiThrNode *)malloc(sizeof(BiThrNode))))
        {
            printf("申请结点空间失败");
            return;
        }
        else
        {
            //采用前序遍历方式初始化二叉树
            (*tree)->data = data;           
            //初始化左子树
            CreateTree(&((*tree)->lchild)); 
            //初始化右子树
            CreateTree(&((*tree)->rchild)); 
        }
    }
    else
    {
        *tree = NULL;
    }
}
/**
 * @Description: 中序对二叉树进行线索化 
 * @Param: BiThrTree p 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InThreading(BiThrTree p)
{
    //如果当前结点存在
    if (p)
    {
        //递归当前结点的左子树，进行线索化
        InThreading(p->lchild); 
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点pre
        if (!p->lchild)
        {
            p->Ltag = Thread;
            //pre为头结点，链接中序遍历的第一个节点（最左边的结点）与头结点
            p->lchild = pre;
        }
        //如果pre 没有右孩子，右标志位设为1，右指针域指向当前结点。
        if (pre && !pre->rchild)
        {
            pre->Rtag = Thread;
            pre->rchild = p;
        }
        //pre 指向当前结点
        pre = p;             
        //递归右子树进行线索化   
        InThreading(p->rchild); 
    }
}

/**
 * @Description: 建立双向线索链表
 * @Param: BiThrTree *h 结构体指针数组 BiThrTree t 结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThread_Head(BiThrTree *h, BiThrTree t)
{
    //初始化头结点
    (*h) = (BiThrTree)malloc(sizeof(BiThrNode));
    if ((*h) == NULL)
    {
        printf("申请内存失败");
        return;
    }
    (*h)->rchild = *h;
    (*h)->Rtag = Link;
    //如果树本身是空树
    if (!t)
    {
        (*h)->lchild = *h;
        (*h)->Ltag = Link;
    }
    else
    {
        //pre 指向头结点
        pre = *h;        
        //头结点左孩子设为树根结点 
        (*h)->lchild = t; 
        (*h)->Ltag = Link;
        //线索化二叉树，pre 结点作为全局变量，线索化结束后，pre 结点指向中序序列中最后一个结点
        InThreading(t); 
        //链接最后一个节点（最右边下角）和头结点
        pre->rchild = *h;
        pre->Rtag = Thread;
        (*h)->rchild = pre;
    }
}

/**
 * @Description: 中序正向遍历双向线索二叉树
 * @Param: BiThrTree h 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThraverse_Thr(BiThrTree h)
{
    BiThrTree p;
    //p 指向根结点
    p = h->lchild; 
    while (p != h)
    {
        //当ltag = 0 时循环到中序序列的第一个结点。
        while (p->Ltag == Link) 
        {
            p = p->lchild;
        }
        //显示结点数据，可以更改为其他对结点的操作
        printf("%c ", p->data); 
        
        //如果当前节点经过了线索化，直接利用该节点访问下一节点
        while (p->Rtag == Thread && p->rchild != h)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        //如果没有线索化或者跳出循环，说明其含有右子树。p 进入其右子树
        p = p->rchild; 
    }
}
/**
 * @Description: 中序逆方向遍历线索二叉树 和正向的区别在于 p = p->rchild 。逆向遍历我们要一直访问到右子树的最后一个。
 * @Param: BiThrTree h 二叉树的结构体指针
 * @Return: 无
 * @Author: Carlos
 */
void InOrderThraverse_Thr(BiThrTree h)
{
    BiThrTree p;
    p = h->rchild;
    while (p != h)
    {
        while (p->Rtag == Link)
        {
            p = p->rchild;
        }
        printf("%c", p->data);
        //如果lchild 为线索，直接使用，输出
        while (p->Ltag == Thread && p->lchild != h)
        {
            p = p->lchild;
            printf("%c", p->data);
        }
        p = p->lchild;
    }
}
int main()
{
    BiThrTree t;
    BiThrTree h;
    printf("输入前序二叉树:\n");
    CreateTree(&t);
    InOrderThread_Head(&h, t);
    printf("输出中序序列:\n");
    InOrderThraverse_Thr(h);
    return 0;
}

总结
  二叉树的线索化就是充分利用了节点的空指针域。所有节点线索化的过程也就是当前节点指针和上一结点指针进行链接的过程，不断递归所有节点。线索化二叉树的访问，以中序遍历为例，首先需要访问到中序遍历的第一个节点，若当前节点进行了线索化，可以直接利用该节点进行下一节点的访问。否则，说明当前节点含有右子树，则进入右子树进行访问。双向线索二叉树的建立，其实就将头结点的左指针和树的根节点链接，头结点的右指针和中序遍历的最后一个节点的链接。这样我们就可以进行双向访问了。当从头结点出发，遍历回头结点时，表示遍历结束。

收起

展开全文

C语言数据结构与算法

线索二叉树

2019-10-17 09:19:48

线索二叉树的思想来源于二叉树的存储结构中，存在一些空的指针域，因此是否能够将这些空间利用起来，存储一些关于节点间先后顺序的信息，由此产生了...线索二叉树的优势是一旦对一棵二叉树建立了相应的线索结构，当...

线索二叉树的思想来源于二叉树的存储结构中，存在一些空的指针域，因此是否能够将这些空间利用起来，存储一些关于节点间先后顺序的信息，由此产生了线索二叉树。线索二叉树中，线索反映前驱、后继的关系，而指针则体现左右子树。
以二叉链表为例，线索二叉树存储结构上的特点是添加标识符，表明左右指针域究竟存的是指向前驱和后继的线索，还是指向左右子树的指针；
线索二叉树的优势是一旦对一棵二叉树建立了相应的线索结构，当以后使用特定的方式遍历这课树时，可以避免递归方式和非递归方式（利用栈）带来的空间开销。
构建和遍历线索二叉树的思路如下：
首先构造一棵二叉树（构造二叉树可以使用任意顺序：先序、中序、后续均可）；

按照一定的顺序线索化这棵二叉树

然后按照相同的顺序遍历该二叉树，就可以利用上一步构建的线索信息。

　　这里以带线索的二叉链表方式作为存储结构，先序创建一棵二叉树，然后中序线索化这棵二叉树，得到的是一棵中序线索二叉树，此后再中序遍历该二叉树，就可以使用这里的线索信息，不用额外的栈空间。

　　

　　1. biThrTree.h，节点存储结构
#include<stdio.h>
#include<stdlib.h>

#define OK            1
#define ERROR         0
#define OVERFLOW     -1

typedef int Status;

typedef char TElemType;

typedef enum {Link, Thread} PointerTag;

typedef struct BiThrNode{
    TElemType data;
    PointerTag LTag, RTag; // 枚举型的特点，LTag和RTag初始为0，即Link
    struct BiThrNode *lchild, *rchild;
}BiThrNode, *BiThrTree;

BiThrTree pre = NULL;   // 在线索化二叉树中用到，记录遍历过程中，一个节点的前驱

由于枚举型的变量声明是如果没有赋初值，默认设置初值为0，所以等于默认每个BiThrNode实例的LTag和RTag都是Link。

　2. biThrTree.h，简单的遍历操作——打印
Status PrintElement(TElemType e){
    printf("%c", e);
    return OK;
}
``
3. biThrTree.h，先序创建二叉树

`
创建二叉树可以采用任何顺序，这里以先序创建为例。

```cpp
BiThrTree CreateBiThrTree()
{
    TElemType ch;
    BiThrTree T;

    scanf("%c", &ch);
    getchar();  // “吃掉”每次输入到缓冲区中的回车，不能缺少
    if (ch == '$')
        T = NULL;
    else{
        T = (BiThrTree)malloc(sizeof(BiThrNode));
        if(!T)
            exit(OVERFLOW);
        T->data = ch; // 11 - 14行代码与下面两个递归调用的位置体现了创建函数采用的遍历顺序
        printf("Input lchild of %c:\n", ch);
        T->lchild = CreateBiThrTree();
        printf("Input rchild of %c:\n", ch);
        T->rchild = CreateBiThrTree();
    }
    return T;
}

这里以美元符号"$"表示空指针，告诉程序一个节点没有左子树或右子树。
创建一棵二叉树与单纯以某种顺序写出二叉树的遍历结果不同，在创建二叉树时，要以某个符号指定NULL指针，这样程序才知道哪里是叶子节点，哪里不能再向左/右，必须回退了。
具体的例子在本文最后的运行示例中给出

　　4. biThrTree.h，中序线索化已经创建的二叉树
线索化针对的是已经创建好的二叉树，将其中的空指针域利用起来指向前驱后继的过程就是线索化。
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;
        InThreading(p->rchild);
    }
}

Status InOrderThreading(BiThrTree *Thrt, BiThrTree T){
    (*Thrt) = (BiThrTree)malloc(sizeof(BiThrNode)); //头节点不同于二叉树的根节点
    if(!(*Thrt))
        exit(OVERFLOW);
    (*Thrt)->RTag = Thread;
    (*Thrt)->rchild = *Thrt;
    (*Thrt)->LTag = Link;

    if(!T)
        (*Thrt)->lchild = *Thrt;
    else{
        (*Thrt)->lchild = T;
        pre = *Thrt; // 全局的pre，这里初始化指向头结点
        InThreading(T);
        pre->rchild = *Thrt; // 此时pre停留在中序遍历二叉树时的最后一个节点上
        pre->RTag = Thread;
        (*Thrt)->rchild = pre;
    }
    return OK;
}

线索化只针对原来是空的指针域，一个节点如果左指针域为空，那么线索化后该指针域指向其遍历过程中的前驱；类似的，如果其右指针域为空，线索化后右指针域指向其遍历过程的后继。线索化后的二叉链树中不存在空的指针域。
考虑这段代码中的 4 -12 行，一方面线索化的过程只关注已经创建好的二叉树中那些空的指针域；另一方面，上文关于存储结构的介绍已经提到，LTag和RTag的初始值都是Link，所以当中序遍历到达某个节点时，非空的指针域已经不需要再设置Link。
4 -12 行代码中，对于中序遍历到的每一个节点，如果它的左指针域为空，那么我们在这次遍历中将其置为线索，而如果它的右指针域为空，我们在遍历走向下一个节点时线索化上一个节点的右指针域。
这样带来一个问题，一棵树中最后一个被遍历到的节点的右指针域没有被线索化，这也就是 31 - 33 行代码的工作。
InOrderThreading() 创建一个额外的头结点 Thrt ，头结点不同于二叉树的根节点。头结点用来解决遍历二叉树过程中，第一个遍历到的节点没有前驱和最后一个遍历到的节点没有后继的问题。
对于一棵非空的二叉树，Thrt的LTag为Link，左指针指向二叉树的根节点；遍历二叉树时的第一个节点，如果左指针域为空，则将其指向Thrt。Thrt的RTag为Thread，Thrt的右指针指向遍历二叉树时的最后一个节点，同时如果最后一个节点的右指针域为空，则将其指向Thrt。
从而中序线索化时，将会形成一个从Thrt出发，再回到Thrt的闭环，这也是线索化的优势。

　　5. biThrTree.h，中序遍历已经线索化的二叉树
采用某种顺序线索化的二叉树，可以相应地采用同样的顺序进行遍历，中序遍历中序线索二叉树，不需要额外的栈空间支持，根据线索即可完成遍历，适用于需要经常对树进行遍历操作，或者给定某个节点，需要判断其前驱或者后继的情境。
Status InOrderTraverse_Thr( BiThrTree Thrt, Status (*Visit)(TElemType e)){
    BiThrTree p;
    p = Thrt->lchild;
    while(p != Thrt){
        while(p->LTag == Link)
            p = p->lchild; //先走到最左端，开始
        if(!(*Visit)(p->data))
            return ERROR;
        while(p->RTag == Thread && p != Thrt){
            p = p->rchild;// 如果右指针是个线索，直接向后遍历后继
            (*Visit)(p->data);
        }
        if (p != Thrt) // 如果不加区分就走向右子树，很有可能出现死循环，因为 p刚刚停到Thrt，还没进行下一次循环判断，就立刻指向Thrt的后继，循环可能不会终止
            p = p->rchild;
    }
    return OK;

线索化和利用线索的遍历必须遵循相同的顺序。

　#include"biThrTree.h"
// 1. Create Binary Tree with Pre-Order input(Creation can be in any order)

// 2. In-Order Threading this tree (How to threading the tree depends on in what

// order you are goning to traverse the tree.)

// 3. then In-Order Traverse this tree
int main(int argc, char *argv[]){

BiThrTree T, temp;
printf("Creating Binary Thread Tree.\n");
T = CreateBiThrTree();
if(!T)
    return OVERFLOW;
printf("Binary Thread Tree Created.\n");

if(!InOrderThreading(&temp, T))
    return ERROR;

printf("In Order Traversing the Binary Thread Tree:\n");
if(!InOrderTraverse_Thr(temp, &PrintElement))
    return ERROR;
printf("\nIn Order Traversing Accomplished.\n");

return OK;

}

主程序首先创建一棵二叉树，然后对其进行中序线索化，最后中序遍历，打印遍历结果。
下面以输入：
ABC$$DE$G$$F$$$


为例先序构建一棵二叉树，这棵二叉树的样子如下：
A
      /
     B
    /  \
   C   D
       /  \
     E    F
      \
       G

在构建二叉树时，必须指定空指针的位置。
在GCC下编译，程序执行的过程如下：
./a.out 
Creating Binary Thread Tree.
A
Input lchild of A:
B
Input lchild of B:
C
Input lchild of C:
$
Input rchild of C:
$
Input rchild of B:
D
Input lchild of D:
E
Input lchild of E:
$
Input rchild of E:
G
Input lchild of G:
$
Input rchild of G:
$
Input rchild of D:
F
Input lchild of F:
$
Input rchild of F:
$
Input rchild of A:
$
Binary Thread Tree Created.
In Order Traversing the Binary Thread Tree.
CBEGDFA
In Order Traversing Accomplished.

最后介绍一个中序线索化二叉树的优点，即中序线索化后，对于二叉树中的任何一个节点，我们都可以快速地求它的前驱和后继：
前驱：
左指针是Thread，lchild就是前驱

左指针是Link，lchild是其左子树，但是可以找到前驱：中序遍历是先左子树，对于左子树而言，最后遍历左子树的右子树，所以此时一个节点的前驱是其左子树最右下的节点，沿着左子树的右Link一直向下，遇到RTag为Thread的就是目标节点的前驱

后继：
右指针是Thread，则rchild就是后继

右指针是Link，rchild是右子树，但是可以找到后继：中序遍历时，后遍历某个节点的右子树，而该节点的后继就是其右子树中最先被遍历到的，即其右子树最左下的节点，沿着右子树的左Link一直向左下，直到遇到LTag为Thread的就是目标节点的后继。

　　所以，中序线索化还是很便于索引树中任意一个节点的前驱后继关系的。

收起

展开全文

数据结构和算法（十一）：二叉树、线索二叉树、线索二叉树、赫夫曼树

2019-07-15 23:04:53

二叉树的定义 二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空...（注意：不是都需要两棵子树，而是最多可以是两棵，没有子树或者有一棵子树也都是可以的。） 2.左子树和右子树是有顺...

二叉树的定义

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），

或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。



二叉树的特点

1.每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。（注意：不是都需要两棵子树，而是最多可以是两棵，没有子树或者有一棵子树也都是可以的。）

2.左子树和右子树是有顺序的，次序不能颠倒。

3.即使树中某结点只有一棵子树，也要区分它是左子树还是右子树，下面是完全不同的二叉树：



 

二叉树的五种基本形态



特殊的二叉树

斜二叉树 、



 满二叉树



完全二叉树





 

二叉树的性质

二叉树的性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)



二叉树的性质二：深度为k的二叉树至多有2^k-1个结点(k>=1)



二叉树的性质三：

 首先我们再假设度为1的结点数为n1，则二叉树T的结点总数n=n0+n1+n2

其次我们发现连接数总是等于总结点数n-1，并且等于n1+2*n2

所以n-1=n1+2*n2 所以n0+n1+n2-1=n1+n2+n2 最后n0=n2+1



二叉树的性质四

 k=⌊log₂n⌋+1



二叉树的性质五：如果对一棵有n个结点的完全二叉树(其深度为⌊log₂n⌋+1)的结点按层序编号，对任一结点i(1<=i<=n)有以下性质： 如果i = 1，则结点 i 是二叉树的根，无双亲；如果i > 1，则其双亲是结点⌊i/2⌋ 如果2i > n，则结点 i 无做左孩子(结点 i 为叶子结点)；否则其左孩子是结点2i 如果2i+1 > n，则结点 i 无右孩子；否则其右孩子是结点2i+1



二叉树的存储结构

二叉树的顺序存储结构



二叉链表



typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;




二叉树的遍历

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树













算法：

前序遍历：

//前序遍历算法

void ProOrderTraverse( BiTree T)
{
    if( T == NULL)
        return ;

    //显示节点的数据
    printf("%c" , T->data);
    //再先序遍历左子树
    ProOrderTraverse (T->lchild);
    //再遍历右子树
    ProOrderTraverse (T->rchild); 
}

中序遍历：

//中遍历算法

void InOrderTraverse( BiTree T)
{
    if( T == NULL)
        return ;

    //再先序遍历左子树
    InOrderTraverse (T->lchild);

    //显示节点的数据
    printf("%c" , T->data);

    //再遍历右子树
    InOrderTraverse(T->rchild); 
}

后序遍历：

//后续遍历算法
void PostOrderTraverse( BiTree T)
{
    if( T == NULL)
        return ;

    //再先序遍历左子树
    PostOrderTraverse (T->lchild);


    //再遍历右子树
   PostOrderTraverse(T->rchild); 

    //显示节点的数据
    printf("%c" , T->data);
}

推导遍历结果：



三种遍历都是从根结点开始，前序遍历是先打印再递归左和右。所以前序遍历序列为ABCDEF，第一个字母是A被打印出来，就说明A是根结点的数据。再由中序遍历序列是CBAEDF，可以知道C和B是A的左子树的结点，E、D、F是A的右子树的结点









 

 

创建一个二叉树：



#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
CreateBiTree(BiTree *T)
{
	char c;

	scanf("%c", &c);
	if( ' ' == c )
	{
		*T = NULL;
	}
	else
	{
		*T = (BiTNode *)malloc(sizeof(BiTNode));
		(*T)->data = c;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

// 访问二叉树结点的具体操作，你想干嘛？！
visit(char c, int level)
{
	printf("%c 位于第 %d 层\n", c, level);
}

// 前序遍历二叉树
PreOrderTraverse(BiTree T, int level)
{
	if( T )
	{
		visit(T->data, level);
		PreOrderTraverse(T->lchild, level+1);
		PreOrderTraverse(T->rchild, level+1);
	}
}

int main()
{
	int level = 1;
	BiTree T = NULL;

	CreateBiTree(&T);
	PreOrderTraverse(T, level);

	return 0;
}

        线索二叉树

线索二叉树



 

其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，这样对我们的插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。 







#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

// 线索存储标志位
// Link(0)：表示指向左右孩子的指针
// Thread(1)：表示指向前驱后继的线索
typedef enum {Link, Thread} PointerTag;

typedef struct BiThrNode
{
	char data;
	struct BiThrNode *lchild, *rchild;
	PointerTag ltag;
	PointerTag rtag;
} BiThrNode, *BiThrTree;

// 全局变量，始终指向刚刚访问过的结点
BiThrTree pre;

// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateBiThrTree( BiThrTree *T )
{
	char c;

	scanf("%c", &c);
	if( ' ' == c )
	{
		*T = NULL;
	}
	else
	{
		*T = (BiThrNode *)malloc(sizeof(BiThrNode));
		(*T)->data = c;
		(*T)->ltag = Link;
		(*T)->rtag = Link;

		CreateBiThrTree(&(*T)->lchild);
		CreateBiThrTree(&(*T)->rchild);
	}
}

// 中序遍历线索化
void InThreading(BiThrTree T)
{
	if( T )
	{
		InThreading( T->lchild );		// 递归左孩子线索化

		if( !T->lchild )	// 如果该结点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的结点。
		{
			T->ltag = Thread;
			T->lchild = pre;
		}

		if( !pre->rchild )   //如果没有右孩子
		{
			pre->rtag = Thread;
			pre->rchild = T;
		}

		pre = T;       //保持pre指向T的前驱

		InThreading( T->rchild );		// 递归右孩子线索化
	}
}

void InOrderThreading( BiThrTree *p, BiThrTree T )
{
	*p = (BiThrTree)malloc(sizeof(BiThrNode));
	(*p)->ltag = Link;
	(*p)->rtag = Thread;
	(*p)->rchild = *p;
	if( !T )
	{
		(*p)->lchild = *p;
	}
	else
	{
		(*p)->lchild = T;
		pre = *p;
		InThreading(T);
		pre->rchild = *p;
		pre->rtag = Thread;
		(*p)->rchild = pre;
	}
}

void visit( char c )
{
	printf("%c", c);
}

// 中序遍历二叉树，非递归
void InOrderTraverse( BiThrTree T )
{
	BiThrTree p;
	p = T->lchild;

	while( p != T )
	{
		while( p->ltag == Link )
		{
			p = p->lchild;
		}
		visit(p->data);

		while( p->rtag == Thread && p->rchild != T )
		{
			p = p->rchild;
			visit(p->data);
		}
		
		p = p->rchild;
	}
}

int main()
{
	BiThrTree P, T = NULL;
 
	CreateBiThrTree( &T );

	InOrderThreading( &P, T );

	printf("中序遍历输出结果为: ");

	InOrderTraverse( P );

	printf("\n");

	return 0;
}



树、森林及二叉树的相互转换









我们的惊人发现：树、森林的前根（序）遍历和二叉树的前序遍历结果相同，树、森林的后根（序）遍历和二叉树的中序遍历结果相同！

赫夫曼树









这样的二叉树是不是就是最优的赫夫曼树呢







 







 







6.12.3 赫夫曼编码 

原来





赫夫曼





赫夫曼树，即发送和接收必须要约定好同样的赫夫曼编码规则。

收起

展开全文

线索二叉树的介绍
2021-06-01 10:07:49
（1）已知一棵二叉树和它的中序遍历序列：（2）对该二叉树进行改造，如图：注意：这里的前驱和后继指的是遍历序列中的前驱和后继，而不是存储结构的前驱和后继。这个改造也就是“线索化”，如图：（3）线索...
收起
C++二叉树与线索二叉树
2020-03-16 11:45:21
C++二叉树与线索二叉树 二叉树 1.学过数据结构的朋友应该都知道二叉树吧。这是一颗满二叉树，原理自己看书去，了解原理才能够更好的理解代码。我就不在这说原理了。上代码。构造一棵二叉树（左子树先...
收起
数据结构
中序遍历线索二叉树
2018-11-18 19:35:41
中序遍历线索二叉树的实现与操作二叉线索树的结构定义创建一棵二叉树创建一棵二叉树及二叉树基本操作中序遍历二叉树线索化的递归算法通过中序遍历建立中序线索二叉树中序遍历主函数测试二叉线索树的结构定义 ...
收起
线索二叉树之「先序」线索二叉树
2020-03-15 18:35:03
typedef struct ThreadNode{ int data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; ThreadNode *pre=NULL;...//初始化一棵树 void initTree(ThreadTree &T){ T = ...
收起
数据结构之：线索二叉树
2020-05-22 22:35:41
数据结构学习之：线索二叉树线索二叉树1、线索二叉树概述1.1 线索二叉树的使用背景1.2线索二叉树创建原理2、线索二叉树代码实现2.1 线索二叉树创建 线索二叉树 1、线索二叉树概述 1.1 线索二叉树的使用背景对于一颗...
收起
数据结构 java 指针
二叉树学习(二) 线索二叉树
2019-06-26 10:52:52
现有一棵结点数目为n的二叉树，采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域，而结点为n的二叉树一共有n-1条有效分支路径。那么，则二叉链表中存在2n-(n-1)=n+1个空指针域。那么，这些空指针....
收起
数据结构
哈夫曼树和线索二叉树
2017-08-01 16:20:49
线索二叉树的思想来源于二叉树的存储结构中，存在一些空的指针域，因此是否能够将这些空间利用起来，存储一些关于节点间先后顺序的信息，由此产生了线索二叉树。...　线索二叉树的优势是一旦对一棵二叉树建立了相应的线
收起
(※)给线索二叉树加线索
2020-05-02 12:48:01
博客更新至此，已基本完成对普通二叉树操作的学习. 下面我即将和大家分享"线索二叉树"的相关知识：还未完全掌握普通二叉树操作的朋友，... 假设一棵二叉树共有n(n≥1)个结点，那么这棵树中共有2*n=2n个指针域(每个...
收起
算法数据结构
深入学习二叉树(二) 线索二叉树
2019-07-30 06:43:55
现有一棵结点数目为n的二叉树，采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域，而结点为n的二叉树一共有n-1条有效分支路径。那么，则二叉链表中存在2n-(n-1)=n+1个空指针域。那么，这些空指针...
收起
二叉树与线索二叉树
2020-08-19 19:00:05
它是同一棵树中除本身外所有结点的祖先，没有父结点。按上图的树结构来看，根节点就是 1。父结点也叫双亲结点，一个结点如果有上一级，则称这个上一级是它的父结点，如果没有上一级，则该结点无父结点。按上图的...
收起
数据结构算法 java
中序线索二叉树的插入
千次阅读 2020-05-08 14:43:08
原题要求：试写一个算法，在中序全线索二叉树的结点*p之下，插入一棵以结点*x为根、只有左子树的中序全线索二叉树，使*x为根的二叉树称为*p的左子树。若*p原来有左子树，则令它为*x的右子树。完成插入之后的二叉树应...
收起
数据结构 c++ 算法

[各种面试题] 将一棵普通二叉树转换为一棵线索二叉树

图解线索二叉树与双向线索二叉树（附源码）

文章目录

线索二叉树的概念

线索二叉树的结构

二叉树的线索化

线索二叉树进行遍历

双向线索二叉树的概念

双向线索二叉树的实现过程

双向线索二叉树的遍历

总结

线索二叉树

数据结构和算法（十 一）： 二叉树、线索二叉树、线索二叉树、赫夫曼树

二叉树的定义

二叉树的特点

二叉树的五种基本形态

特殊的二叉树

二叉树的性质

二叉树的存储结构

二叉树的遍历

算法：

推导遍历结果：

创建一个二叉树：

线索二叉树

线索二叉树

树、森林及二叉树的相互转换

赫夫曼树

这样的二叉树是不是就是最优的赫夫曼树呢

6.12.3 赫夫曼编码

赫夫曼

赫夫曼树，即发送和接收必须要约定好同样的赫夫曼编码规则。

线索二叉树的介绍

C++二叉树与线索二叉树

中序遍历线索二叉树

线索二叉树之「先序」线索二叉树

数据结构之：线索二叉树

二叉树学习(二) 线索二叉树

哈夫曼树和线索二叉树

(※)给线索二叉树加线索

深入学习二叉树(二) 线索二叉树

二叉树与线索二叉树

中序线索二叉树的插入

一棵线索二叉树

数据结构和算法（十一）：二叉树、线索二叉树、线索二叉树、赫夫曼树