Python数据结构之树和二叉树(先序遍历、中序遍历和后序遍历)
程序员文章站
2022-05-07 20:12:20
...
转载自:点击打开链接
树
树是nn(n≥0n≥0)个结点的有限集。在任意一棵非空树中,有且只有一个根结点。
二叉树是有限个元素的集合,该集合或者为空、或者有一个称为根节点(root)的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。
- 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。
- 二叉树的第i层至多有2^{i-1}个结点
- 深度为k的二叉树至多有2^k-1个结点;
- 对任何一棵二叉树T,如果其终端结点数为N0,度为2的结点数为N2,则N0=N2+1
例子
实现以下二叉树,并进行先序遍历、中序遍历和后序遍历。
class BinaryTreeNode(object):
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
class BinaryTree(object):
def __init__(self, root=None):
self.root = root
def is_empty(self):
return self.root == None
def preOrder(self,BinaryTreeNode):
if BinaryTreeNode == None:
return
# 先打印根结点,再打印左结点,后打印右结点
print(BinaryTreeNode.data)
self.preOrder(BinaryTreeNode.left)
self.preOrder(BinaryTreeNode.right)
def inOrder(self,BinaryTreeNode):
if BinaryTreeNode == None:
return
# 先打印左结点,再打印根结点,后打印右结点
self.inOrder(BinaryTreeNode.left)
print(BinaryTreeNode.data)
self.inOrder(BinaryTreeNode.right)
def postOrder(self,BinaryTreeNode):
if BinaryTreeNode == None:
return
# 先打印左结点,再打印右结点,后打印根结点
self.postOrder(BinaryTreeNode.left)
self.postOrder(BinaryTreeNode.right)
print(BinaryTreeNode.data)
n1 = BinaryTreeNode(data="D")
n2 = BinaryTreeNode(data="E")
n3 = BinaryTreeNode(data="F")
n4 = BinaryTreeNode(data="B", left=n1, right=n2)
n5 = BinaryTreeNode(data="C", left=n3, right=None)
root = BinaryTreeNode(data="A", left=n4, right=n5)
bt = BinaryTree(root)
print('先序遍历')
bt.preOrder(bt.root)
print('中序遍历')
bt.inOrder(bt.root)
print('后序遍历')
bt.postOrder(bt.root)
程序运行结果:
先序遍历
A
B
D
E
C
F
中序遍历
D
B
E
A
F
C
后序遍历
D
E
B
F
C
A
[Finished in 0.1s]
推荐阅读
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
Python利用前序和中序遍历结果重建二叉树的方法
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
c++智能指针和二叉树(1): 图解层序遍历和逐层打印二叉树