第五章 树 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.

Presentation on theme: "第五章 树 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件."— Presentation transcript:

1 第五章 树 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

2 本章主要内容 树的基本概念 二叉树 二叉树的存储表示 二叉树的遍历及其应用 二叉树遍历的非递归算法 二叉树的计数 树与二叉树的转换 堆
Huffman树及其应用

3 树的基本概念 树是由n (n>0) 个结点组成的有限集合： 这个定义是递归的 有一个特定的称之为根 (root) 的结点；
除根以外的其它结点划分为 m (m≥0) 个互不相交的有限集合T1, T2, …, Tm，其中每个集合也是一棵树，并被称为根的子树。 这个定义是递归的

4 树的基本概念 A 1层 深度 = 2 B C D 2层 深度 = 4 高度 = 4 高度 = 3 E F G H I J 3层 K L M
根 A 1层 深度 = 2 B C D 2层 深度 = 4 高度 = 4 高度 = 3 E F G H I J 3层 K L M 4层 结点 结点的度 叶结点 分支结点 子女结点 父结点 兄弟结点 祖先结点 子孙结点 结点所处层次 树的深度 树的高度 树的度 有序树 无序树 森林

5 树的基本概念 树的其他表示方法 A B C D E F G H I J K L M A B C D E F G H I J K L M A
集合表示 凹入表表示 目录表示

6 二叉树 二叉树是结点的有限集合： 这个定义也是递归的 该集合或者为空；
或者由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 这个定义也是递归的 Ф L R L R 空 只有根 右子树为空 右子树为空 左右子树不为空

7 二叉树 性质1 若二叉树的层次从 1 开始, 则在二叉树的第 i ( i≥1)层最多有 2i-1 个结点。 证明：(用数学归纳法)
若设 i = k 时性质成立，即该层最多有 2k-1 个结点，则当 i = k+1 时，由于第 k 层每个结点最多可有 2 个子女，第 k+1 层最多结点个数可有 2*2k-1 = 2k 个，故性质成立。

8 二叉树 性质2 高度为 h (h≥1) 的二叉树最多有 2h -1个结点。 证明：(用求等比级数前k项和的公式)
空树的高度为 0，只有根结点的树的高度为 1。

9 二叉树 性质3 对任何一棵非空二叉树, 如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有n0＝n2＋1 证明：
若设度为 1 的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0+n1+n2，且 e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1，n0 = n2+1

10 二叉树 满二叉树 完全二叉树 深度为k的满二叉树是有2k-1个结点的二叉树 特点：每一层结点数都达到了最大数

11 二叉树 1 2 4 5 8 9 10 11 12 13 14 15 3 6 7 1 2 4 5 8 9 10 3 6 7 满二叉树 完全二叉树

12 二叉树 性质4 具有n个结点的完全二叉树的深度为log2(n+1) 证明： 设完全二叉树的深度为h，则有 2h-1-1＜n ≤ 2h-1
h-1＜log2(n+1)≤h h = log2(n+1) 1 2 4 5 10 13 15 3 6 7 上面h-1层结点数 包括h层的最大结点数 性质4也适用于理想平衡二叉树

13 二叉树 性质5 若将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3,…,n，则有：
4 5 8 9 10 3 6 7 二叉树 性质5 若将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3,…,n，则有： 若i = 1, 则 i 无父结点； 若i > 1, 则 i 的父结点为i/2； 若2*i ≤ n, 则 i 的左子女为 2*i； 若2*i+1 ≤ n, 则 i 的右子女为2*i+1； 若 i 为奇数, 且i !=1, 则其左兄弟为i-1； 若 i 为偶数, 且i != n，则其右兄弟为i+1。 i所在层次为log2(i+1)（或者log2i +1，两者等效）

14 二叉树的存储表示 二叉树的数组存储表示 1 2 4 5 8 9 10 11 12 13 14 15 3 6 7 1 2 4 5 8 9 10 11 12 3 6 7 4 6 7 8 9 3 2 1 13 15 一般二叉树的顺序表示 4 5 6 7 8 9 3 2 1 10 11 12 完全二叉树的顺序表示

