第六章树和二叉树 树的概念和基本术语 二叉树 二叉树遍历 二叉树的计数 树与森林 霍夫曼树
第六章 树和二叉树 ▪ 树的概念和基本术语 ▪ 二叉树 ▪ 二叉树遍历 ▪ 二叉树的计数 ▪ 树与森林 ▪ 霍夫曼树
树的概念和基本术语 树的定义 树是由n(n≥0)个结点的有限集合。如 果n=0,称为空树;如果n>0,则 有且仅有一个特定的称之为根(R00的结 点,它只有直接后继,但没有直接前驱; 当n>1,除根以外的其它结点划分为m (m>0)个互不相交的有限集T1,T2,,T 其中每个集合本身又是一棵树,并且称为 根的子树( SubTree
树的概念和基本术语 树的定义 树是由 n (n 0) 个结点的有限集合。如 果 n = 0，称为空树；如果n > 0，则 ▪ 有且仅有一个特定的称之为根(Root)的结 点，它只有直接后继，但没有直接前驱； ▪ 当n > 1，除根以外的其它结点划分为m (m >0) 个互不相交的有限集 T1 , T2 ,…, Tm， 其中每个集合本身又是一棵树，并且称为 根的子树(SubTree)
例如 A A B 只有根结点的树 80 有13个结点的树 其中:A是根;其余结点分成三个互不相交的子集, T1={B,E,F,K,}:T2={C,G}:T3={D,H,L,J,M}, T1,T2,T3都是根A的子树,且本身也是一棵树
A C G B D E F K L H M I J 例如 A 只有根结点的树 有13个结点的树 其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树
树的基本术语 A 1层 B C 2层 height 00-3层 K(L 4层 结点 结点的度*子女*祖先树的深度 叶结点双亲*子孙*树的度 分支结点*兄弟*结点层次*森林
树的基本术语 1层 2层 4层 3层 height = 4 A C G B D E F K L H M I J 结点 结点的度 叶结点 分支结点 子女 双亲 兄弟 祖先 子孙 结点层次 树的深度 树的度 森林
二叉树( Binary Tree) 定义一棵二叉树是结点的一个有限集合, 该集合或者为空,或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 特点每个结点至多只有两棵子树(二叉树中 不存在度大于2的结点) 五种形态 R LR
二叉树 (Binary Tree) 定义 五种形态 一棵二叉树是结点的一个有限集合， 该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 L R L R 特点 每个结点至多只有两棵子树（二叉树中 不存在度大于2的结点）