分类：笔记&教程

数据结构之树-线索二叉树（二）-学习笔记-57

发表于 2018-12-08 | 分类笔记&教程 | 评论数： 0 | 阅读次数： 76

引入

上一节，我们试着解决了树在存储时空间浪费和没法找到双亲结点的问题，这一节，我们着重看一下如何用代码实现。这篇难度有一点大，请务必沉住气，认真仔细。

思路拆解

我们一步一步的拆解代码来看看。

创建树结构体

我们首先声明我们重新设计的线索二叉树结点

char data 存放结点数据
左孩子、右孩子这个不用细说了吧，
Ltag 和 Rtag 主要是判断左孩子和右孩子究竟是指向左右孩子还是前驱后继
我们定义结构体的时候，使用了 typedef
后面所有的 BiTNode 你可以理解为 struct BiTNode，代表该结构体
后面所有的 BiTree 你可以理解为 struct BiTNode *，代表结构体指针
注意上面有个星号哈！

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} NodeState;
typedef struct BiTNode{
    char data;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    NodeState Ltag;
    NodeState Rtag;
}BiTNode,*BiTree;

阅读全文 »

数据结构之树-线索二叉树（一）-学习笔记-56

发表于 2018-12-08 | 分类笔记&教程 | 评论数： 0 | 阅读次数： 54

引入

前面，我们说过，二叉树的遍历方法，以及如何使用代码创建二叉树并将三种遍历顺序都输出出来。如果你还对单链表有印象，我们会发现上节我们树的创建过程其实就是根结点指向左右子树，很像单链表指向唯一后继，对不对？还记得为什么我们要使用双向链表嘛？因为双向链表在找寻唯一前驱的时候方便。因此，二叉树也遇到了相同的问题，左右子树不知道自己的双亲是谁，我们该怎么解决呢？

问题

现在的二叉树

一个结点下，数据域和指针域
数据域，存放数据
指针域，指向该结点下的左右子树

问题一

如果我要找这个结点的双亲该怎么办呢？

麻烦了！我们要重新遍历这个棵二叉树
直到遇到这个结点，然后记录它得双亲

问题二

阅读全文 »

数据结构之树-二叉树的建立及遍历算法（二）-学习笔记-55

发表于 2018-12-07 | 分类笔记&教程 | 评论数： 0 | 阅读次数： 72

引入

上一节，我们详细说明了二叉树的 4 种遍历方式，根据根的位置不同，我们分为前序遍历、中序遍历和后序遍历以及最常用的层序遍历。今天我们就来实战一下，看看如何建立一棵树，并且按照我们需要的方式遍历树上的结点。

需求

根据输入建立一棵二叉树
输出其前序遍历、中序遍历和后序遍历结果

代码分析

首先要构建一棵树，因为是二叉树，所以结构体中包含左右两棵子树

存放数据的data
存放左右子树的指针域

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

struct BiTNode{
    char data;   //用于存放结点数据
    struct BiTNode *Lchild;   //存放左孩子地址
    struct BiTNode *Rchild;   //存放右孩子地址
};