论坛首页 编程语言技术论坛

C之一个二叉树题目解答

浏览 3681 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2009-09-17   最后修改:2010-06-13
C
那天看到这么一个题目,内容是这样的:
引用
编写一算法,利用叶子结点中的空指针域将所有叶子结点链接为一个双链表,算法返回头结点的地址。


我大概思考了一下,首先得先得到这棵树的一个遍历,然后树中节点的左子树指针相当于双向链表中的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;

}
   发表时间:2009-09-17  
我晕,,,发个贴还要做什么个小测试.....
===================
二叉树的节点定义,我觉得还应该再增加一个标记,用来标记是否叶节点,不然就无法判断一个节点是否叶子了
0 请登录后投票
   发表时间:2009-09-23  
我觉的没有必要增加这个标记,因为当左右子树不存在时,那就是叶子,你觉的了。换句话说,就是这个条件!p->rChild&&!p->lChild成立就是叶子。
0 请登录后投票
   发表时间:2009-10-11  
问题是当你将叶结点串成双链表的时候,叶结点的左右指针已经不是NULL了
0 请登录后投票
   发表时间:2009-10-12  
是啊。我那天真正理解你的意思,如果串成双向链表以后,叶子的左右子树的指针就不为NULL,这样就不能区分叶子了。多谢指教,看来我考虑问题还不是很周全啊。
0 请登录后投票
   发表时间:2009-10-12  
经过我这么一整,虽然也达到了连接叶子的目的,但是破坏了树的结构。

修改树节点定义,增加一个叶子标志位就行了。
struct TNode { 
     TNode* rChild; 
     TNode* lChild; 
     T value; 
     bool isLeaf;
};
   
0 请登录后投票
论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics