双向链表习题.ppt

1、,/*8-16设链表上的结点的数据结构为： struct node int data； node *left，*right； ； 构造一棵二叉树，结点上的指针left和right分别指向该结点的左子树和右子树。 要求对任一结点，其左子树的所有结点上的数据data值均小于该结点的data值； 其右子树的所有结点上的数据data值均大于该结点的data值。 设输入的结点数据为：24 36 12 8 13 25 77构造一棵满足条件的二叉树。 */,双向链表方法,struct node int data; node * left; node * right; ;,void main() node *

2、head,*tail; Create_sort( ,void Create_sort(node *head,node *tail) int a; node *p1; *head=*tail=0; couta; while(a!=-1) p1=new node; p1-data=a; insert(head,tail,p1); cina; ,插入算法要解决的几种情况,空链表，插入结点，作为链表的第1个结点； 在头结点的右侧; 在头结点的左侧; p2居左，p1居右，找到插入点; 插入尾部结点的左边，即批p2左边。,插入算法要解决的几种情况,空链表，插入结点，作为链表的第1个结点； 在头结点的右侧;

3、 在头结点的左侧; p2居左，p1居右，找到插入点; 插入尾部结点的左边，即批p2左边。,void insert(node *head,node *tail,node *p) node *p1,*p2; if(*head=0) /空链表，插入链表，作为第1个结点 *head=*tail=p; p-left=0;p-right=0; return; ,必须有的语句。,插入算法要解决的几种情况,空链表，插入结点，作为链表的第1个结点； 在头结点的右侧; 在头结点的左侧; p2居左，p1居右，找到插入点; 插入尾部结点的左边，即批p2左边。,void insert(node *head,node *

4、tail,node *p) node *p1,*p2; . if(*head)-datadata) /在头结点的右侧 p-left=*head;(*head)-right=p; p-right=0;*head=p; return ; ,必须有的语句。,插入算法要解决的几种情况,空链表，插入结点，作为链表的第1个结点； 在头结点的右侧; 在头结点的左侧; p2居左，p1居右，找到插入点; 插入尾部结点的左边，即批p2左边。,void insert(node *head,node *tail,node *p) node *p1,*p2; . p1=p2=*head; while(p2-left /

5、p2居左，p1居右， ,搜索到的插入点位置有两种可能:,在头结点的左侧; p2居左，p1居右，找到插入点; 插入尾部结点的左边，即批p2左边,while(p2-left p2居左，p1居右，找到插入点; 插入尾部结点的左边，即批p2左边,if(p2-datadata) /插入p1,p2 中间 p1-left=p;p-right=p1; p-left=p2;p2-right=p; else p-right=p2;p2-left=p; /插入p2左边，即尾部 *tail=p;p-left=0; ,打印输出,void main() node *head,*tail; Create_sort( ,void Print(node *head, int flag) const node *p; p=head; if(flag=