当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

线索树

发表于: 2013-05-10   作者:chinrui   来源:转载   浏览次数:
摘要: #include <iostream> #include <stdlib.h> using namespace std; enum PointerTag {LINK , INDEX}; typedef char Elemtype; typedef struct node { Elemtype data; struct node *lch
#include <iostream>
#include <stdlib.h>

using namespace std;

enum PointerTag {LINK , INDEX};
typedef char Elemtype;
typedef struct node {
    Elemtype data;
    struct node *lchild , *rchild;
    PointerTag lTag , rTag;
} *ThreadTree;

//声明所需要用到的函数
void createTree(ThreadTree *);
void displayBefore(ThreadTree);
void displayBetween(ThreadTree);
void inorderThrTree(ThreadTree * , ThreadTree);
void inorderThread(ThreadTree);
void displayThreadTree(ThreadTree);
//用于线索化的时候,记录前一个结点
ThreadTree  pre;

int main()
{
    ThreadTree tree;
    createTree(&tree);
    cout << "先序显示未线索化的树:" << endl;
    displayBefore(tree);
    cout << endl;
    cout << "中序显示未线索化的树:" << endl;
    displayBetween(tree);

    ThreadTree newTree;
    //线索化树
    inorderThrTree(&newTree , tree);

    cout << endl;
    cout << "显示线索化后的树:" << endl;
    displayThreadTree(newTree);
    return 0;
}

//创建一棵树,当输入为空格的时候,其当前结点为NULL
void createTree(ThreadTree *tCurrTree) {
    char cIn;
    cin.get(cIn);
    (*tCurrTree) = NULL;

    if(cIn == '\0') {
        return;
    }

    if(cIn != ' ') {
        (*tCurrTree) = (ThreadTree)malloc(sizeof(node));
        (*tCurrTree)->data = cIn;
        createTree(&(*tCurrTree)->lchild);
        createTree(&(*tCurrTree)->rchild);
    }
}

//先序遍历树显示,用于证明树创建的正确性
void displayBefore(ThreadTree tCurrTree) {
    if(tCurrTree != NULL) {
        cout << tCurrTree->data << " ";
        displayBefore(tCurrTree->lchild);
        displayBefore(tCurrTree->rchild);
    }
}

//中序遍历树显示,用于证明树创建的正确性
void displayBetween(ThreadTree tCurrTree) {
    if(tCurrTree != NULL) {
        displayBefore(tCurrTree->lchild);
        cout << tCurrTree->data << " ";
        displayBefore(tCurrTree->rchild);
    }
}

//用已有的树创建一个带头结点的线索树
void inorderThrTree(ThreadTree *root ,  ThreadTree tree) {

    //创建线索树头结点
    (*root) = (ThreadTree)malloc(sizeof(node));
    if(!(*root)) {
        exit(0);
    }

    //让头结点的左子树为线索,用于让线索化后最后一个结点的右子树指向它
    (*root)->rTag = LINK;
    (*root)->lTag = INDEX;
    (*root)->lchild = (*root);
    if(!tree) {
        (*root)->rchild = (*root);
    } else {
        (*root)->rchild = tree;
        pre = (*root);
        inorderThread(tree);
        pre->rchild = (*root);
        pre->rTag = INDEX;
        (*root)->lchild = pre;
    }

}

//对一个无头指针的树进行线索化
void inorderThread(ThreadTree tCurrTree) {
    if(tCurrTree != NULL) {
        //线索化当前结点的左子树
        inorderThread(tCurrTree->lchild);

        //线索化当前结点,由于其下一个结点不知道
        //所以它的右孩子指针留给它的下一个结点进行线索化
        if(tCurrTree->lchild == NULL) {
            tCurrTree->lTag = INDEX;
            tCurrTree->lchild = pre;
        }
        if(pre->rchild == NULL) {
            pre->rTag = INDEX;
            pre->rchild = tCurrTree;
        }
        pre = tCurrTree;

        //线索化当前结点的右子树
        inorderThread(tCurrTree->rchild);
    }
}

//显示线索化后的树,由于树是中序线索化,所以显示的结果与中序遍历的结果一样
void displayThreadTree(ThreadTree tree) {
    ThreadTree head = tree->rchild;
    while(head != tree) {

        //移动到第一个结点并打印值,即最左下的结点
        while(head->lTag == LINK) {
            head = head->lchild;
        }
        cout << head->data << "  ";

        //判断其右孩子指针是否是线索,如果是直接下移并输出
        //如果不是,移动到它的右子树,进行新一轮的遍历
        if(head->rTag == INDEX && head->rchild != tree) {
            head = head->rchild;
            cout << head->data << "  ";
        }
        head = head->rchild;
    }
}

线索树

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操作,具体什么是线索二叉树,百度一下!
来源:http://www.cnblogs.com/JCSU/articles/2005967.html /* **********************************
#include "stdafx.h" #include <iostream> #include <iomanip> #include <stack>
一、线索二叉树概念 具有 n 个结点的二叉链表中,其二叉链表的 n 个结点中共有 2n 个指针域,在这 2
1 前言 这篇文章主要介绍了线索二叉树,树,森林与二叉树的转换以及赫夫曼树的相关内容。 转载请注
遍历二叉树是按一定的规则将树中的结点排列成一个线性序列,即是对非线性结构的线性化操作。如何找
上一篇总结了二叉树,这一篇要总结的是线索二叉树,我想从以下几个方面进行总结。 1,什么是线索二
中序线索二叉树 /************************************************************************ 线索
男主角: 丹泽尔·华盛顿(饰道格·卡林)    拥有两届奥斯卡影帝头衔的丹泽尔·华盛顿是一个从不停止
男主角: 丹泽尔·华盛顿(饰道格·卡林)    拥有两届奥斯卡影帝头衔的丹泽尔·华盛顿是一个从不停止
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号