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;

}

评论

5 楼 Qaohao 2009-10-12  

经过我这么一整，虽然也达到了连接叶子的目的，但是破坏了树的结构。

修改树节点定义，增加一个叶子标志位就行了。

struct TNode { 
     TNode* rChild; 
     TNode* lChild; 
     T value; 
     bool isLeaf;
};

   

4 楼 Qaohao 2009-10-12  

是啊。我那天真正理解你的意思，如果串成双向链表以后，叶子的左右子树的指针就不为NULL，这样就不能区分叶子了。多谢指教，看来我考虑问题还不是很周全啊。

3 楼 hellojinjie 2009-10-11  

问题是当你将叶结点串成双链表的时候,叶结点的左右指针已经不是NULL了

2 楼 Qaohao 2009-09-23  

我觉的没有必要增加这个标记，因为当左右子树不存在时，那就是叶子，你觉的了。换句话说，就是这个条件!p->rChild&&!p->lChild成立就是叶子。

1 楼 hellojinjie 2009-09-17  

我晕,,,发个贴还要做什么个小测试.....
===================
二叉树的节点定义,我觉得还应该再增加一个标记,用来标记是否叶节点,不然就无法判断一个节点是否叶子了