孩子兄弟表示法（二叉树表示法) ●实现：用二叉链表作树的存储结构，链表中每个结点的两个 指针域分别指向其第一个孩子结点和下一个兄弟结点 ●特点 typedef struct node ◆操作容易 datatype data; ◆破坏了树的层次 struct node *fch.*nsib: JD; a a b b d e d 7 g h A g
❖孩子兄弟表示法（二叉树表示法） ⚫实现：用二叉链表作树的存储结构，链表中每个结点的两个 指针域分别指向其第一个孩子结点和下一个兄弟结点 ⚫特点 ◆操作容易 ◆破坏了树的层次 typedef struct node { datatype data; struct node *fch, *nsib; }JD; a b c d e f g h i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
★二叉树的存储结构 冬顺序存储结构 ●实现：按满二又树的结点层次编号，依次存放二叉树中的数 据元素 ●特点： ◆结点间关系蕴含在其存储位置中 ◆浪费空间，适于存满二叉树和完全二叉树 a C 1 234567891011 a b c d e 000 f g g
二叉树的存储结构 ❖顺序存储结构 ⚫实现：按满二叉树的结点层次编号，依次存放二叉树中的数 据元素 ⚫特点： ◆结点间关系蕴含在其存储位置中 ◆浪费空间，适于存满二叉树和完全二叉树 a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11
链式存储结构 ●二叉链表 typedef struct node datatype data; lchild data rchild struct node *lchild,*rchild; JD; 7 A B B F 在n个结点的二叉链表中，有n+1个空指针域
❖链式存储结构 ⚫二叉链表 typedef struct node { datatype data; struct node *lchild, *rchild; }JD; lchild data rchild A B C D E F G 在n个结点的二叉链表中，有n+1个空指针域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^
●三叉链表 typedef struct node datatype data; lchild data parentrchild struct node *lchild,*rchild,*parent; D A B B D E F G E
⚫三叉链表 typedef struct node { datatype data; struct node *lchild, *rchild, *parent; }JD; lchild data parent rchild A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^
★树与二叉树转换 树 对应 二叉树 A A B B E 存储 存储 D D E 解释 解释 A B B D
树与二叉树转换 A B C E D 树 A B C D E 二叉树 A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ 对应