数据结构 第五章：二叉树

1.基础概念树由根节点和若干个子节点构成的具有一对多关系的数据的集合称为树形结构。空树一个结点都没有根节点最顶层节点叶子节点终端节点没有子节点的结点称为叶子节点节点的度为0分支节点有子节点的节点。度树的深度树的层数树的度广度树中节点最大的度是该树的广度节点的度节点的子节点个数二叉树树的广度为二的树形结构称为二叉树且各节点的左右子节点不能交换。满二叉树在不增加层数的前提下无法再增加一个节点。K层满二叉树第K层的节点个数2^(K-1)K层总共节点个数2^K - 1完全二叉树在满二叉树基础上按照从左至右从上至下的顺序增加节点该树是完全二叉树在满二叉树基础上按照从下至上从右至左的顺序删除节点该树是完全二叉树满二叉树一定是完全二叉树。【例】下面完全二叉树有4567个节点求叶子节点个数。12层总节点数2^12 - 1 4095;第13层叶子节点数4567 - 4095 472第12层节点数2^11 2048第12层叶子节点数2048 - 472 / 2 1812叶子节点数472 1812 2284。二叉树的遍历深度优先遍历算法前序遍历根、左子树、右子树ABFGCDHIE中序遍历左子树、根、右子树FBCGAHIDE后序遍历左子树、右子树、根FCGBIHEDA广度优先遍历算法层序遍历从上至下从左至右逐层遍历ABDFGHECI已知前序遍历和中序遍历结果可以唯一还原一棵二叉树已知后序遍历和中序遍历结果可以唯一还原一棵二叉树2.二叉树链表①构造数据类型②创建二叉树链表③前序遍历④中序遍历⑤后序遍历⑥求总结点数⑦求深度层数⑧层序遍历⑨销毁