Python实现，由父节点往下遍历生成一棵树

Question

已知各节点关系，怎么生成一棵树

用代码怎么实现

Answer 1

前序遍历/先序遍历

通过调用树的preorder函数，生成一个关于树的前序迭代器。（yield函数）

def preorder(self):
    """生成树的前序遍历序列"""
    if not self.is_empty():
        for p in self._subtree_preorder(self.root()):  # 开始迭代
            yield p

def _subtree_preorder(self,p):
    yield p                              # 生成根节点
    for c in self.children(p):           # 对每个根节点的左右子树都进行迭代 直至节点为叶节点
        for other in self._subtree_preorder(c):
            yield other
    

后序遍历

前序遍历和后续遍历的区别在于递归查到子树之后，再生成根节点

def postorder(self):
    """生成树的后序遍历序列"""
    if not self.is_empty():
        for p in self._subtree_preorder(self.root()):  # 开始迭代
            yield p

def _subtree_preorder(self,p):
    for c in self.children(p):           # 对每个根节点的左右子树都进行迭代 直至节点为叶节点
        for other in self._subtree_preorder(c):
            yield other
    yield p                              # 生成根节点

广度优先遍历

BFS不是递归，其借助于队列来管理递归。

from collections import deque
def bfs(self):
	if not self.is_empty():
		a=deque()               # 创建一个空队列
		a.append(self.root())   # 从根节点开始
		while not a.is_empty(): # 循环截止条件是队列pop为空
			p=a.popleft()		# 弹出根节点
			yield p
			for c in self.children(p): # 放入每个根节点的子节点 
				a.append(c)

中序遍历

前三中方法可以用于树的任何结构中，而中序遍历，只能用于二叉树中。
过程和前序、后序遍历类似，更改根节点和左右子树遍历的位置即可

def inorder(self):
	if not self.is_empty():
		for p in self._subtree_inorder(self.root()):
			yield p

def _subtree_inorder(self,p):
	if self.left(p) is not None:          # 遍历左子树
		for other in self._suntree_inorder(self.left(p)):
			yield other
	yield p										# 遍历根节点																		
	if self.right(p) is not None:				# 遍历右子树
		for other in self._suntree_inorder(self.right(p)):
			yield other