程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 二元查找樹轉有序雙向鏈表

二元查找樹轉有序雙向鏈表

編輯:C++入門知識

[cpp] view plaincopyprint?// 二元查找樹轉有序的雙向鏈表.cpp : Defines the entry point for the console application.  
//  
//題目:把二元查找樹轉變成排序的雙向鏈表  
//要求:輸入一棵二元查找樹,將該二元查找樹轉換成一個排序的雙向鏈表。  
//要求不能創建任何新的結點,只調整指針的指向。  
/* 將下面這個二元查找樹轉化成
            10
            / \
           6   14
          /\   /\
         4  8 12 16
         
    4=6=8=10=12=14=16 這個雙向鏈表     
         
*/ 
 
/*
什麼是二元查找樹?
二元查找樹: 它首先要是一棵二元樹,在這基礎上它或者是一棵空樹;
或者是具有下列性質的二元樹: 
(1)若左子樹不空,則左子樹上所有結點的值均小於它的根結點的值; 
(2)若右子樹不空,則右子樹上所有結點的值均大於它的根結點的值; 
(3)左、右子樹也分別為二元查找樹
如何構造一個二元查找樹?
和一般二叉樹構造方式類似,只是需要滿足上述條件
元素插入時利用遞歸,找到合適的插入位置
定義樹節點結構
struct BSTreeNode
{
    int value;
    BTreeNode *left;
    BTreeNode *right;
}
思路:通過觀察可以發現,二元查找樹的中序遍歷結果就是一個有序的數列,
這樣只需要對樹進行一次中序遍歷,同時調整指針成為一個雙向鏈表即可
*/ 
#include "stdafx.h"  
#include <iostream>  
using namespace std; 
struct BSTreeNode 

    int value; 
    BSTreeNode *left; 
    BSTreeNode *right; 
}; 
BSTreeNode *pHead=NULL; //指向雙向鏈表頭結點  
BSTreeNode *pIndex=NULL;//保存當前訪問節點的前一個節點  
//比如當前訪問節點6,那麼pIndex指向的是4  
void AddBSTreeNode(BSTreeNode **pRoot,int value) 

    if(NULL==*pRoot) 
    { 
        BSTreeNode *tmpNode=new BSTreeNode; 
        tmpNode->value=value; 
        tmpNode->left=NULL; 
        tmpNode->right=NULL; 
        *pRoot=tmpNode; 
    } 
    else if((*pRoot)->value<value) 
    { 
        AddBSTreeNode(&(*pRoot)->right,value); 
    } 
    else if((*pRoot)->value>value) 
    { 
        AddBSTreeNode(&(*pRoot)->left,value); 
    } 

//中序遍歷,同時調整節點指針  
void InOrderAdjust(BSTreeNode* pBSTree) 

    if(NULL==pBSTree) 
        return; 
    //遞歸訪問左子  
    if(NULL!=pBSTree->left) 
        InOrderAdjust(pBSTree->left); 
    //調整節點指針  
     
    pBSTree->left=pIndex;//將當前訪問節點的左指針指向前一個節點  
    if(NULL==pIndex)//如果前一個節點是空,說明是第一次訪問  
        pHead=pBSTree;//此時的節點應作為雙向鏈表的表頭節點  
    else 
        pIndex->right=pBSTree;//將前一個節點右指針指向當前節點,這樣便構成了一個雙向鏈表  
    pIndex=pBSTree; 
    //遞歸訪問右子  
    if(NULL!=pBSTree->right) 
        InOrderAdjust(pBSTree->right); 

//輸出結果驗證  
void Print(BSTreeNode *pHead) 

    if(pHead==NULL) 
        return; 
    BSTreeNode *pTmp; 
    cout<<"順序遍歷:"<<endl; 
    while(pHead!=NULL) 
    { 
        pTmp=pHead; 
        cout<<pHead->value<<" "; 
        pHead=pHead->right; 
    } 
    cout<<endl; 
    cout<<"逆序遍歷:"<<endl; 
    while(pTmp!=NULL) 
    { 
        cout<<pTmp->value<<" "; 
        pTmp=pTmp->left; 
    } 
    cout<<endl; 

int _tmain(int argc, _TCHAR* argv[]) 

    BSTreeNode *pRoot=NULL; 
    AddBSTreeNode(&pRoot,10); 
    AddBSTreeNode(&pRoot,6); 
    AddBSTreeNode(&pRoot,14); 
    AddBSTreeNode(&pRoot,4); 
    AddBSTreeNode(&pRoot,8); 
    AddBSTreeNode(&pRoot,12); 
    AddBSTreeNode(&pRoot,16); 
    InOrderAdjust(pRoot); 
    Print(pHead); 
    system("pause"); 
    return 0; 

