资源简介

(共19张PPT)
4.2
二叉树的基本操作
02
PART
二叉树的基本操作
Click here to add your title
树的实现
树的遍历
满二叉树
节点个数为7=23-1
完全二叉树
节点个数为10<24-1
1.每个节点的度均为2或0
2. 每一层上的结点数都达到最大值
1.至多只有最下两层节点度数小于2
2.最下层的叶子节点依次排在左侧
满二叉树是完全二叉树，
完全二叉树不一定是满
二叉树。
数组表示
完全二叉树
把它不全为一颗完全二叉树，补上的结点分别用虚线表示。
非完全二叉树
优点和缺点
对完全二叉树而言，顺序存储结构既简单又节省存储空间。
一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。
在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。
链表表示
树的实现
二叉树的节点可能有两个孩子，即 左孩子和右孩子，因此二叉树的节点至少需要3个域，一个数据域，2个指针域。也称为二叉链表。
N个节点有几个空指针
树的遍历
前序遍历
(根左右)
树的遍历
中序遍历
(左根右)
树的遍历
后序遍历
(左右根)
1.8-(3+2*6)/5+4
2.8326*+5/-4+
分别输出中序遍历和后序遍历的结果
练一练
后续序遍历就是逆波兰式，逆波兰式用栈是怎么样计算的？
2、对应的中序遍历为？
1、请画出序列为ABC所对应所有的二叉树？
练一练
二叉树的基本操作
树
·二叉树的唯一性
通过二叉树任二种遍历方式能否确定一颗唯一的二叉树呢？
有唯一二叉树：
前序遍历+中序遍历
后序遍历+中序遍历
前序遍历+后序遍历
-----没有唯一二叉树
二叉树的基本操作
树
·二叉树的唯一性
例如：前序遍历：E-A-C-B-D-G-F
中序遍历：A-B-C-D-E-F-G
求其后序遍历顺序？
先画出二叉树，再用后序遍历规则求出其输出顺序
后序遍历：B-D-C-A-F-G-E
E A C B D G F
A B C D E F G
E
ABCD
FG
G
F
A
BCD
C
B
D
二叉树的基本操作
树
·二叉树的唯一性
练习：
后序遍历：H-D-E-B-I-F-J-K-G-C-A
中序遍历：D-H-B-E-A-I-F-C-J-G-K
求其前序遍历顺序？
A-B-D-H-E-C-F-I-G-J-K
练一练
一棵二叉树的前序遍历序列为“abdgecf”，中序遍历序列为“gdbeacf”，则该二叉树的后序遍历序列是( )
A.gdebfca B.gdebcfa C.gdebafc D.gedbfca
A
二叉树Python代码实现
class Node: #建立二叉树
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
二叉树Python代码实现
root=Node('A',Node('B',Node('D'),Node('E')),Node('C',rigt=Node('F',Node('G'))))
print("前序遍历：")
preTraverse(root)
print("中序遍历：")
midTraverse(root)
print("后序遍历：")
afterTraverse(root)
if __name__=='__main__’:
二叉树Python代码实现
def preTraverse(root):#前序遍历
if root==None:
return
print(____________)
preTraverse(_____________)
preTraverse(______________)
def midTraverse(root): #中序遍历
if root==None:
return
midTraverse(____________)
print(_____________)
midTraverse(____________)
def afterTraverse(root): #后序遍历
if root==None:
return
afterTraverse(_____________)
afterTraverse(_____________)
print(______________)
root.value
root.left
root.left
root.value
root.right
root.left
root.right
root.value
root.right
CREATIVE FASHION GENERAL PPT TEMPLATE
谢谢观看！

展开更多......

收起↑