★53二叉树的存储结构 今顺序存储结构 实现:按满二叉树的结点层次编号,依次存放二叉树中的数 据元素 ●特点: ◆结点间关系蕴含在其存储位置中 ◆浪费空间,适于存满二叉树和完全二叉树 123456 a b o fg g
5.3 二叉树的存储结构 ❖顺序存储结构 ⚫实现：按满二叉树的结点层次编号，依次存放二叉树中的数 据元素 ⚫特点： ◆结点间关系蕴含在其存储位置中 ◆浪费空间，适于存满二叉树和完全二叉树 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 3 Bnode, *Btree A B D F E FA G GA 在n个结点的二叉链表中,有n+1个空指针域
❖链式存储结构 ⚫二叉链表 typedef struct node { datatype data; struct node *lchild, *rchild; } Bnode,*Btree; lchild data rchild A B C D E F G 在n个结点的二叉链表中，有n+1个空指针域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^
三叉链表 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 ^ ^ ^ ^ ^ ^ ^ ^ ^ 三叉链表
二叉链表的生成 方法: 1输入根结点;2若左子树不空,输入左子树;3若右子树不空,输入右子树 Btree createbtree( Btree bt, int k) i datatype b Btree t; Bnode"p printf( Please input node b: ) Scanf(%,, &b) if(b!=0){ p=( Bnode )malloc(sizeof( Bnode)), p->data= p->lchild=NULL; p->rchild=NULL switch(k)f case 0: t=p; break case 1: bt->lchild=p; break case2: bt->rchild=p; break; createbtree(p, 1); createtree(p, 2); return(t);
二叉链表的生成 方法: 1 输入根结点; 2 若左子树不空，输入左子树; 3 若右子树不空，输入右子树 Btree createbtree(Btree bt,int k) {datatype b; Btree t; Bnode *p; printf(“Please input node b: ”); scanf (“%d” , &b); if (b!=0){ p=(Bnode*)malloc(sizeof(Bnode));p->data=b; p->lchild=NULL;p->rchild=NULL; switch(k){ case 0: t=p;break; case 1: bt->lchild=p;break; case2: bt->rchild=p;break;} createbtree(p,1);createtree(p,2); } return(t);}
§54树和二又树的遍历 ★树的遍历 ◆遍历——按一定规律走遍树的各个顶点,且使每一顶点 仅被访问一次,即找一个完整而有规律的走法,以得到 树中所有结点的一个线性排列 今常用方法 ●先根(序)遍历:先访问树的根结点,然后依次先根遍历根的 每棵子树 ●后根(序)遍历:先依次后根遍历每棵子树,然后访问根结点 ●按层次遍历:先访问第一层上的结点.然后依次遍历第二 层 第层的结点
§5.4 树和二叉树的遍历 树的遍历 ❖遍历——按一定规律走遍树的各个顶点，且使每一顶点 仅被访问一次，即找一个完整而有规律的走法，以得到 树中所有结点的一个线性排列 ❖常用方法 ⚫先根（序）遍历：先访问树的根结点，然后依次先根遍历根的 每棵子树 ⚫后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 ⚫按层次遍历：先访问第一层上的结点，然后依次遍历第二 层，……第n层的结点