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

参考地址为

      //* 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