那天看到这么一个题目,内容是这样的:
引用
编写一算法,利用叶子结点中的空指针域将所有叶子结点链接为一个双链表,算法返回头结点的地址。
我大概思考了一下,首先得先得到这棵树的一个遍历,然后树中节点的左子树指针相当于双向链表中的prior指针,右子树指针相当于双向链表的next指针,那么头结点应该就是叶子中最左的,我们前面得到的遍历结果中,凡是左右子树都为NULL的就是叶子,只需要将这些链接到双向链表中就OK了。
我给出的伪码如下:
/*
* 假设二叉树的结点定义 如下:
* struct TNode {
* TNode* rChild;
* TNode* lChild;
* T value;
* };
*/
TNode* linkLeaf(TNode* pRoot) {
Stack auxiliaryStack;
Stack inorderStack;
TNode* p=pRoot;
while (true) {
if (p) {
auxiliaryStack.push(p);
p = p->lChild;
} else {
if (auxiliaryStack.size()) {
p = auxiliaryStack.pop();
inorderStack.push(p);
p = p->rChild;
} else {
break;
}
}
}
TNode* pCurLeaf = NULL;
while (inorderStack.size()) {
p = inorderStack.pop();
if (!p->rChild&&!p->lChild) {
if (!pCurLeaf) {
pCurLeaf = p;
} else {
p->rChild = pCurLeaf;
pCurLeaf->lChild = p;
pCurLeaf = p;
}
}
}
return pCurLeaf;
}
分享到:
相关推荐
一个用c语言实现的二叉树的 先序遍历,中序遍历、后序遍历的算法。
用C语言实现的二叉树,包括二叉树的多种遍历方法,恢复方法,求树的深度,结点个数,进行结点的查找等函数的实现。
递归遍历二叉树、c语言以及数据结构均要用到,我还会上传非递归的··
(1)题目一的内容和要求: 1、编写已知二叉树的先序、中序序列,恢复此二叉树的程序 2、编写求二叉树深度的程序 (2)题目二的内容和要求: 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数,运算符为...
二叉树 C语言 二叉树 C语言 二叉树 C语言
C语言数据结构实现二叉树的建立与遍历.cpp
在二叉树类binarytree中增加一个功能,判断是否为完全二叉树(使用自定义的队列类完成)
C语言详细介绍二叉树,及其遍历方法。值得学习
C语言实现二叉树的重建,VC环境下调试,完整源码
利用C语言实现二叉树的一些基本功能,例如建立一颗空二叉树,,向其中插入数据,查找数据,删除数据等功能
利用递归方式完成二叉树的简单创建以及遍历。
c语言动态演示二叉树的遍历,包括先序,中序和后序遍历。
二叉树 二叉树_基于C语言实现的二叉树基本操作
二叉树递归非递归遍历(递归前中后,非递归前中后,层次遍历)
数据结构 二叉树 用C语言创建与遍历 前序 中序遍历 后序遍历
C语言 二叉树实验报告,创建并输出二叉树,输出内容有:图形、数的深度、数的叶子数量。然后根据所创建的二叉树进行线序遍历,创建一棵先序线索二叉树链表,并非递归地输出先序遍历序列。包含各函数算法,源代码。
c语言,二叉树的建立和遍历操作。数据结构Bitree
C语言 二叉树 C 数据结构 用C语言实现建立一棵二叉树 支持插入,删除结点,画出二叉树
二叉树 二叉树_基于C语言实现的二叉树动态可视化打印
数据结构实验,二叉树的建立与遍历,C语言