1.把二元查找树转变成排序的双向链表（树）
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ /
6 14
/ / / /
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ /
6 14
/ / / /
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
我的解答：
# include <iostream > # include <string > # include <vector > # include <bitset > # include <string > # include <sstream > using namespace std; struct BSTreeNode{ int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; void addBSTreeNode(BSTreeNode * &T, int node){ //注意：由于要给T这个指针赋值(T = new BSTreeNode()),故此处必须用引用！ if(T){ if(T - >m_nValue > node){ //添加到左子树 addBSTreeNode(T - >m_pLeft, node); } else if(T - >m_nValue < node){ //添加到右子树 addBSTreeNode(T - >m_pRight, node); } else{ cout << "加入重复节点" <<endl; } } else{ T = new BSTreeNode(); //添加节点 T - >m_nValue = node; T - >m_pLeft = NULL; T - >m_pRight = NULL; } } BSTreeNode *lastNode = NULL; //储存链表中的上一个节点 BSTreeNode *startNode = NULL; //存双向链表的头节点 void midOrderTraverse(BSTreeNode *T){ if(T){ midOrderTraverse(T - >m_pLeft); //访问左子树 T - >m_pLeft =lastNode; //当前节点的m_pLeft指向上一节点 if(lastNode){ lastNode - >m_pRight = T; //上一个节点的m_pRight指向当前节点 } else{ startNode = T; //上一个节点为空,则该节点为头结点 } lastNode = T; //当前节点变为上一节点 midOrderTraverse(T - >m_pRight); //访问右子树 } } int main(){ BSTreeNode *pRoot =NULL; //初始化二叉搜索树 addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 4); addBSTreeNode(pRoot, 6); addBSTreeNode(pRoot, 8); addBSTreeNode(pRoot, 12); addBSTreeNode(pRoot, 14); addBSTreeNode(pRoot, 15); addBSTreeNode(pRoot, 16); //中序遍历变为双向链表 midOrderTraverse(pRoot); //打印输出 while(startNode){ cout <<startNode - >m_nValue <<endl; startNode = startNode - >m_pRight; } return 0; }
心得：
1、注意形参中引用的作用，如在addBSTreeNode函数中行参T加上&,才能是给T赋值有效！
2、二叉树的遍历：采用递归，流程如下
Traverse(BiTree *T){ if(T){ //T不为空 PreOrderVisitDate(T - >Data) //先序遍历 Traverse(T - >leftChild) //访问左子树 MidOrderVisitDate(T - >Data) //中序遍历 Traverse(T - >rightChild) //访问右子树 postOrdrtVisitDate(T - >Data) //后序遍历 } }