// 二元查找樹轉有序的雙向鏈表.cpp : Defines the entry point for the console application.
//
//題目:把二元查找樹轉變成排序的雙向鏈表
//要求:輸入一棵二元查找樹,將該二元查找樹轉換成一個排序的雙向鏈表。
//要求不能創建任何新的結點,只調整指針的指向。
/* 將下面這個二元查找樹轉化成
   10
   / \
     6   14
    /\   /\
   4  8 12 16
  
    4=6=8=10=12=14=16 這個雙向鏈表 
  
*/

/*
什麼是二元查找樹?
二元查找樹: 它首先要是一棵二元樹,在這基礎上它或者是一棵空樹;
或者是具有下列性質的二元樹:
(1)若左子樹不空,則左子樹上所有結點的值均小於它的根結點的值;
(2)若右子樹不空,則右子樹上所有結點的值均大於它的根結點的值;
(3)左、右子樹也分別為二元查找樹
如何構造一個二元查找樹?
和一般二叉樹構造方式類似,只是需要滿足上述條件
元素插入時利用遞歸,找到合適的插入位置
定義樹節點結構
struct BSTreeNode
{
 int value;
 BTreeNode *left;
 BTreeNode *right;
}
思路:通過觀察可以發現,二元查找樹的中序遍歷結果就是一個有序的數列,
這樣只需要對樹進行一次中序遍歷,同時調整指針成為一個雙向鏈表即可
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
struct BSTreeNode
{
 int value;
 BSTreeNode *left;
 BSTreeNode *right;
};
BSTreeNode *pHead=NULL; //指向雙向鏈表頭結點
BSTreeNode *pIndex=NULL;//保存當前訪問節點的前一個節點
//比如當前訪問節點6,那麼pIndex指向的是4
void AddBSTreeNode(BSTreeNode **pRoot,int value)
{
 if(NULL==*pRoot)
 {
  BSTreeNode *tmpNode=new BSTreeNode;
  tmpNode->value=value;
  tmpNode->left=NULL;
  tmpNode->right=NULL;
  *pRoot=tmpNode;
 }
 else if((*pRoot)->value<value)
 {
  AddBSTreeNode(&(*pRoot)->right,value);
 }
 else if((*pRoot)->value>value)
 {
  AddBSTreeNode(&(*pRoot)->left,value);
 }
}
//中序遍歷,同時調整節點指針
void InOrderAdjust(BSTreeNode* pBSTree)
{
 if(NULL==pBSTree)
  return;
 //遞歸訪問左子
 if(NULL!=pBSTree->left)
  InOrderAdjust(pBSTree->left);
 //調整節點指針
 
 pBSTree->left=pIndex;//將當前訪問節點的左指針指向前一個節點
 if(NULL==pIndex)//如果前一個節點是空,說明是第一次訪問
  pHead=pBSTree;//此時的節點應作為雙向鏈表的表頭節點
 else
  pIndex->right=pBSTree;//將前一個節點右指針指向當前節點,這樣便構成了一個雙向鏈表
 pIndex=pBSTree;
 //遞歸訪問右子
 if(NULL!=pBSTree->right)
  InOrderAdjust(pBSTree->right);
}
//輸出結果驗證
void Print(BSTreeNode *pHead)
{
 if(pHead==NULL)
  return;
 BSTreeNode *pTmp;
 cout<<"順序遍歷:"<<endl;
 while(pHead!=NULL)
 {
  pTmp=pHead;
  cout<<pHead->value<<" ";
  pHead=pHead->right;
 }
 cout<<endl;
 cout<<"逆序遍歷:"<<endl;
 while(pTmp!=NULL)
 {
  cout<<pTmp->value<<" ";
  pTmp=pTmp->left;
 }
 cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
 BSTreeNode *pRoot=NULL;
 AddBSTreeNode(&pRoot,10);
 AddBSTreeNode(&pRoot,6);
 AddBSTreeNode(&pRoot,14);
 AddBSTreeNode(&pRoot,4);
 AddBSTreeNode(&pRoot,8);
 AddBSTreeNode(&pRoot,12);
 AddBSTreeNode(&pRoot,16);
 InOrderAdjust(pRoot);
 Print(pHead);
 system("pause");
 return 0;
}
[cpp]  運行結果: 

運行結果:

\

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved