feiqds060树的递归遍历.pptx
文本预览下载声明
第五章 二叉树;结点、结点的度、树的度、叶结点、孩子、双亲、兄弟、祖先、子孙、结点层次、树的深度;叶结点：度是零的结点
结点的度：结点的孩子总数
树的度：结点的度的最大值;一棵二叉树是结点的有限集合：
或者为空，
或者由：根结点 +左子树+右子树 组成。;二叉树的性质;;;;;;;;由性质5：完全二叉树适合顺序存储！;空树：None
非空树：[data, left, right]
;tree = [‘*’, [3, None, None],
[‘+’, [5, None, None],
[7, None, None]]]
; 空树：None
非空树：
若结点的左右子树均为空，则为 data
否则：[data, left, right];tree = [‘*’, 3, [‘+’, 5, 7]]
; list表示是利用了Python的list可以含有不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构；
由于list是一个一般意义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。
;class BinTNode:
def __init__(self, data, left = None,
right = None):
self.data = data
self.left = left
self.right = right
;2019/12/5;root = BinTNode(‘*’,
BinTNode(3, None, None),
BinTNode(‘+’, BinTNode(5, None, None),
BinTNode(7, None, None)))
;root = BinTNode(‘*’,
BinTNode(3),
BinTNode(‘+’, BinTNode(5),
BinTNode(7)))
;三叉链表;; 三叉链表相当于线性表中的“双向”链表，方便由孩子找到双亲。;二叉树的递归遍历;
;;;若二叉树为空，则空操作；
否则：
访问根结点 (v)；
先序遍历左子树 (L)；
先序遍历右子树 (R)。
;
先序：- + a * b - c d / e f
;def preorder(tree):
if tree != None:
print(tree[0], end=) # 对根的访问
preorder(tree[1])
preorder(tree[2]);def preorder(root):
if root != None:
print(root.data, end=‘’) # 对根的访问
preorder(root.left)
preorder(root.right);若二叉树为空，则空操作；
否则：
中序遍历左子树 (L)；
访问根结点 (v)；
中序遍历右子树 (R)。
;
中序：a + b * c - d - e / f
后序：a b c d - * + e f / -
;def inorder(root):
if root != None:
inorder(root.left)
print(root.data, end=‘’) # 对根的访问
inorder(root.right);def order(树T):
if tree != None:
order(T的左子树);
order(T的右子树);
}
};;基于遍历的递归算法;def count(root):
if root == None:
return 0
else:
n1 = count(root.left)
n2 = count(root.right)
n = 1 + n1 + n2;
return n
;def num(root):
if root == None:
return 0
else:
return 1 + num(root.left)
显示全部