心孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储结构,链表中每个结点的两个 指针域分别指向其第一个孩子结点和下一个兄弟结点 0特点 typedef struct node ◆操作容易 i datatype data ◆破坏了树的层次 struct node *fch. *nsib a d((((((e def g g h ∧
❖孩子兄弟表示法（二叉树表示法） ⚫实现：用二叉链表作树的存储结构，链表中每个结点的两个 指针域分别指向其第一个孩子结点和下一个兄弟结点 ⚫特点 ◆操作容易 ◆破坏了树的层次 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 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
★二叉树的存储结构 今顺序存储结构 ●实现:按满二叉树的结点层次编号,依次存放二叉树中的数 据元素 ●特点: ◆结点间关系蕴含在其存储位置中 ◆浪费空间,适于存满二叉树和完全二叉树 123456 a b o fg 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
◆链式存储结构 0二叉链表 typedef struct node i datatype data Child data rchild struct node *lchild. *rchild JJD A B D F E FA G GA 在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 ^ ^ ^ ^ ^ ^ ^ ^
0三叉链表 typedef struct node i datatype data; Child data parent rchild struct node*Child,*rchild, *parent A B B F C D G ELFI G
⚫三叉链表 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 BCE 存(B B D C 释 D假 解 AE A A B B C E C D D E
树与二叉树转换 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 ^ 对应