目录

一、线索二叉树的类型定义

二、各种线索化的二叉树

三、中序线索二叉树的算法

 完整代码

四、有关哈夫曼树的定义

哈夫曼编码

---

一、线索二叉树的类型定义

typedef struct BTNode
{
    ElemType data;//数据域
    struct BTNode* lchild;//左孩子或线索指针
    struct BTNode* rchild;//右孩子或线索指针
    int ltag, rtag;
}BTNode, * BTree;

•  左标志ltag=0，表示lchild指向左孩子结点；ltag=1，表示lchild指向前驱结点
• 右标志rtag=0，表示rchild指向右孩子结点；rtag=1，表示rchild指向后继结点
• 二叉树线索化的基本思想：
• 二叉树的线索化实质上是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查此结点的左、右指针域是否为空，如果为空，将它指向其前驱或后继结点的线索

二、各种线索化的二叉树

 

•  为了操作方便，在存储线索二叉树的时候增设一个头结点，其结构与其他的线索二叉树的结点相同，只是数据域不存储任何数据，其左指针域指向二叉树的根结点，右指针指向遍历的最后一个结点，而二叉树在某种遍历下的第一个结点的前驱和最后一个结点的后继线索都指向头结点。

三、中序线索二叉树的算法

• 第一种方法建立并且遍历中序线索二叉树： 

//第一种方法
void CreatInThread(BTree &T);建立中序线索树
void InThread(BTree& T);//中序遍历二叉树，一边遍历一边线索化
void visit(BTree& q);//访问根结点
void visit2(BTree T);//遍历输出中序线索二叉树

BTNode* pre = NULL;//定义全局变量

void CreatInThread(BTree& T)//建立中序线索树
{
    pre = NULL;
    if (T != NULL)
    {
        InThread(T);//中序线索化二叉树
        if (pre!=NULL&&pre->rchild == NULL)
        {
            pre->rtag = 1;
        }
    }
}

void InThread(BTree& T)//中序遍历二叉树，一边遍历一边线索化
{
    if (T != NULL)
    {
        InThread(T->lchild);//左子树递归线索化
        visit(T);//访问根结点同时线索化
        InThread(T->rchild);//右子树递归线索化
    }
}

void visit(BTree& q)//访问根结点
{
    if (q->lchild == NULL)//左子树为空的时候，让其前驱线索指向空
    {
        q->lchild = pre;
        q->ltag = 1;
     }
    else
    {
        q->ltag = 0;
    }
    if (pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;//建立前驱结点的后继线索（让前驱结点的rchild域存放后继结点的地址）
        pre->rtag = 1;
    }
    else
    {
        q->rtag = 0;
    }
    pre = q;
}

void visit2(BTree T)//遍历中序线索二叉树
{
    BTNode* p = T;
    while (p != NULL)
    {
        while (p->ltag == 0)//找开始结点
        {
            p = p->lchild;
        }
        cout << p->data << " ";//找到中序遍历最开始的结点并输出其data的值
        while (p->rtag == 1 && p->rchild != NULL)
        {
            p = p->rchild;
            cout << p->data << " ";
        }
        p = p->rchild;
    }
    return;
}

•  第二种方法建立并且遍历中序线索二叉树：

//第二种方法
BTree CreatBTree(BTree& T);//中序线索化二叉树，先创建头结点root
void Thread(BTree& T);//中序线索化二叉树
void ThInOrder(BTree T);//在中序线索化二叉树中实现中序遍历（输出）

BTree CreatBTree(BTree & T)//中序线索化二叉树，先创建头结点root
{
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));//创建一个头结点
    if (root == NULL)
    {
        exit(0);
    }
    root->ltag = 0;
    root->rtag = 1;
    root->rchild = T;
    if (T == NULL)//空二叉树
    {
        root->lchild = root;
    }
    else
    {
        root->lchild = T;//头结点的lchild域存放二叉树根结点的地址
        pre = root;
        Thread(T);//中序线索化二叉树
        pre->rchild = root;//最后处理加入头结点的线索
        pre->rtag = 1;
        root->rchild = pre;//头结点线索化

    }
    return root;
}

void Thread(BTree& T)//中序线索化二叉树
{
    if (T != NULL)
    {
        Thread(T->lchild);//左子树线索化
        if (T->lchild == NULL)
        {
            T->lchild = pre;//建立当前结点的前驱线索
            T->ltag = 1;
        }
        else
        {
            T->ltag = 0;
        }
        if (pre != NULL && pre->rchild == NULL)
        {
            pre->rchild = T;//建立前驱结点的后继线索
            pre->rtag = 1;
        }
        else
        {
            if (pre != NULL)
            {
                pre->rtag = 0;
            }
        }
        pre = T;
        Thread(T->rchild);//右子树线索化
    }
}


