freedomfanye 2020-04-19
==================================链表==================================
1. 找一个链表中倒数第k个结点(假设原链表肯定有多余k个结点)
假设整个链表有x个结点,用两个指针即可找到倒数第k个,示意图如下:
先用一个指针a遍历到第k个 ;然后a、b指针同时开始往后,直到指针a结束,则b在这段时间里走过了x-k个结点,也就是倒数第k个结点
typedef struct { int data; Node *next; }Node; Node *findKthToTail(Node *head,int k) { //假设链表不为空,且有多于k个结点 Node *fast = head; Node *slow = head; for(int i=0;i<k;i++) { if(fast == NULL) { return NULL; } fast = fast->next; } while(fast != NULL) { fast = fast->next; slow = slow->next; } return slow; }
2. 单链表排序
3. 两个单链表求交、并、差
4. 单链表反转
Node是结点结构体类型:有数据域elemType data和指针域Node *next 第一个结点就是有效结点 Node *head = initSingleList(); //.....加入了很多新元素进去 reverseSingleList(&head); //或head = reverseSingleList(&head); Node *reverseSingleList(Node **head) { if(NULL == *head || NULL == (*head)->next) { return *head; } Node *a = *head; Node *b = a->next; Node *c = NULL; (*head)->next = NULL; while(NULL != b) { c = b->next; b->next = a; a = b; b = c; } *head = a; return a; }
==================================二叉树==================================
1. 结点数量相关问题
(1)不同度结点的关系
(2)计算结点总数
https://www.cnblogs.com/taoXiang/p/12324454.html
(3)树深度
https://www.cnblogs.com/taoXiang/p/12324454.html
2. 二叉树形状推导
(1)已知前序遍历和中序遍历
前序:ABDHIEJKCFLMGNO
中序:HDIBJEKALFMCNGO
还原:
分块,区分哪一块是左边的、哪一块是右边的:
【A B DHI EJK C FLM GNO】
【HDI B JEK A LFM C NGO】
①根据前序,A是最上面的结点,根据中序,则【HDI B JEK】为A左侧结点,【LFM C NGO】为A右侧结点
②分析A左侧这部分,右侧类似
分析【B DHI EJK】【HDI B JEK】,B是根,【DHI】为B左侧结点,【JEK】为B右侧结点
分析【C FLM GNO】【LFM C NGO】,C是根,【FLM】为C左侧,【GNO】为C的右侧结点
③
分析【DHI】【HDI】,D是根,H为D左侧点,I为D右侧点
分析【EJK】【JEK】,E为根,J为E左侧点,K为E右侧点
分析【FLM】【LFM】,F为根,L为F左侧点,M为F右侧点
分析【GNO】【NGO】,G为根,N为G左侧点,O为G右侧点
(2)已知后序遍历和中序遍历
后序:HIDJKEBLMFNOGCA
中序:HDIBJEKALFMCNGO
(3)已知后序遍历和前序遍历
无法推断