1.访问根节点
2.先序遍历左子树
3.先序遍历右子树

1.中序遍历左子树
2.访问根节点
3.中序遍历右子树

1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

# 二叉树类 class BTree(object): # 初始化 def __init__(self, data=None, left=None,
right=None): self.data = data # 数据域 self.left = left # 左子树 self.right = right #

if self.left: self.left.preorder() if self.right: self.right.preorder() #

: print(self.data, end=' ') if self.right : self.right.inorder() # 后序遍历：左->右->中
def postorder(self): if self.left : self.left.postorder() if self.right : self.
right.postorder() if self.data : print(self.data, end=' ') # 层序遍历： def
levelorder(self): # 返回某个节点的左孩子 def LChild_Of_Node(node): return node.left if
node.left else None # 返回某个节点的右孩子 def RChild_Of_Node(node): return node.right if
node.right else None # 层序遍历列表 level_order = [] #

data) level_order.append([self]) # 二叉树的高度 height = self.height() if height >= 1:
# 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据 for _ in range(2, height + 1): level =
[] # 该层的节点 for node in level_order[-1]: # 如果它有左子树，则将左子树节点入队 if LChild_Of_Node(
node): level.append(LChild_Of_Node(node)) # 如果它有右子树，则将右子树结点入队 if RChild_Of_Node(
node): level.append(RChild_Of_Node(node)) if level: # 如果该层非空，则添加该层 level_order.
append(level) # 取出每层中的数据 for i in range(0, height): # 层数 for index in range(len(
level_order[i])): level_order[i][index] = level_order[i][index].data return
level_order# 二叉树的高度 def height(self): # 空的树高度为0, 只有root节点的树高度为1 if self.data is
None: return 0 #左右子树都为空，则当前结点为叶子结点 elif self.left is None and self.right is None
: return 1 elif self.left is None and self.right : return 1 + self.right.height(
) elif self.left and self.right is None: return 1 + self.left.height() else:
return 1 + max(self.left.height(), self.right.height()) # 二叉树的叶子节点 def leaves(
self): if self.data is None: return None elif self.left is None and self.right
is None: print(self.data, end=' ') elif self.left is None and self.right : self.
right.leaves() elif self.right is None and self.left : self.left.leaves() else:
self.left.leaves() self.right.leaves() if __name__ == '__main__': right_tree =
BTree(6) right_tree.left = BTree(2) right_tree.right = BTree(4) left_tree =
BTree(5) left_tree.left = BTree(1) left_tree.right = BTree(3) tree = BTree(11)
tree.left = left_tree tree.right = right_tree left_tree = BTree(7) left_tree.
left= BTree(3) left_tree.right = BTree(4) right_tree = tree # 增加新的变量 tree =
BTree(18) tree.left = left_tree tree.right = right_tree print('先序遍历为:') tree.
preorder() print() print('中序遍历为:') tree.inorder() print() print('后序遍历为:') tree.
postorder() print() print('层序遍历为:') level_order = tree.levelorder() print(
level_order) print() height = tree.height() print('树的高度为%s.' % height) print(
'叶子节点为：') tree.leaves() print() # 先序遍历为: # 18 7 3 4 11 5 1 3 6 2 4 # 中序遍历为: # 3
7 4 18 1 5 3 11 2 6 4 # 后序遍历为: # 3 4 7 1 3 5 2 4 6 11 18 # 层序遍历为: # self: 18 #
[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]] # # 树的高度为4. # 叶子节点为： # 3 4 1 3 2 4

# 二叉树类 class BTree(object): # 初始化 def __init__(self, data=None, left=None,
right=None): self.data = data # 数据域 self.left = left # 左子树 self.right = right #

if self.left: self.left.preorder() if self.right: self.right.preorder() #

: print(self.data, end=' ') if self.right : self.right.inorder() # 后序遍历：左->右->中
def postorder(self): if self.left : self.left.postorder() if self.right : self.
right.postorder() if self.data : print(self.data, end=' ') # 层序遍历： def
levelorder(self): # 返回某个节点的左孩子 def LChild_Of_Node(node): return node.left if
node.left else None # 返回某个节点的右孩子 def RChild_Of_Node(node): return node.right if
node.right else None # 层序遍历列表 level_order = [] #

