第6章 树和二叉树

第6章树和二叉树6.4先序遍历classTreeNode:def__init__(self,value):self.value=valueself.left=Noneself.right=Noneroot=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)6.4.1递归实现先序遍历defpreorder(root):result=[]defpreorder(root):ifroot:result.append(root.value)preorder(root.left)#先序遍历左子树preorder(root.right)#先序遍历右子树preorder(root)returnresultprint("递归先序遍历结果:",preorder(root))6.4.2非递归实现先序遍历defpreorderTraversal_nonrecursive(root):result=[]stack=[]ifroot:stack.append(root)whilestack:node=stack.pop()result.append(node.value)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresultprint("非递归先序遍历结果:",preorderTraversal_nonrecursive(root))6.5中序遍历6.5.1递归实现中序遍历definorder_traversal(root):ifrootisnotNone:inorder_traversal(root.left)#遍历左子树print(root.value,end='')#访问根节点inorder_traversal(root.right)#遍历右子树print("二叉树中序遍历结果:")inorder_traversal(root)6.5.2非递归实现中序遍历definorderTraversal_nonrecursive(root):result=[]stack=[]current=rootwhilecurrentorstack:#不断将当前节点的左子树节点压入栈，直到左子树为空whilecurrent:stack.append(current)current=current.left#弹出栈顶元素（即当前最左子树的根节点），并将其值加入结果列表current=stack.pop()result.append(current.value)#处理右子树，将当前节点更新为右子树节点，继续循环current=current.rightreturnresultprint("二叉树中序遍历结果:",inorderTraversal_nonrecursive(root))6.6后序遍历6.6.1递归实现后序遍历defPostOrder(root):ifroot==None:returnPostOrder(root.left)#后序遍历左子树PostOrder(root.right)#后序遍历右子树print(root.value,end='')#访问根节点print("二叉树后序遍历结果:")PostOrder(root)6.6.2非递归实现后序遍历defpostorderTraversal_nonrecursive(root):result=[]stack=[]last_visited=None#用于记录上一次访问的节点whilerootorstack:whileroot:stack.append(root)root=root.leftroot=stack.pop()#如果右子树为空或者右子树已经被访问过（即上一次访问的节点是右子树节点）ifnotroot.rightorroot.right==last_visited:result.append(root.value)last_visited=rootroot=None#继续从栈中取节点else:stack.append(root)root=root.rightreturnresultprint("二叉树后序遍历结果:",postorderTraversal_nonrecursive(root))6.7层序遍历fromcollectionsimportdequedeflevel_order_traversal(root):ifrootisNone:return#使用队列来存储待访问的节点queue=deque([root])whilequeue:node=queue.popleft()#从队列中取出一个节点print(node.value,end='')#访问该节点#将该节点的左子节点和右子节点依次加入队列ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)#进行层序遍历level_order_traversal(root)6.9二叉树创建6.9.1递归创建法defcreateBiTree(self,root):data=input()ifdatais"#":#如果当前元素为'#',则认为其为NonereturnNoneelse:root.data=dataroot.lchild=self.createBiTree(root.lchild)//构造左子树 root.rchild=self.createBiTree(root.rchild)//构造右子树returnroot6.9.2非递归创建法基于栈的创建方法#定义二叉树节点类classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefcreate_binary_tree():node_stack=[]val=input("请输入根节点的值（输入None表示该节点为空）：")ifval=="None":returnNoneroot=TreeNode(int(val))node_stack.append(root)whilenode_stack:current=node_stack.pop()#创建并处理左子树left_val=input(f"请输入{current.val}的左子树节点的值（输入None表示为空）：")ifleft_val!="None":left_node=TreeNode(int(left_val))current.left=left_nodenode_stack.append(left_node)#创建并处理右子树right_val=input(f"请输入{current.val}的左子树节点值（输入None表示为空）：")ifright_val!="None":right_node=TreeNode(int(right_val))current.right=right_nodenode_stack.append(right_node)returnroot调用函数如下：#简单的中序遍历函数，用于查看创建的二叉树