• 数据结构题型16-线索二叉树

    文章目录

    1 参考博客：

    1、【图解】数据结构代码领背-中序建立线索二叉树
    2、【数据结构】中序线索二叉树的实现(源代码以及讲解)

    2 线索二叉树的节点结构

    在这里插入图片描述
    在这里插入图片描述

    3、分析他人博客

    具体博客地址请参考：【数据结构】中序线索二叉树的实现(源代码以及讲解)

    首先需要进行二叉树的创建。

    #define _CRT_SECURE_NO_WARNINGS

//参考博客：
//https://zhuanlan.zhihu.com/p/590566514
//https://blog.csdn.net/Zhangsama1/article/details/121362652
#include   //引入头文件
#include   
using namespace std;

typedef char Elemtype;

#define Maxsize 5
#define STR_SIZE 1024
#define ERROR 0
#define OK    1

enum Tag { Link, Thead };
/*建立线索二叉树的结构体*/
typedef struct ThreadNode
{
	Elemtype data; //数据域
	struct ThreadNode* lchild;//左孩子指针域
	struct ThreadNode* rchild;//右孩子指针域
	int ltag;  //左标志位 0 1
	int rtag;  //右标志位 0 1
}ThreadNode, * ThreadTree;

void CreateBinaryTree(ThreadTree& T);
void draw_level(ThreadNode* node, bool left, char* str);
void draw(ThreadNode* root);

int main()
{
	ThreadTree T=NULL;
	CreateBinaryTree(T);
	draw(T);
	return 0;
}

//新建二叉树  ABD##E##C##
void CreateBinaryTree(ThreadTree& T)
{
	Elemtype ch;
	cin >> ch;
	if (ch == '#')
		T = NULL;
	else
	{
		T = (ThreadTree)malloc(sizeof(ThreadNode));
		if (T == NULL)
			exit(false);
		T->data = ch;
		T->ltag = Link;   //初始化设定左右子树为指针类型
		T->rtag = Link;
		CreateBinaryTree(T->lchild);  //构建左子树
		CreateBinaryTree(T->rchild);   //构建右子树
	}
}

/*****************************************************************************
* @date   2020/4/19
* @brief  水平画树
* @param  node	二叉树节点
* @param  left	判断左右
* @param  str 	可变字符串
*****************************************************************************/
void draw_level(ThreadNode* node, bool left, char* str) {
    if (node->rchild) {
        draw_level(node->rchild, false, strcat(str, (left ? "|     " : "      ")));
    }

    printf("%s", str);
    printf("%c", (left ? '\\' : '/'));
    printf("-----");
    printf("%c\n", node->data);

    if (node->lchild) {
        draw_level(node->lchild, true, strcat(str, (left ? "      " : "|     ")));
    }
    //  "      " : "|     " 长度为 6
    str[strlen(str) - 6] = '\0';
}

