数据结构与算法（四）：二叉树

二叉树

基本概念

• 结点：结构中的逻辑单元，用于保存数据
• 度数：一个结点的子结点个数

二叉树的性质

1. 最多两个子树，有左右区分
2. 第$i$层的最多有2i−12^{i-1}2i−1个节点

二叉树种类

1. 满二叉树：所有分支结点的度数都是2
2. 扩充二叉树：对二叉树加入足够多的叶子结点，使所有原结点变为度数为2的分支结点
3. 完全二叉树：最后一层叶子都在左边
4. 平衡二叉树：

定义一个二叉树

class Node:def __init__(self, value=None, left=None, right=None):self.value = valueself.left = leftself.right = right

1. 二叉树遍历

• 深度遍历（前中后）
• 广度遍历

#递归
def preTraverse(note):if note == None:returnprint(note.value)preTraverse(note.left)preTraverse(note.right) def midTraverse(note):if note == None:returnmidTraverse(note.left)print(note.value)midTraverse(note.right)def afterTraverse(note):if note == None:return afterTraverse(note.left)afterTraverse(note.right)print(note.value)

#迭代
# pre
def preIter(root):stack = []while stack or root:if root:print(root)stack.append(root.right)stack.append(root.left)else:tmp = stack.pop()# mid
def midIter(root):stack = []while stack or root:if root:stack.append(root)root = root.leftelse:tmp = stack.pop()print(tmp.value)root = tmp.right

#层次遍历

def traversal(root):pass

2. 测试一下是否可行

if __name__ == '__main__':root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))print('preTraverse:')preTraverse(root)print('midTraverse:')midTraverse(root)print('afterTraverse:')afterTraverse(root)

3.已知前序中序遍历，求后续遍历

def findTree1(preList, midList, afterList1):'''wrong program''''if len(preList) == 0:returnif len(preList) == 1:afterList1.append(preList[0])return root = preList[0]n = midList.index(root)findTree1(preList[1:n+1], midList[:n], afterList1)findTree1(preList[n+1:], midList[n+1:], afterList1)afterList1.append(root)def findTree2(preList, midList, afterList2):if len(preList) == 0:returnif len(preList) == 1:afterList2.append(preList[0])returnroot = preList[0]n = midList.index(root)findTree2(preList[1:n + 1], midList[:n], afterList2)findTree2(preList[n + 1:], midList[n + 1:], afterList2)afterList2.append(root)

if __name__ == '__main__':preList = list('12473568')midList = list('47215386')afterList1 = []afterList2 = []findTree1(preList, midList, afterList1)findTree2(preList, midList, afterList2)print(afterList1)print(afterList2)

4.求二叉树的深度和宽度

def getMaxDepth(tree):if tree == None:return 0l = getMaxDepth(tree.left)r = getMaxDepth(tree.right)return max(l, r)+1

参考

1. python： http://www.cnblogs.com/freeman818/p/7252041.html
2. java：https://blog.csdn.net/u012428012/article/details/79089915

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！