3.二叉树与2度树的区别 (1)二叉树 B B T1 T2 T4 (2)树 A /③⑧ B O B TI T2 T3 T4 0度树 2度树 1度树 2度树
3.二叉树与2度树的区别 (1)二叉树 T4 C A D B D A B C A B T2 T3 C (2)树 A B C T2 2度树 A B C D T5 T3 1度树 T4 2度树 A T1 A T1 0度树 C A B C A B
4.三个结点不同形态的二叉树(5种) T4 T5 5.三个结点不同形态的树(2种) A TI T2
4.三个结点不同形态的二叉树(5种) T1 A B C T2 T3 T4 T5 A B C A B C A B C A B C 5.三个结点不同形态的树(2种) A B C T1 A B C T2
6.二叉树的基本操作 1.置T为空二叉树:T={} 2.销毁二叉树T 3.生成二叉树T: 例:生成哈夫曼树、二叉排序树、平衡二叉树、堆 4.遍历二叉树T 按某种规则访问T的每一个结点一次且仅一次的过程 5.二叉树 树 6.二叉树→平衡二叉树 7.求结点的层号 8.求结点的度 9.求二叉树T的深度 10.插入一个结点 11.删除一个结点 12.求二叉树T的叶子/非叶子 13
6.二叉树的基本操作 1.置T为空二叉树：T={ } 2.销毁二叉树T 3.生成二叉树T： 例：生成哈夫曼树、二叉排序树、平衡二叉树、堆 4.遍历二叉树T： 按某种规则访问T的每一个结点一次且仅一次的过程。 5.二叉树 ←→ 树 6.二叉树 → 平衡二叉树 7.求结点的层号 8.求结点的度 9.求二叉树T的深度 10.插入一个结点 11.删除一个结点 12.求二叉树T的叶子/非叶子 13
6.2.2二叉树的性质和特殊二叉树 1.二叉树的第i(i≥1)层最多有2个结点 ≤20=1个 B ≤21=2个 ≤22=4个 23=8个 二叉树 2.深度为k的二叉树最多有2-1个结点 2+2+.+2 20(1-2
6.2.2 二叉树的性质和特殊二叉树 1.二叉树的第i(i≥1)层最多有2 i-1个结点 二叉树 C A G B E F H ≤20 =1个 ≤23 =8个 ≤22 =4个 ≤21 =2个 2 0 (1- 2 k ) 1- 2 2.深度为k的二叉树最多有2 k -1个结点 2 0 +2 1 + ...+ 2 k-1 = = 2 k -1
3.叶子的数目=度为2的结点数目+1 n0=n2+1 T2 T3 T1:n0=2,n2=1,2=1+1 T2:n0=1,n2=01=0+1 T3:n0=3,n223=2+1
3.叶子的数目=度为2的结点数目+1 n0 = n2 + 1 A B C A B C C A G B E F H T1 T2 T3 T1: n0=2, n2=1, 2=1+1 T2: n0=1, n2=0 1=0+1 T3: n0=3, n2=2 3=2+1