#号法创建树

前面我们记录下来的文章都是手动创建的树,我们还从未尝试过将一组数据动态的在内存中构建成为一棵树。本文将详细介绍使用#号创建法动态的在内存中创建树的详细步骤。当然动态创建树并非就这么一种办法,我们记录的是最常用而且是最方便的方法。

动态创建树有一种方法是根据先序和中序遍历的结果推导出树的结构中内存中创建,办法相对复杂而且难以理解。我们不会做介绍,有兴趣的可以自己查找资料。本文重点介绍的是#号法创建树的过程。有以下这么一组数据。

1 2 4 # # # 3 # #

数据中的#号代表了一棵树的结尾,也就是说,#号前面一个的数据可能是一个叶子节点,也可能是一个没有左子节点的节点。这取决于这个数据后面跟随了几个#号。#号法推导一棵树是使用先序遍历(根、左、右)的方式推导的。那么上面这组数据,我们依次来看,具体的排列是什么样子呢?

1 一定是整棵树的根节点,因为线序遍历优先记录的就是根节点

2 一定是 1 的左子节点

4 就有异议了,他可能是 1 的右子节点,也有可能是 2 的左子节点或 2 的右子节点。但是我们要想到,如果是 1 的右子节点,那么证明 2 肯定已经是左侧子树的叶子节点了,2 的后面应该跟着两个 # 号代表左侧节点的结束标记,而明显上面给出的数据不是这样的,所以 4 为 1 的右子节点不成立,并且间接的证明了,4一定是 2 的左子树,因为 2 后面没有 # 号,而紧随其后的是 4 ,所以可以确定,4 是 2 的左子节点。

# 代表一个节点的结束,紧随 4 的后面,证明是 4 的左侧节点。

# 有跟着一个结束标记,紧随上一个 # ,证明这是 4 的右侧节点。

【已经组建起来的结构】

2015-06-07_214553

 

# 在连续两个结束标记后,又紧随其后的跟着一个 #,看上图,既然 4 已经是叶子节点,那么证明 2 的左侧子树已经遍历完毕,接下来应该是 2 的右子树了。所以这个 # 号是 2 的右子树结束标记。链接后的树结构如下图:

2015-06-07_214810

3 上图中,1 的左侧子树已经全部填充完毕了,那么接下来这个 3 一定就是 1 的右子树。

2015-06-07_215429

 

# # 最后两个都是井号,毋庸置疑,肯定代表节点 3 已经是叶子节点了。最后组成的图如下:

2015-06-07_215608

【代码实现】

上面介绍了具体的思路,我们开始用代码来实现这个需求。

#include <iostream>

using namespace std;

typedef struct tag_bitnode
{
	// 节点的数据
	char data;
	// 节点的左子树
	struct tag_bitnode* leftChild;
	// 节点的右子树
	struct tag_bitnode* rightChild;
}BitNode;

BitNode* create_tree()
{
	char ch;
	scanf_s("%c", &ch);
	if ('#' == ch)
	{
		return NULL;
	}
	// 创建根节点
	BitNode* pNew = (BitNode*)malloc(sizeof(BitNode));
	if (NULL == pNew) return NULL;

	// 赋值
	pNew->data = ch;

	// 创建左子树
	pNew->leftChild = create_tree();

	// 创建右子树
	pNew->rightChild = create_tree();

	return pNew;
}

// 打印树
void show_tree(BitNode* tree)
{
	if (NULL == tree) return;

	printf("%c ", tree->data);

	show_tree(tree->leftChild);
	show_tree(tree->rightChild);
}

int main(int argc, char* argv[])
{
	BitNode* tree = create_tree();
	show_tree(tree);
	return 0;
}

以上代码演示了如何使用#号法创建树,程序运行时,提示你输入一串数据,我们将之前自己组合的一组数据传递进去,按下回车便会组成树结构,并且我们在程序的最后按 先序遍历的方式打印了整个树。

2015-06-07_221311

一棵数据较多的树:

2015-06-07_221132

 

评论