void ThInOrder(BTree tb)//tb指向中序线索二叉树的头结点
{
    BTNode* p = tb->lchild;
    while (p != tb)
    {
        while (p->ltag == 0)//找中序二叉树的开始结点（开始结点在最左下方）
        {
            p = p->lchild;
        }
        cout << p->data << " ";
        while (p->rtag == 1 && p->rchild != tb)
            //p->rtag=1并且p->rchild!=头结点表示p结点的rchild域存放的是中序遍历的后继结点的地址（线索）
        {
            p = p->rchild;//沿右线索访问后继结点
            cout << p->data << " ";
        }
        p = p->rchild;//转向p的右子树
    }
       
    
}

•  完整代码

#pragma once
#include<iostream>
#include<cstdlib>
#include<stdbool.h>
using namespace std;
#define MAXSIZE 100
typedef char ElemType;
typedef struct BTNode
{
    ElemType data;//数据域
    struct BTNode* lchild;//左孩子或线索指针
    struct BTNode* rchild;//右孩子或线索指针
    int ltag, rtag;
}BTNode, * BTree;
 
BTree Creat(char str[]);//先序序列建立二叉链表

void PreOrder(BTree T);//先序遍历
void InOrder(BTree T);//中序遍历
void PostOrder(BTree T);//后序遍历
void LevelOrder(BTree T);//层序遍历


//第一种方法
void CreatInThread(BTree &T);建立中序线索树
void InThread(BTree& T);//中序遍历二叉树，一边遍历一边线索化
void visit(BTree& q);//访问根结点
void visit2(BTree T);//遍历输出中序线索二叉树


//第二种方法
BTree CreatBTree(BTree& T);//中序线索化二叉树，先创建头结点root
void Thread(BTree& T);//中序线索化二叉树
void ThInOrder(BTree T);//在中序线索化二叉树中实现中序遍历（输出）

//找后继结点
bool InPostNode(BTree& s);//寻找中序线索二叉树的的后继结点

#include"TBTree.h"
BTree Creat(char str[])//先序序列建立二叉链表（方法1）
{
    BTree T;
    static int i = 0;
    ElemType c = str[i++];
    if (c == '#')//输入#表示此结点下不存在分支
    {
        T = NULL;
    }
    else
    {
        T = (BTree)malloc(sizeof(BTree));
        if (T == NULL)
        {
            exit(0);
        }
        T->data = c;
        T->lchild = Creat(str);//递归创建左子树
        T->rchild = Creat(str);//到上一个结点的右边递归创建左右子树
    }
    return T;
}

BTNode* pre = NULL;//定义全局变量

void CreatInThread(BTree& T)//建立中序线索树
{
    pre = NULL;
    if (T != NULL)
    {
        InThread(T);//中序线索化二叉树
        if (pre!=NULL&&pre->rchild == NULL)
        {
            pre->rtag = 1;
        }
    }
}

void InThread(BTree& T)//中序遍历二叉树，一边遍历一边线索化
{
    if (T != NULL)
    {
        InThread(T->lchild);//左子树递归线索化
        visit(T);//访问根结点同时线索化
        InThread(T->rchild);//右子树递归线索化
    }
}

void visit(BTree& q)//访问根结点
{
    if (q->lchild == NULL)//左子树为空的时候，让其前驱线索指向空
    {
        q->lchild = pre;
        q->ltag = 1;
     }
    else
    {
        q->ltag = 0;
    }
    if (pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;//建立前驱结点的后继线索（让前驱结点的rchild域存放后继结点的地址）
        pre->rtag = 1;
    }
    else
    {
        q->rtag = 0;
    }
    pre = q;
}

bool InPostNode(BTree& s)//寻找中序线索二叉树的的后继结点
{
    BTNode* post;
    post = s->rchild;
    if (s->rtag != 1)//结点s有右孩子
    {
        while (post->ltag == 0)//从右子树的根结点开始，沿左指针域往下查找，
            //直到没有左孩子为止
        {
            post = post->lchild;
        }
    }
    s = post;
    return true;
}


void visit2(BTree T)//遍历中序线索二叉树
{
    BTNode* p = T;
    while (p != NULL)
    {
        while (p->ltag == 0)//找开始结点
        {
            p = p->lchild;
        }
        cout << p->data << " ";//找到中序遍历最开始的结点并输出其data的值
        while (p->rtag == 1 && p->rchild != NULL)
        {
            p = p->rchild;
            cout << p->data << " ";
        }
        p = p->rchild;
    }
    return;
}





BTree CreatBTree(BTree & T)//中序线索化二叉树，先创建头结点root
{
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));//创建一个头结点
    if (root == NULL)
    {
        exit(0);
    }
    root->ltag = 0;
    root->rtag = 1;
    root->rchild = T;
    if (T == NULL)//空二叉树
    {
        root->lchild = root;
    }
    else
    {
        root->lchild = T;//头结点的lchild域存放二叉树根结点的地址
        pre = root;
        Thread(T);//中序线索化二叉树
        pre->rchild = root;//最后处理加入头结点的线索
        pre->rtag = 1;
        root->rchild = pre;//头结点线索化

    }
    return root;
}

