python实现对二叉树进行镜像反转

广告位

python实现对二叉树进行镜像反转 题目描述: 二叉树的镜像就是二叉树对称的二叉树就是交换每一个非叶子结点的…

python实现对二叉树进行镜像反转

题目描述:
二叉树的镜像就是二叉树对称的二叉树就是交换每一个非叶子结点的左子树指针和右子树指针 ,如下图所示,请 写 出能实现该功能的代码 。注意 : 请勿对该树做任何假设,它不 一定是平衡树 ,也不 一定有序。
python实现对二叉树进行镜像反转
分析与解答:
从上图可以看出,要实现二叉树的镜像反转,只需交换二叉树中所有结点的左右孩子即 可。由于对所有的结点都做了同样的操作,因此,可以用递归的方法来实现,由于需 要调用 printTreeLayer层序打印 二叉树,这种方法中使用了队列来实现,实现代码如下:

from collections import deque class BiTNode:     def __init__(self):         self.data=None         self.lchild=None         self.rchild=None def fun(root):     if not root:         return None     if root.lchild or root.rchild:         root.lchild,root.rchild=root.rchild,root.lchild     fun(root.lchild)     fun(root.rchild) def arraytotree(arr,start,end):     root=None     if end>=start:         root=BiTNode()         mid=(start+end+1)//2         root.data=arr[mid]         root.lchild=arraytotree(arr,start,mid-1)         root.rchild=arraytotree(arr,mid+1,end)     else:         root=None     return root def printtree(root):     if root==None:         return     queue=deque()     queue.append(root)     while len(queue)>0:         p=queue.popleft()         print(p.data)         if p.lchild!=None:             queue.append(p.lchild)         if p.rchild!=None:             queue.append(p.rchild) if __name__=='__main__':     arr=[1,2,3,4,5,6,7]     root=arraytotree(arr,0,len(arr)-1)     print('二叉树的层次遍历结果')     printtree(root)     print('n')     fun(root)     print('反转后的二叉树层次遍历的结果')     printtree(root) 
二叉树的层次遍历结果 4 2 6 1 3 5 7   反转后的二叉树层次遍历的结果 4 6 2 7 5 3 1 

剪烛西窗, 程

关于作者: 剪烛西窗

为您推荐