62二叉树 5、如果对一棵有n个结点的完全二叉树,则对任结点有 (1)若i=1,则k是根结点,无双亲;若i>1则k的双亲 编号为int(/2)。 (2)若2i≤n,则k的左孩子的编号是2i;2i>n,则无左 孩子。 (3)若2i+1sn则k右孩子的编号是2+1;2+1>n,则无 右孩子 (4)若i奇数且不为1,则k的左兄弟的编号是ⅰ-1;否 则k无左兄弟。 (5)若i为偶数且小于n,则k的右兄弟的编号是i+1;香 则k无右兄弟
6.2 二叉树 5、如果对一棵有n个结点的完全二叉树，则对任一结点有： （1）若i=1，则ki是根结点，无双亲；若i>1,则ki的双亲 编号为int(i/2)。 （2）若2i≤n，则ki的左孩子的编号是2i；2i>n,则无左 孩子。 （3）若2i+1≤n,则ki右孩子的编号是2i+1;2i+1>n,则无 右孩子。 （4）若i为奇数且不为1，则ki的左兄弟的编号是i-1；否 则ki无左兄弟。 （5）若i为偶数且小于n，则ki的右兄弟的编号是i+1；否 则ki无右兄弟
62二叉树 ●二叉树的存储结构 1)顺序存储结构:对完全二叉树而言,既简单又节省存 储空间,但对非完全二叉树,必须按完全二叉树的形 式来存储树中的结点,这将造成存储空间的浪费。 kO 00c 1234567 AOB000C
6.2 二叉树 ⚫ 二叉树的存储结构 1）顺序存储结构: 对完全二叉树而言，既简单又节省存 储空间，但对非完全二叉树，必须按完全二叉树的形 式来存储树中的结点，这将造成存储空间的浪费。 A 0 B 0 0 0 C 1 2 3 4 5 6 7 A 0 B 0 0 0 C
6.2二叉树 2)链式存储结构 设计不同的结点结构可构成不同的链式存储结构。通 常采用二叉链表的形式,即: Child data rchild typedef struct BinOde f TElem Type data struct binOde *lchild. *rchild 3 * BiTree
6.2 二叉树 2）链式存储结构 设计不同的结点结构可构成不同的链式存储结构。通 常采用二叉链表的形式，即： lchild data rchild typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } *BiTree;
6.2二叉树 叉链表的生成 Status CreateBiTree(BiTree&T) i scanf( &ch); if(ch==")T=NULL else f if (!(t=BinOde *)malloc(sizeof( BiTNode)))) exit(OVERFLOW) T->data=ch Create BiTree(T->lchild) CreateBiTree(T->rchild) return oK
6.2 二叉树 ⚫ 二叉链表的生成 Status CreateBiTree(BiTree &T) { scanf(&ch); if (ch==‘’) T=NULL; else { if (!(T=(BiTNode *) malloc (sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; }
6.2二叉树 F B因c WIDIAJ WEA AFA
6.2 二叉树 A B C D E F T A B ∧ C ∧ D ∧ ∧ E ∧ ∧ F ∧