博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
面试题27:二叉搜索树与双向链表
阅读量:6184 次
发布时间:2019-06-21

本文共 2879 字,大约阅读时间需要 9 分钟。

题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。比如输入下图中左边儿茶搜索树,则输出转换后的排序双向链表。     10    /  \   6    14  / \   / \ 4   8 12 164=6=8=10=12=14=16

 将二叉搜索树转化为有序双向链表,类似于中序遍历,中序遍历的结果就是一个排序的数字。因此在程序中以中序遍历树,当遍历左子树到在叶子结点的时候,开始修改指针。 

代码实例:

View Code
#include
#include
using namespace std;struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};//创建二叉树结点BinaryTreeNode* CreateBinaryTreeNode(int value){ BinaryTreeNode* pNode=new BinaryTreeNode(); pNode->m_nValue=value; pNode->m_pLeft=NULL; pNode->m_pRight=NULL; return pNode;}void ConnectTreeNodes(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight){ if(pParent!=NULL) { pParent->m_pLeft=pLeft; pParent->m_pRight=pRight; }}void InOrderPrintTree(BinaryTreeNode* pRoot)//中序遍历{ if(pRoot!=NULL) { if(pRoot->m_pLeft!=NULL)// InOrderPrintTree(pRoot->m_pLeft); cout<<"value of this node is "<
m_nValue<
m_pRight!=NULL) InOrderPrintTree(pRoot->m_pRight); } else { cout<<"this node is null."<
m_pLeft!=NULL)//遍历左子树 Convert(pCurrent->m_pLeft,pLastNodeInList); pCurrent->m_pLeft=*pLastNodeInList; if((*pLastNodeInList)!=NULL) (*pLastNodeInList)->m_pRight=pCurrent; *pLastNodeInList=pCurrent; //右子树转换 if(pCurrent->m_pRight!=NULL)//遍历右子树 Convert(pCurrent->m_pRight,pLastNodeInList);}BinaryTreeNode* Convert(BinaryTreeNode* pRoot){ BinaryTreeNode* pLastNodeInList=NULL;//指向双向链表的尾结点 Convert(pRoot,&pLastNodeInList);//转换排序二叉树为双向链表 //求双向链表的头结点 BinaryTreeNode* pHeadOfList=pLastNodeInList; while(pHeadOfList!=NULL&&pHeadOfList->m_pLeft!=NULL) pHeadOfList=pHeadOfList->m_pLeft; return pHeadOfList;}//输出双向链表void PrintList(BinaryTreeNode* pRoot){ BinaryTreeNode* pNode = pRoot; while(pNode != NULL) { printf("%d\t", pNode->m_nValue); pNode = pNode->m_pRight; } printf("\nPrintList ends.\n");}void main(){// 10// / \// 6 14// /\ /\// 4 8 12 16 //创建树结点 BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12); BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16); //连接树结点 ConnectTreeNodes(pNode10, pNode6, pNode14); ConnectTreeNodes(pNode6, pNode4, pNode8); ConnectTreeNodes(pNode14, pNode12, pNode16); //PrintTree(pNode10); InOrderPrintTree(pNode10);//中序遍历 BinaryTreeNode* pHeadOfList=Convert(pNode10);//获取双向链表头结点 PrintList(pHeadOfList);//输出链表 system("pause");}

转载地址:http://stsda.baihongyu.com/

你可能感兴趣的文章
《极简JavaScript正则教程》
查看>>
推荐一个非常好用的 MarkDown 编辑器!
查看>>
React Native 调用原生Android、iOS模块实现拨号功能
查看>>
element-ul InputNumber 空白
查看>>
iOS 从0到1搭建高可用App框架(二)
查看>>
java循环小游戏(任意月份日历表)
查看>>
Android Studio NDK :一、基础入门(基于gradle-experimental插件)
查看>>
lc1051. Height Checker
查看>>
菜单的隐藏&显示
查看>>
环信联合创始人: Saas敏捷开发实践!
查看>>
一个完全平均分布的固定长度随机数发生器
查看>>
Graviton:极简的开源代码编辑器
查看>>
4196: [Noi2015]软件包管理器
查看>>
TiKV 源码解析系列文章(八)grpc-rs 的封装与实现
查看>>
MYSQL添加远程用户或允许远程访问三种方法
查看>>
jquery-插件
查看>>
Docker版本(三)
查看>>
NPM 安装速度慢,镜像修改
查看>>
养12的益处—随想请轻拍
查看>>
CSS表单属性
查看>>