二进制查找树转换为双向链表
2023-09-11 14:14:10 时间
全然依照海涛哥剑指offer里边的递归思路来写的。基本一样。仅作学习验证。努力锻炼。努力学习!
题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建不论什么新的结点,仅仅调整指针的指向。
比方将二元查找树
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
code例如以下:
//Change a BSTree to a sorted double linklist struct BSTreeNode { int value; BSTreeNode *left; BSTreeNode *right; }head; //Create a node of BSTree for test BSTreeNode* CreateNode(int value) { BSTreeNode *node = new BSTreeNode(); node->value = value; node->left = NULL; node->right = NULL; return node; } //using a lastNode pointer to convert the pointer of the node void ConvertNode(BSTreeNode *head, BSTreeNode **lastNode) { if(head == NULL) return; BSTreeNode *pCurrent = head; if(pCurrent->left != NULL) ConvertNode(pCurrent->left, lastNode); pCurrent->left = *lastNode; if(*lastNode != NULL) (*lastNode)->right = pCurrent; *lastNode = pCurrent; if(pCurrent->right != NULL) ConvertNode(pCurrent->right, lastNode); } //lastNode pointer is pointing to the rear,so the head can be obtained BSTreeNode* Convert(BSTreeNode *head) { if(head == NULL) return NULL; BSTreeNode *lastNode = NULL; ConvertNode(head, &lastNode); while(lastNode->left != NULL) lastNode = lastNode->left; return lastNode; } //main function for test int main() { BSTreeNode *head = CreateNode(10); head->left = CreateNode(8); head->left->left = CreateNode(7); head->left->right = CreateNode(9); head->right = CreateNode(12); head->right->left = CreateNode(11); head = Convert(head); while(head != NULL) { printf("%d ",head->value); head = head->right; } }
相关文章
- 使用FFmpeg工具进行推流、拉流、截图、变速、转换,及常见问题处理
- 单位转换 inch mm mil
- C# MVC 用户登录状态判断 【C#】list 去重(转载) js 日期格式转换(转载) C#日期转换(转载) Nullable<System.DateTime>日期格式转换 (转载) Asp.Net MVC中Action跳转(转载)
- Python中string、json、bytes的相互转换
- 图片视角转换 cv2.warpPerspective
- Bitmap与IplImage之间的转换
- Swift3.0语言教程字符串与文件的数据转换
- openvino使用(一)转换并量化(INT8)分类网络模型
- 转 javascript 本地时间 和utc 节点 和 时间戳转换 的
- c# Bitmap byte[] Stream 文件相互转换
- html-rem与px的转换
- List数组转换JSON格式