.把二元查找树转变成排序的双向链表

参考地址为

  

   

    

     

    
    

     

      //* Copyright(C) 2011 
     
    
   

    

     

    
    

     

      //*
     
    
   

    

     

    
    

     

      //* FUNCTION : TreeToLink
     
    
   

    

     

    
    

     

      //* DESCRIPTION : Tree to link
     
    
   

    

     

    
    

     

      //* PARAMETERS : Type Name Description
     
    
   

    

     

    
    

     

      //* RETURN : Type Values Description
     
    
   

    

     

    
    

     

      //* CREATED DATE/BY : 2011/11/30 perfect2011
     
    
   

    

     

    
    

     

      //*
     
    
   

    

     

    
    

     

      //* REVISION HISTORY:V1.0
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

      1.把二元查找树转变成排序的双向链表
     
    
   

    

     

    
    

     

      题目：
     
    
   

    

     

    
    

     

      输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
     
    
   

    

     

    
    

     

      要求不能创建任何新的结点，只调整指针的指向。
     
    
   

    

     

    
    

     

       
     
    
   

    

     

    
    

     

       10
     
    
   

    

     

    
    

     

       / /
     
    
   

    

     

    
    

     

       6 14
     
    
   

    

     

    
    

     

      / / / /
     
    
   

    

     

    
    

     

      4 8 12 16
     
    
   

    

     

    
    

     

       
     
    
   

    

     

    
    

     

      转换成双向链表
     
    
   

    

     

    
    

     

      4=6=8=10=12=14=16。
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #include "stdafx.h"
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct TreeNode
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int m_nValue; // value of node
     
    
   

    

     

    
    

     

       TreeNode *m_pLeft; // left child of node
     
    
   

    

     

    
    

     

       TreeNode *m_pRight; // right child of node
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef TreeNode DoubleList;
     
    
   

    

     

    
    

     

      DoubleList * pHead;
     
    
   

    

     

    
    

     

      DoubleList * pListIndex;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //生成查找树
     
    
   

    

     

    
    

     

      void adjust(TreeNode * & pCurrent, int value)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//根节点的处理，生成根节点,为pCurrent赋值 重点理解：注意为传址，修改了main内的pRoot
     
    
   

    

     

    
    

     
	if(NULL == pCurrent)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      	TreeNode *pEnd = new TreeNode();
     
    
   

    

     

    
    

     

      	pEnd ->m_pLeft =NULL;
     
    
   

    

     

    
    

     

      	pEnd ->m_pRight = NULL;
     
    
   

    

     

    
    

     

      	pEnd ->m_nValue = value;
     
    
   

    

     

    
    

     

      	pCurrent = pEnd;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//
     
    
   

    

     

    
    

     
	else
     
    
   

    

     

    
    

     

      	{   //在左子树添加
     
    
   

    

     

    
    

     
		if (value<pCurrent->m_nValue)
     
    
   

    

     

    
    

     

      		{  
     
    
   

    

     

    
    

     

      			adjust(pCurrent->m_pLeft,value);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//在右子树添加
     
    
   

    

     

    
    

     
		else if(value>pCurrent->m_nValue)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			adjust(pCurrent->m_pRight,value);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
		cout<<" 重 复 的 节 点 "<<endl;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void addList(TreeNode *pCurrent);
     
    
   

    

     

    
    

     

      //covert the tree to link
     
    
   

    

     

    
    

     

      void covertTreeToLink(TreeNode *pCurrent)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//中序读出
     
    
   

    

     

    
    

     
	if(pCurrent==NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
	return;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	//遍历左子树
     
    
   

    

     

    
    

     
	if(NULL != pCurrent->m_pLeft)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      	covertTreeToLink(pCurrent->m_pLeft);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	//将根节点加进链表
     
    
   

    

     

    
    

     

      	addList(pCurrent);
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	//遍历右子树
     
    
   

    

     

    
    

     
	if(NULL != pCurrent->m_pRight)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

      		covertTreeToLink(pCurrent->m_pRight);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //添加节点到链表
     
    
   

    

     

    
    

     

      void addList(TreeNode *pCurrent)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if(NULL ==pListIndex)
     
    
   

    

     

    
    

     

      	pHead = pListIndex;
     
    
   

    

     

    
    

     

      else
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      pCurrent->m_pLeft = pListIndex;
     
    
   

    

     

    
    

     

      pListIndex ->m_pRight = pCurrent;
     
    
   

    

     

    
    

     

      pListIndex = pCurrent;//指针后移
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      cout<<"Now "<<pCurrent->m_nValue<<endl;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {   TreeNode * pRoot = NULL;
     
    
   

    

     

    
    

     

       pListIndex = NULL;//链表的移动指针
     
    
   

    

     

    
    

     

       pHead = NULL;//链表的头指针
     
    
   

    

     

    
    

     

      	adjust(pRoot, 10);
     
    
   

    

     

    
    

     

       adjust(pRoot, 4);
     
    
   

    

     

    
    

     

       adjust(pRoot, 6);
     
    
   

    

     

    
    

     

       adjust(pRoot, 8);
     
    
   

    

     

    
    

     

       adjust(pRoot, 12);
     
    
   

    

     

    
    

     

       adjust(pRoot, 14);
     
    
   

    

     

    
    

     

       adjust(pRoot, 15);
     
    
   

    

     

    
    

     

       adjust(pRoot, 16);
     
    
   

    

     

    
    

     

       covertTreeToLink(pRoot);
     
    
   

    

     

    
    

     

       getchar();
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: gamwatcher.blog.csdn.net，作者：香菜聊游戏，版权归原作者所有，如需转载，请联系作者。

原文链接：gamwatcher.blog.csdn.net/article/details/7026968