首页 > 代码库 > 算法学习 - 线索二叉树
算法学习 - 线索二叉树
线索二叉树
线索二叉树就是在通用的二叉树里多了点东西,多了什么呢? 前驱和后继,把二叉树变成一个链式的结构。解释下:通常我们的二叉树里,叶子节点是没有孩子,所以指向空也就是NULL
,在线索二叉树里,叶子节点的左右孩子分别指向它自己的前驱和后继,而前驱和后继是哪个节点呢? 就是树遍历过程的前一个节点和后一个节点。所以第一个遍历的节点是没有前驱的,最后一个节点是没有后继的。这里一般都是中序线索二叉树,当然也有先序线索二叉树和后序线索二叉树。
[]a[]
/ []b[] []c[]
/ \
[]d[] []e[]
上面是一个二叉树,我在每个节点两边都添加了一个标签[]
这个标签里面我暂时还没添内容,里面只有两种值,一个是0
一个是1
,当节点有孩子节点的时候,为0
,没有孩子的时候为1
。
所以节点的结构体为:
typedef struct TreeNode* node; struct TreeNode{ node lchild; int ltag; int rtag; node rchild; int data; };
当为0
的时候,指向孩子节点,为1
的时候指向前驱或者后继。
下面附上代码。
代码实现
代码如下:
node Pre = NULL; void InOrderTree(node n){ if (n == NULL) { }else{ // Pre = n; if (n->lchild != NULL) { n->ltag = 0; InOrderTree(n->lchild); }else{ n->ltag = 1; n->lchild = Pre; } if (Pre!=NULL && Pre->rchild == NULL) { Pre->rtag = 1; Pre->rchild = n; } Pre = n; if (n->rchild != NULL) { n->rtag = 0; InOrderTree(n->rchild); }else{ n->rtag = 1; } } }
测试代码(main):
int main(int argc, const char * argv[]) { node head = (node)malloc(sizeof(struct TreeNode)); head->data = http://www.mamicode.com/1;>算法学习 - 线索二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。