15 二叉树的存储表示 二叉树的数组存储表示 完全二叉树适用于数组存储表示 一般二叉树不适用 1 2 4 5 8 9 10 11 12 13 14
15 3 6 7 7 3 1 15 单支树的顺序表示

16 二叉树的存储表示 二叉树的链表存储表示 Struct TNode{ Type Data; TNode *leftChild;
TNode *rightChild; TNode *parent; }; 二叉树的链表存储表示 左孩子指针 右孩子指针 左孩子指针 右孩子指针 leftChild data rightChild leftChild data parent rightChild parent data data leftChild rightChild leftChild rightChild 二叉链表 三叉链表 找子女时间O(1)， 找父亲要从根开始，时间O(log2i) 找子女时间O(1)， 找父亲时间O(1)

17 二叉树的存储表示 二叉树的链表存储表示 A B C D G E F root root root A ʌ A ʌ B A C ʌ D A ʌ
二叉链表 三叉链表

18 二叉树的存储表示 二叉树的链表存储表示 A B C D G E F root data parent leftChild
rightChild A -1 1 B 2 3 C D 4 5 E 6 F G A B C D G E F 静态链表结构 二叉树

19 二叉树的遍历及其应用 二叉树的遍历就是按某种次序访问树中的结点一次且仅一次 遍历次序一般有 访问当前结点记为V 访问结点的左子树记为L
访问结点的右子树记为R 遍历次序一般有 前序遍历 (VLR) 中序遍历 (LVR) 后序遍历 (LRV)

