tree树形结构_什么是树形结构

A是根结点，A结点的度是3，D结点的度是3；因为3是结点的度的最大值，所以这棵树的度是3；E、G、H、I、K、L和M是叶子结点。

A在树的第一层，B、C、D在树的第二层，E、F、G、H、I、J在树的第三层，K、L、M在树的第四层；树的深度是4。

树从左往右是有序的，这是一棵有序树；E结点的祖先是A、B。
 

class Node: "定义节点类" def __init__(self,item): self.item=item self.lchild=None self.rchild=None class Tree: "定义树类" def __init__(self): self.root=None def add(self,item): node=Node(item) if not self.root: self.root=node return queue=[self.root,] while queue: current_node=queue.pop(0) if current_node.lchild is None: current_node.lchild=node return else: queue.append(current_node.lchild) if current_node.rchild is None: current_node.rchild=node return else: queue.append(current_node.rchild) def breadth_travel(self): '''广度遍历''' if self.root is None: return queue=[self.root,] while queue: current_node=queue.pop(0) print(current_node.item,end=" ") if current_node.lchild is not None: queue.append(current_node.lchild) if current_node.rchild is not None: queue.append(current_node.rchild) def preorder(self,node): '''先序遍历----根->左->右''' if node is None: return print(node.item,end=" ") self.preorder(node.lchild) self.preorder(node.rchild) def inorder(self,node): '''中序遍历----左->中->右''' if node is None: return self.inorder(node.lchild) print(node.item,end=" ") self.inorder(node.rchild) def postorder(self,node): '''后序遍历----左->右->中''' if node is None: return self.postorder(node.lchild) self.postorder(node.rchild) print(node.item,end=" ") if __name__ == '__main__': tree=Tree() tree.add(0) tree.add(1) tree.add(2) tree.add(3) tree.add(4) tree.add(5) tree.add(6) tree.add(7) tree.add(8) tree.add(9) print('-----广度遍历-----') tree.breadth_travel() print('\n-----深度先序遍历-----') tree.preorder(tree.root) print('\n-----深度中序遍历-----') tree.inorder(tree.root) print('\n-----深度后序遍历-----') tree.postorder(tree.root)

-----广度遍历----- 0 1 2 3 4 5 6 7 8 9 -----深度先序遍历----- 0 1 3 7 8 4 9 2 5 6 -----深度中序遍历----- 7 3 8 1 9 4 0 5 2 6 -----深度后序遍历----- 7 8 3 9 4 1 5 6 2 0