void Thread(BTree& T)//中序线索化二叉树
{
    if (T != NULL)
    {
        Thread(T->lchild);//左子树线索化
        if (T->lchild == NULL)
        {
            T->lchild = pre;//建立当前结点的前驱线索
            T->ltag = 1;
        }
        else
        {
            T->ltag = 0;
        }
        if (pre != NULL && pre->rchild == NULL)
        {
            pre->rchild = T;//建立前驱结点的后继线索
            pre->rtag = 1;
        }
        else
        {
            if (pre != NULL)
            {
                pre->rtag = 0;
            }
        }
        pre = T;
        Thread(T->rchild);//右子树线索化
    }
}


void ThInOrder(BTree tb)//tb指向中序线索二叉树的头结点
{
    BTNode* p = tb->lchild;
    while (p != tb)
    {
        while (p->ltag == 0)//找中序二叉树的开始结点（开始结点在最左下方）
        {
            p = p->lchild;
        }
        cout << p->data << " ";
        while (p->rtag == 1 && p->rchild != tb)
            //p->rtag=1并且p->rchild!=头结点表示p结点的rchild域存放的是中序遍历的后继结点的地址（线索）
        {
            p = p->rchild;//沿右线索访问后继结点
            cout << p->data << " ";
        }
        p = p->rchild;//转向p的右子树
    }
       
    
}

void PreOrder(BTree T)//先序遍历
{
    if (T != NULL)
    {
        cout << T->data << " ";//访问根结点
        PreOrder(T->lchild);//先序遍历左子树
        PreOrder(T->rchild);//先序遍历右子树
    }
}

void InOrder(BTree T)//中序遍历
{
    if (T != NULL)
    {
        InOrder(T->lchild);
        cout << T->data << " ";
        InOrder(T->rchild);
    }

}
void PostOrder(BTree T)//后序遍历
{
    if (T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->data << " ";
    }
}


void LevelOrder(BTree T)//层序遍历
{
    BTNode* p;
    BTNode* qu[MAXSIZE];//定义循环队列，存放结点指针
    int front, rear;//定义头指针和尾指针
    front = rear = 0;//置队列为空队列
    rear++;
    qu[rear] = T;//根结点指针进队
    rear++;//队尾指针指向队尾元素的后一个位置
    front = (front + 1) % MAXSIZE;//队头指针加1取模
    while (front != rear)//队列不为空
    {
        p = qu[front];//取队头元素
        front = (front + 1) % MAXSIZE;//队头元素出队，队头指针后移
        cout << p->data << " ";
        if (p->lchild != NULL)
        {
            qu[rear] = p->lchild;//p结点的左孩子进栈
            rear = (rear + 1) % MAXSIZE;//队尾指针加1取模
        }
        if (p->rchild != NULL)
        {
            qu[rear] = p->rchild;//p结点的右孩子进栈
            rear = (rear + 1) % MAXSIZE;
        }
    }
}

#include"TBTree.h"

int main()
{
	cout << "二叉树建立的第一种方法" << endl;
	BTree T;//T为指向根结点的指针
	T = (BTree)malloc(50*sizeof(BTree));
	char str[] = { 'a','b','d','#','g','#','#','#','c','e','#','#','f','#','#' };
	T = Creat(str);
	cout << "先序遍历结果：";
	PreOrder(T);//先序遍历
	cout << endl;
	cout << "中序遍历结果：";
	InOrder(T);//中序遍历
	cout << endl;
	cout << "后序遍历结果：";
	PostOrder(T);//后序遍历
	cout << endl;
	cout << "层次遍历的结果：";
	LevelOrder(T);
	cout << endl << endl;


	/*cout << "中序线索树遍历结果：";
	CreatInThread(T);
	visit2(T);
	cout << endl << endl;*/


	cout << "中序遍历结果2：";
	BTree tb;
	tb = (BTree)malloc(50*sizeof(BTree));

	tb = CreatBTree(T);
	ThInOrder(tb);
	//system("pause");
	return 0;
}

四、有关哈夫曼树的定义

• 路径：是指从一个结点到另一个结点之间的分支序列。
• 路径长度：是指从一个结点到另一个结点所经过的分支数目。
• 哈夫曼树：也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树

• 哈夫曼树的构造步骤：

给定n个权值分别为w1，w2...wn的结点
1.将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
2.构造一个新的结点，从F中选取两棵根结点权值最小的树作为新结点的左，右子树，并且将
新结点的权值置为左、右子树上根结点的权值之和。
3.从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4.重复步骤2和3，直至F中只剩下一棵树为止。 

 

哈夫曼编码

• 固定长度编码：每个字符用相等长度的二进制位表示

例如：A--00；B--01；C--10；D--11

• 可变长度编码：允许对不同字符用不等长的二进制位表示

例如：C--0；A--10；B--111；D--110

• 前缀编码：若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

由哈夫曼树得到的哈夫曼编码--字符集中每个字符作为一个叶子结点，各个字符出现的频度作为
结点的权值。