/*****************************************************************************
* @date   2020/4/19
* @brief  根节点画树
* @param  root	二叉树根节点
*****************************************************************************/
void draw(ThreadNode* root) {
    char str[STR_SIZE];
    memset(str, '\0', STR_SIZE);

    /**
     * 1. 在 windows 下，下面是可执行的
     * 2. 在 Linux   下，执行会报 Segmentation fault
     *      需要使用中间变量
     */
    if (root->rchild) {
        draw_level(root->rchild, false, str);
    }
    printf("%c\n", root->data);
    if (root->lchild) {
        draw_level(root->lchild, true, str);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106

    在这里插入图片描述
    在这里插入图片描述

    #define _CRT_SECURE_NO_WARNINGS

//参考博客：
//https://zhuanlan.zhihu.com/p/590566514
//https://blog.csdn.net/Zhangsama1/article/details/121362652
#include   //引入头文件
#include   
using namespace std;

typedef char Elemtype;

#define Maxsize 5
#define STR_SIZE 1024
#define ERROR 0
#define OK    1

enum Tag { Link, Thead };
/*建立线索二叉树的结构体*/
typedef struct ThreadNode
{
	Elemtype data; //数据域
	struct ThreadNode* lchild;//左孩子指针域
	struct ThreadNode* rchild;//右孩子指针域
	int ltag;  //左标志位 0 1
	int rtag;  //右标志位 0 1
}ThreadNode, * ThreadTree;

void CreateBinaryTree(ThreadTree& T);
void draw_level(ThreadNode* node, bool left, char* str);
void draw(ThreadNode* root);
void createInThread(ThreadTree T);
void inThread(ThreadTree& p, ThreadTree& pre);

int main()
{
	ThreadTree T=NULL;
	CreateBinaryTree(T);
	draw(T);
	createInThread(T);
	return 0;
}

//新建二叉树  ABD##E##C##
void CreateBinaryTree(ThreadTree& T)
{
	Elemtype ch;
	cin >> ch;
	if (ch == '#')
		T = NULL;
	else
	{
		T = (ThreadTree)malloc(sizeof(ThreadNode));
		if (T == NULL)
			exit(false);
		T->data = ch;
		T->ltag = Link;   //初始化设定左右子树为指针类型
		T->rtag = Link;
		CreateBinaryTree(T->lchild);  //构建左子树
		CreateBinaryTree(T->rchild);   //构建右子树
	}
}

/*****************************************************************************
* @date   2020/4/19
* @brief  水平画树
* @param  node	二叉树节点
* @param  left	判断左右
* @param  str 	可变字符串
*****************************************************************************/
void draw_level(ThreadNode* node, bool left, char* str) {
    if (node->rchild) {
        draw_level(node->rchild, false, strcat(str, (left ? "|     " : "      ")));
    }

    printf("%s", str);
    printf("%c", (left ? '\\' : '/'));
    printf("-----");
    printf("%c\n", node->data);

    if (node->lchild) {
        draw_level(node->lchild, true, strcat(str, (left ? "      " : "|     ")));
    }
    //  "      " : "|     " 长度为 6
    str[strlen(str) - 6] = '\0';
}

/*****************************************************************************
* @date   2020/4/19
* @brief  根节点画树
* @param  root	二叉树根节点
*****************************************************************************/
void draw(ThreadNode* root) {
    char str[STR_SIZE];
    memset(str, '\0', STR_SIZE);

    /**
     * 1. 在 windows 下，下面是可执行的
     * 2. 在 Linux   下，执行会报 Segmentation fault
     *      需要使用中间变量
     */
    if (root->rchild) {
        draw_level(root->rchild, false, str);
    }
    printf("%c\n", root->data);
    if (root->lchild) {
        draw_level(root->lchild, true, str);
    }
}



void createInThread(ThreadTree T)
{
	ThreadTree pre = NULL;
	if (T != NULL)
	{
		inThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}


void inThread(ThreadTree& p, ThreadTree& pre)
{
	if (p != NULL)
	{
		inThread(p->lchild, pre);
		if (p->lchild == NULL)
		{
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL)
		{
			pre->rchild = p;
			pre->rtag = 1;
		}

		pre = p;
		inThread(p->rchild, pre);
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
  • 相关阅读:
    基础Redis-Java客户端操作介绍
    6月7日 Linux 基础学习——常用文件管理命令、tmux 和 vim
    pyqt5-tools的安装（深度学习）
    Log4j比较配置信息
    攻击检测和防护
    PHP基于Thinkphp的莆田学院图书馆管理系统毕业设计-附源码071418
    redis5.0配置一主两从三哨兵
    如何在 Docker 容器中运行 MySQL
    LeetCode19.删除链表的倒数第N个结点
    如何判断一个点在地图上？如何判断一个点在多边形内？
  • 原文地址：https://blog.csdn.net/qq_41735476/article/details/133708453