data) level_order.append([self]) # 二叉树的高度 height = self.height() if height >= 1:
# 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据 for _ in range(2, height + 1): level =
[] # 该层的节点 for node in level_order[-1]: # 如果它有左子树，则将左子树节点入队 if LChild_Of_Node(
node): level.append(LChild_Of_Node(node)) # 如果它有右子树，则将右子树结点入队 if RChild_Of_Node(
node): level.append(RChild_Of_Node(node)) if level: # 如果该层非空，则添加该层 level_order.
append(level) # 取出每层中的数据 for i in range(0, height): # 层数 for index in range(len(
level_order[i])): level_order[i][index] = level_order[i][index].data return
level_order# 二叉树的高度 def height(self): # 空的树高度为0, 只有root节点的树高度为1 if self.data is
None: return 0 #左右子树都为空，则当前结点为叶子结点 elif self.left is None and self.right is None
: return 1 elif self.left is None and self.right : return 1 + self.right.height(
) elif self.left and self.right is None: return 1 + self.left.height() else:
return 1 + max(self.left.height(), self.right.height()) # 二叉树的叶子节点 def leaves(
self): if self.data is None: return None elif self.left is None and self.right
is None: print(self.data, end=' ') elif self.left is None and self.right : self.
right.leaves() elif self.right is None and self.left : self.left.leaves() else:
self.left.leaves() self.right.leaves() # 利用列表构造二叉树 # 列表中至少有一个元素 def
create_BTree_By_List(array): i = 1 # 将原数组拆成层次遍历的数组，每一项都储存这一层所有的节点的数据 level_order
= [] sum = 1 #二叉树每层元素数目为pow(2,n-1),索引为i-1:i*2-1 while sum < len(array):
level_order.append(array[i-1:2*i-1]) i *= 2 sum += i level_order.append(array[i-
1:])#如果不是满二叉树，则剩余的放到最后一层 # BTree_list: 这一层所有的节点组成的列表 # forword_level:

new_BTree_list= []#最终得到一层有左右子树的结点 i = 0 for elem in forword_level:
#这是父节点的集合，给结点分配左右子树 root = BTree(elem) if 2*i < len(BTree_list):#左子树 root.left =
BTree_list[2*i] if 2*i+1 < len(BTree_list):#右子树 root.right = BTree_list[2*i+1]
new_BTree_list.append(root) i += 1 return new_BTree_list # 只有一层：即只有一个节点 if len(
level_order) == 1: return BTree(level_order[0][0]) else: # 二叉树的层数大于1 #

BTree_list= Create_BTree_One_Step_Up(BTree_list, level_order[i]) return
BTree_list[0] if __name__ == '__main__': array = [chr(x) for x in range(65,91)]
tree= create_BTree_By_List(array) print('先序遍历为:') tree.preorder() height = tree.
height() print('树的高度为%s.'%height) print('层序遍历为:') level_order = tree.levelorder(
) print(level_order) print('叶子节点为：') tree.leaves() # 先序遍历为: # A B D H P Q I R S
E J T U K V W C F L X Y M Z G N O 树的高度为5. # 层序遍历为: # self: A # [['A'], ['B',
'C'], ['D', 'E', 'F', 'G'], ['H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'], ['P',
'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']] # 叶子节点为： # P Q R S T U V W X
Y Z N O
<>非递归遍历

1)访问结点P，并将结点P入栈

2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将将结点P入栈并把P的左孩子置为当前的结点P
3)直到P为NULL并且栈为空，则遍历结束。
def preorder_non_recursive(self): mystack = [] # 保存节点的栈 tmp = self # 保存根节点
while mystack or tmp: # 访问左子树直至叶子节点 while tmp: print(tmp.data, end=" ") mystack.
append(tmp) tmp = tmp.left # 左子树为空之后再访问右子树 tmp = mystack.pop() tmp = tmp.right
print("stack", mystack)

1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子
def inorder_non_recursive(self): mystack = [] tmp = self while mystack or tmp:
# 从根节点开始，寻找左子树并入栈 while tmp: mystack.append(tmp) tmp = tmp.left # 出栈并处理当前节点的右子树
tmp= mystack.pop() print(tmp.data, end=" ") tmp = tmp.right

def postorder_non_recursive(self): """利用堆栈后序遍历""" stack1 = [] stack2 = []
stack1.append(self) while stack1: # 找出后序遍历的逆序，存放在 stack2中 node = stack1.pop() if
node.left: stack1.append(node.left) if node.right: stack1.append(node.right)
stack2.append(node) while stack2: # 将 stack2中的元素出栈，即是后序遍历序列 print(stack2.pop().
data, end=' ')

GitHub

Gitee