20 二叉树的遍历及其应用 - + a e f b - c d 前序遍历 (VLR) 首先访问当前结点 (V) 其次前序遍历左子树 (L)
/ a e × f void PreOrder ( BinTreeNode *T ) { if ( T != NULL ) { visit( T->data ); PreOrder ( T->leftChild ); PreOrder ( T->rightChild ); } b - c d 前序遍历： – + a × b – c d / e f

21 二叉树的遍历及其应用 - + / a e f b - c d 中序遍历 (LVR) 首先中序遍历左子树 (L) 其次访问当前结点 (V)
× f void InOrder ( BinTreeNode *T ) { if ( T != NULL ) { InOrder ( T->leftChild ); visit( T->data ); InOrder ( T->rightChild ); } b - c d 中序遍历： a + b × c – d – e / f

22 二叉树的遍历及其应用 - + / a e f b - c d 后序遍历 (LRV) 首先后序遍历左子树 (L) 其次后序遍历右子树 (R)
× f void PostOrder ( BinTreeNode *T ) { if ( T != NULL ) { PostOrder ( T->leftChild ); PostOrder ( T->rightChild ); visit( T->data ); } b - c d 后序遍历： a b c d – × + e f / –

23 二叉树的遍历及其应用 三种遍历路线相同，结果不同 前序遍历： – + a × b – c d / e f
- + / a × e f b - c d

24 二叉树的遍历及其应用 计算二叉树的结点个数 (后序遍历) 对左子树递归计数a 对右子树递归计数b 返回1+a+b
int Count ( BinTreeNode *T ) { if ( T == NULL ) return 0; else { int a = Count ( T->leftChild ); int b = Count ( T->rightChild ); return 1+a+b; }

25 二叉树的遍历及其应用 计算二叉树的深度 (后序遍历) 计算左子树的深度a 计算右子树的深度b 返回(a>b)?a+1:b+1
int Height ( BinTreeNode *T ) { if ( T == NULL ) return 0; else { int a = Height ( T->leftChild ); int b = Height ( T->rightChild ); return (a>b)?a+1:b+1; }

26 二叉树的遍历及其应用 二叉树的复制 (前序遍历) 复制根结点数据 复制左子树 复制右子树 返回根结点指针
BinTreeNode * Copy( BinTreeNode *T ) { if ( T == NULL ) return NULL; else { BinTreeNode * temp = new BinTreeNode; temp->data = T->data; Temp->leftChild = Copy ( T->leftChild ); Temp->rightChild = Copy( T->rightChild ); return temp; }

27 二叉树的遍历及其应用 判断两棵二叉树是否相等 (前序遍历) 判断两棵树数据是否相等 判断两棵树左子树是否相等 判断两棵右子树是否相等
bool BinTreeNode * equal ( BinTreeNode *a, BinTreeNode *b ) { if ( a == NULL && b == NULL ) return true; else if ( a!=NULL && b!=NULL ) { bool r = ( a->data == b->data ); bool s = equal ( a->leftChild, b->leftChild ); bool t = equal ( a->rightChild, b->rightChild ); if (r && s && t) return true; else return false; }

28 二叉树的遍历及其应用 前序遍历建立二叉树 结点值为正整数，每个结点有2个或0个孩子结点 输入结点值的顺序对应二叉树前序遍历顺序
0表示叶子结点 1 void CreatBinTree ( BinTreeNode *T ) { scanf (“%d”, &item); if ( item == 0) T = NULL; else { T = new BinTreeNode; T->data = item; CreatBinTree( T->leftChild ); CreatBinTree( T->rightChild ); } 2 3 4 5 6 7 前序遍历对应的整数序列：

29 二叉树的遍历及其应用 前序遍历输出二叉树 以凹入表表示输出 1 2 4 5 3 6 7
void PrintBinTree ( int depth, BinTreeNode *T ) { if (T != NULL) { for (int i=1; i<depth; i++) printf (“ ”); //输出(depth-1)*4个空格 printf (“%d ”, T->data); for (int i=6; i>depth; i--) printf(“****”);//输出(6-depth)*4个星号 PrintBinTree( depth+1, T->leftChild ); PrintBinTree( depth+1, T->rightChild ); } 凹入表表示： 1 2 4 5 3 6 7 1 ******************** 2 **************** 4 ************ 5 ************ 3 **************** 6 ************ 7 ************

30 二叉树遍历的非递归算法 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1
2 4 5 3 6 7 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1入栈 1出栈，其右左孩子3和2入栈 top 1 空栈 top

31 二叉树遍历的非递归算法 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1
2 4 5 3 6 7 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1入栈 1出栈，其右左孩子3和2入栈 2出栈，其右左孩子5和4入栈 top 2 top 3 空栈 top

32 二叉树遍历的非递归算法 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1
2 4 5 3 6 7 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1入栈 1出栈，其右左孩子3和2入栈 2出栈，其右左孩子5和4入栈 4出栈，其无孩子 top 4 5出栈，其无孩子 top 5 3出栈，其右左孩子7和6入栈 top 3 空栈 top

33 二叉树遍历的非递归算法 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1
2 4 5 3 6 7 利用栈的前序遍历非递归算法 根先入栈 栈非空时循环 出栈一个结点v，对v进行操作 v的右孩子入栈，v的左孩子入栈 1入栈 1出栈，其右左孩子3和2入栈 2出栈，其右左孩子5和4入栈 4出栈，其无孩子 5出栈，其无孩子 top 6 3出栈，其右左孩子7和6入栈 top 7 6出栈，其无孩子 7出栈，其无孩子 空栈 top 出栈顺序，即遍历顺序为：

34 二叉树遍历的非递归算法 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1 2 4 5
3 6 7 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1入栈，1的左孩子2入栈，2的左孩子4入栈 4出栈，其无右孩子 2出栈，其右孩子5入栈 top 4 top 2 top 1 空栈 top

35 二叉树遍历的非递归算法 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1 2 4 5
3 6 7 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1入栈，1的左孩子2入栈，2的左孩子4入栈 4出栈，其无右孩子 2出栈，其右孩子5入栈 5出栈，其无右孩子 1出栈，1的右孩子3入栈，3的左孩子6入栈 top 5 top 1 空栈 top

36 二叉树遍历的非递归算法 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1 2 4 5
3 6 7 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1入栈，1的左孩子2入栈，2的左孩子4入栈 4出栈，其无右孩子 2出栈，其右孩子5入栈 5出栈，其无右孩子 1出栈，1的右孩子3入栈，3的左孩子6入栈 top 6 6出栈，其无右孩子 top 3 3出栈，其右孩子7入栈 空栈 top

37 二叉树遍历的非递归算法 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1 2 4 5
3 6 7 利用栈的中序遍历非递归算法 1. 只要入栈一直向左直到结点为空 2. 只要出栈访问，然后右孩子入栈 1入栈，1的左孩子2入栈，2的左孩子4入栈 4出栈，其无右孩子 2出栈，其右孩子5入栈 5出栈，其无右孩子 1出栈，1的右孩子3入栈，3的左孩子6入栈 6出栈，其无右孩子 top 7 3出栈，其右孩子7入栈 7出栈，其无右孩子 空栈 top 出栈顺序，即遍历顺序为：

38 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 1 2 4 5 3 6 7 每新入栈一个结点一直向左入栈直到为空，标识L
当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R top 4, L top 2, L top 1, L 空栈 top 栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历

39 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 1 2 4 5 3 6 7 每新入栈一个结点一直向左入栈直到为空，标识L
当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R 4无右子树，4R出栈 2访完左子树，访2右子树，栈顶改为2R，5L入栈 top 4, R top 2, L 1, L 栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历

40 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 1 2 4 5 3 6 7 每新入栈一个结点一直向左入栈直到为空，标识L
当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R 4无右子树，4R出栈 2访完左子树，访2右子树，栈顶改为2R，5L入栈 5无左子树，访5右子树，栈顶改为5R top 5, L top 2, R 1, L 栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历

41 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 1 2 4 5 3 6 7 每新入栈一个结点一直向左入栈直到为空，标识L
当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R 4无右子树，4R出栈 2访完左子树，访2右子树，栈顶改为2R，5L入栈 5无左子树，访5右子树，栈顶改为5R 5无右子树，5R出栈 2访完右子树，2R出栈 top 5, R 1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈 top 2, R top 1, L 栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历

42 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 1 2 4 5 3 6 7 每新入栈一个结点一直向左入栈直到为空，标识L
当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R 4无右子树，4R出栈 2访完左子树，访2右子树，栈顶改为2R，5L入栈 5无左子树，访5右子树，栈顶改为5R 5无右子树，5R出栈 2访完右子树，2R出栈 top 6, L 1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈 top 3, L 6无左子树，访6右子树，栈顶改为6R top 1, R 栈顶标识若为L可理解为对左子树进行遍历，栈顶标识若为R可理解为对右子树进行遍历

43 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 1 2 4 5 3 6 7 每新入栈一个结点一直向左入栈直到为空，标识L
当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R 4无右子树，4R出栈 2访完左子树，访2右子树，栈顶改为2R，5L入栈 5无左子树，访5右子树，栈顶改为5R 5无右子树，5R出栈 2访完右子树，2R出栈 top 6, R 1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈 top 3, L 6无左子树，访6右子树，栈顶改为6R 6无右子树，6R出栈 1, R 3访完左子树，访3右子树，栈顶改为3R，7L入栈；

44 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 1 2 4 5 3 6 7 每新入栈一个结点一直向左入栈直到为空，标识L
当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R 4无右子树，4R出栈 2访完左子树，访2右子树，栈顶改为2R，5L入栈 5无左子树，访5右子树，栈顶改为5R 5无右子树，5R出栈 2访完右子树，2R出栈 top 7, L 1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈 top 3, R 6无左子树，访6右子树，栈顶改为6R 6无右子树，6R出栈 1, R 3访完左子树，访3右子树，栈顶改为3R，7L入栈； 7无左子树，访7右子树，栈顶改为7R

45 二叉树遍历的非递归算法 利用栈的后序遍历非递归算法 出栈顺序，即遍历顺序为：4 5 2 6 7 3 1 1 2 4 5 3 6 7
每新入栈一个结点一直向左入栈直到为空，标识L 当遍历完左子树并从左子树退回时，将栈顶标识改为R，再去遍历右子树 从右子树退回（即第二次退回）时才访问数据 访1左子树，1L入栈；访2左子树，2L入栈；访4左子树，4L入栈 4无左子树，访4右子树，栈顶改为4R 4无右子树，4R出栈 2访完左子树，访2右子树，栈顶改为2R，5L入栈 出栈顺序，即遍历顺序为： 5无左子树，访5右子树，栈顶改为5R 5无右子树，5R出栈 2访完右子树，2R出栈 top 7, R 1访完左子树，访1右子树，改为1R，3L入栈；访6左子树，6L入栈 top 3, R 6无左子树，访6右子树，栈顶改为6R 6无右子树，6R出栈 top 1, R 3访完左子树，访3右子树，栈顶改为3R，7L入栈； 空栈 top 7无左子树，访7右子树，栈顶改为7R 7无右子树，7R出栈 3访完右子树，3R出栈 1访完右子树，1R出栈

46 作业 struct BTNode { Type data; BTNode *leftChild; BTNode *rightChild;
}; 先序遍历非递归伪代码： preWalk(BTNode *T) { …… } 后序遍历非递归伪代码： postWalk(BTNode *T) {

47 二叉树遍历的非递归算法 利用队列的层次序遍历 根入队列 若队列不空，出队列v，v的左右孩子入队列
1 2 4 5 3 6 7 利用队列的层次序遍历 根入队列 若队列不空，出队列v，v的左右孩子入队列 1入队列 1出队列，其左右孩子2和3入队列 1 2 3 4 5 6 7 2出队列，其左右孩子4和5入队列 3出队列，其左右孩子6和7入队列 4出队列，其无孩子 5出队列，其无孩子 6出队列，其无孩子 7出队列，其无孩子 出队列顺序，即按层次遍历顺序为：

48 二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树 EKCG A B H DF HBDF EKCG A EKCG A B H
前序序列：A B H F D E C K G 中序序列：H B D F A E K C G EKCG A B H DF HBDF EKCG A EKCG A B H DF 扫描A 扫描B 扫描H

49 二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树 D EKCG A B H F D EKCG A B H F D E A B
前序序列：A B H F D E C K G 中序序列：H B D F A E K C G D EKCG A B H F D EKCG A B H F D E A B H F KCG 扫描F 扫描D 扫描E

50 二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树 D E A B H F C K G D E A B H F C K G D
前序序列：A B H F D E C K G 中序序列：H B D F A E K C G D E A B H F C K G D E A B H F C K G D E A B H F C K G 扫描C 扫描K 扫描G

51 二叉树的计数 由二叉树的后序序列和中序序列可唯一地确定一棵二叉树? 后序序列：H D F B K G C E A
中序序列：H B D F A E K C G 作业：画出这棵二叉树

52 二叉树的计数 前序序列固定不变，给出不同中序序列，可得不同二叉树 共可构造多少种不同的二叉树？ 1 1 2 6 2 6 3 4 7 3 7
前序序列： 1 1 2 6 2 6 3 4 7 3 7 8 5 8 9 4 5 9

53 二叉树的计数 例如，前序序列 {1, 2, 3}，可构造5种不同的二叉树，其中序序列分别为123，132，213，231，321 1 2 3

54 二叉树的计数 bn表示有n个结点的不同二叉树棵数 bi bn-i-1 1 bn等于Catalan函数： 例如：

55 树与二叉树的转换 将一般树化为二叉树就是用树的子女-兄弟表示来存储树的结构 森林与二叉树的转换可以借助树的二叉树表示来实现。

56 树与二叉树的转换 森林F转换二叉树B 树T转换成二叉树B 若F为空，则B也为空 若F不空，则 若T为空，则B也为空
B的左子树为B(T11, T12, …, T1m )，其中，T11,T12,…,T1m是T1的根的子树； B的右子树为B(T2, T3, …, Tn )，其中，T2,T3,…,Tn是除T1外其它树构成的森林。 树T转换成二叉树B 若T为空，则B也为空 若T不为空，则B的根是T的根；B的左子树是由T的根的子树构成的森林转换而来

57 树与二叉树的转换 T1 T2 T3 A B C D E F G H I J K A B C E D H I K J G F T1 T2 T3