输入一棵二叉搜索树,现在要将该二叉搜索树转换成一个排序的双向链表。
一、问题描述
创新互联公司作为成都网站建设公司,专注成都网站建设、网站设计,有关企业网站设计方案、改版、费用等问题,行业涉及咖啡厅设计等多个领域,已为上千家企业服务,得到了客户的尊重与认可。
输入一棵二叉搜索树,现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中,不能创建任何新的结点,只能调整树中的结点指针的指向来实现。
二、实现思路
在二叉搜索树中,每个结点都有两个分别指向其左、右子树的指针,左子树结点的值总是小于父结点的值,右子树结点的值总是大于父结点的值。而在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。所以这两种数据结构的结点是一致,二叉搜索树之所以为二叉搜索树,双向链表之所以为双向链表,只是因为两个指针的指向不同而已
思路:在转换成排序双向链表时,原先指向左子结点的指针调整为链表中指向前一个结点的指针,原先指向右子结点的指针调整为链表中指向下一个结点的指针。对于树的操作,通常是在遍历树的各个结点的过程中,通过对结点实施某些操作来完成的,这个算法也不例外。由于要求转换后的双向链表也是有序的,而我们从上面也可以看到,当我们以中序遍历二叉搜索树时,其遍历的结点就是有序的,所以在这里采用的遍历顺序应该是中序。
//递归 #include#include using namespace std; struct BinaryTreeNode { int data; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int x) :data(x) , left(NULL) , right(NULL) {} }; class BinaryTree { protected: BinaryTreeNode* _root; BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size) { BinaryTreeNode* root = NULL; if (index < size&&arr[index] != '#') { root = new BinaryTreeNode(arr[index]); root->left = _CreateBinaryTree(arr, ++index, size); root->right = _CreateBinaryTree(arr, ++index, size); } return root; } void _Clear(BinaryTreeNode* root) { if (root == NULL) return; _Clear(root->left); _Clear(root->right); delete root; } void _Convert(BinaryTreeNode* root, BinaryTreeNode** head)//有可能改变head,加引用 { if (root == NULL) return; BinaryTreeNode* cur = root; if (cur->left) _Convert(root->left, head); cur->left = *head; if (*head) (*head)->right = cur; *head = cur; if (cur->right) _Convert(cur->right, head); } //打印并销毁双向链表 private: static void PrintList(BinaryTreeNode* head) { if (head == NULL) return; BinaryTreeNode* cur = head; while (cur) { cout << cur->data << " "; if (cur->left) cout << "prev" << cur->left->data << " "; if (cur->right) cout << "next" << cur->right->data << endl; cur = cur->right; } } static void Destroy(BinaryTreeNode** head) { BinaryTreeNode* cur = *head; BinaryTreeNode* del = NULL; while (cur) { del = cur; cur = cur->right; delete del; } head = NULL; } public: BinaryTree() :_root(NULL) {} ~BinaryTree() { _Clear(_root); } BinaryTree(int *arr, int size) { int index = 0; _root = _CreateBinaryTree(arr, index, size); } void PreOrder_Non() { if (_root == NULL) return; BinaryTreeNode* cur = _root; stack s; s.push(_root); while (!s.empty()) { cur = s.top(); printf("%d ", cur->data); s.pop(); if (cur->right) s.push(cur->right); if (cur->left) s.push(cur->left); } } BinaryTreeNode* TransformList() { if (_root == NULL) return NULL;//返回匿名对象 //应按后序遍历顺序 BinaryTreeNode* ret = NULL; _Convert(_root, &ret); while (ret != NULL&&ret->left != NULL) ret = ret->left; _root = NULL; PrintList(ret); Destroy(&ret); } }; void Test1() { int arr[] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, 12, '#', '#', 16 }; BinaryTree bt1(arr, sizeof(arr) / sizeof(arr[0])); bt1.PreOrder_Non(); BinaryTreeNode* head = bt1.TransformList(); } //非递归 TreeNode * transfer(TreeNode * root) { // left will be used as previous pointer (point to a little one); // right will be used as post pointer (point to a large one); if (!root) return NULL; Stack *s = new Stack(); TreeNode *curr, *head, *tail; curr = root; head = NULL, tail=NULL; while(true) { while(curr) { s->push(curr); curr = curr->left; } if(s->isEmpty()) break; curr = s->pop(); //visit(curr); //将curr节点加入到双向链表末尾 if ( head==NULL) { //curr是链表中的第一个节点。 head = curr; tail = curr; } else { tail->right = curr; curr->left = tail; tail = curr; //注意此处不能够修改tail->right指针的值,到目前为止, //当前节点的右子树还未被访问。 } while(!curr->right) { if(s->isEmpty()) break; curr = s->pop(); //visit(curr); // if ( head==NULL) { head = curr; tail = curr; } else { tail->right = curr; curr->left = tail; tail = curr; } } if (curr->right) curr = curr->right; else break; } head->left = NULL; tail->right = NULL; delete s; return head; }
我们有一个变量head用来记录转换了的链表末结点,由于在惯例中,我们会返回链表的第1个结点(从1开始计数)的指针,而head指向的却是末结点,我们可以通过该指针来从尾走到头来获取第一个结点的指针,但是在这里我却没有这样做,因为它需要对每个结点都遍历一次,时间复杂度为O(n)。而是在变换前,找到二叉排序树的最左结点的指针。因为排序二叉树是有序的,最左的结点即为最小的结点,而我们的算法也不会删除或新增结点,也就是说结点的地址是不会改变的,所以最左的结点就是转换后的链表的第1个结点,其时间复杂度为O(logN)。
该算法首先从根要点一直向左走,找到最左边的结点,其时间复杂度为O(logN),然后对二叉排序树中的每个结点遍历一次,进行指针变换,其时间复杂度为O(N),所以总的时间复杂度为O(N)。
至于空间复杂度,由于ConvertNode函数进行递归调用,其函数有两个开参,而函数栈中的函数调用层数不会超过树高,所以其空间复杂度为O(logN)。
当前文章:输入一棵二叉搜索树,现在要将该二叉搜索树转换成一个排序的双向链表。
网页网址:http://scyanting.com/article/pgijsd.html