青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

那誰的技術(shù)博客

感興趣領(lǐng)域:高性能服務(wù)器編程,存儲(chǔ),算法,Linux內(nèi)核
隨筆 - 210, 文章 - 0, 評(píng)論 - 1183, 引用 - 0
數(shù)據(jù)加載中……

二叉查找樹的解析與實(shí)現(xiàn)

二叉查找樹是二叉樹的一個(gè)特化,它具有的特殊性質(zhì)是:對(duì)于樹中的任何一個(gè)結(jié)點(diǎn),它的左子樹的所有結(jié)點(diǎn)的關(guān)鍵字都小于此結(jié)點(diǎn)的關(guān)鍵字,而右子樹的所有結(jié)點(diǎn)的關(guān)鍵字都大于此結(jié)點(diǎn)的關(guān)鍵字.

二叉查找樹的這種特殊性質(zhì)使得它在查找元素的時(shí)候特別的方便,每一次查找都可以去掉一半的元素,因此查找的時(shí)間是O(logN).

二叉查找樹的插入和查找算法也是很簡(jiǎn)單的,就是與當(dāng)前結(jié)點(diǎn)的關(guān)鍵字作比較決定在右邊還是左邊繼續(xù)操作.

二叉查找樹最復(fù)雜的算法就是刪除結(jié)點(diǎn)的算法了,根據(jù)所要?jiǎng)h除的結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)還是只有一個(gè)或者沒有子結(jié)點(diǎn)會(huì)有不同的處理.有兩個(gè)子結(jié)點(diǎn)的情況一般的處理是找到右子樹中值最小的一個(gè)結(jié)點(diǎn),將它的值替代當(dāng)前的結(jié)點(diǎn)值,然后再把這個(gè)值最小的結(jié)點(diǎn)刪除,也就是說有兩個(gè)子結(jié)點(diǎn)的情況是用最小的一個(gè)大于當(dāng)前結(jié)點(diǎn)關(guān)鍵字的結(jié)點(diǎn)替代了當(dāng)前的結(jié)點(diǎn)(很拗口,但愿我說清楚了:)在只有一個(gè)或者沒有子結(jié)點(diǎn)的情況就比較的簡(jiǎn)單了,如果還有子結(jié)點(diǎn)就把子結(jié)點(diǎn)的位置往上挪,然后把當(dāng)前結(jié)點(diǎn)刪除.

實(shí)現(xiàn)如下:
1)BSTree.h
/********************************************************************
????created:????2006/07/28
????filename:?????BSTree.h
????author:????????李創(chuàng)
????????????????http://m.shnenglu.com/converse/

????purpose:????二叉查找樹的實(shí)現(xiàn)代碼
*********************************************************************/

#ifndef?BINARY_SEARCH_TREE_H
#define?BINARY_SEARCH_TREE_H

#include?<stdio.h>

template<typename?T>
struct?BTreeNode
{
????T????Data;
????BTreeNode*?pLeft;
????BTreeNode*?pRight;
????BTreeNode*?pParent;

????BTreeNode(????T?data?=?T(),?BTreeNode<T>*?Parent?=?NULL,?
????????????????BTreeNode<T>*?Left?=?NULL,?BTreeNode<T>*?Right?=?NULL)
????????????????:?Data(data),?pLeft(Left),?pRight(Right),?pParent(Parent)
????{
????}
};

template<typename?T>
class?BSTree
{
protected:
????BTreeNode<T>*????m_pRootNode;

public:
????BSTree(BTreeNode<T>*?pRoot?=?NULL)?
????????:?m_pRootNode(pRoot)
????{
????}
????~BSTree();

????void????????????Display();
????BTreeNode<T>*????Insert(const?T&?data);
????BTreeNode<T>*????Find(const?T&?data);
????BTreeNode<T>*????FindMin();
????BTreeNode<T>*????FindMax();
????BTreeNode<T>*????Delete(const?T&?data);

private:
????void????????????Display(BTreeNode<T>*?p);
????BTreeNode<T>*????Insert(const?T&?data,?BTreeNode<T>*?p);
????BTreeNode<T>*????Find(const?T&?data,?BTreeNode<T>*?p);
????BTreeNode<T>*????FindMin(BTreeNode<T>*?p);
????BTreeNode<T>*????FindMax(BTreeNode<T>*?p);
????BTreeNode<T>*????Delete(const?T&?data,?BTreeNode<T>*?p);

????void????????????DestructImpl(BTreeNode<T>*?p);
};

#endif

2)BSTree.cpp
/********************************************************************
????created:????2006/07/28
????filename:?????BSTree.cpp
????author:????????李創(chuàng)
????????????????http://m.shnenglu.com/converse/

????purpose:????二叉查找樹的實(shí)現(xiàn)代碼
*********************************************************************/

#include?<iostream>
#include?"BSTree.h"

template<typename?T>
BSTree<T>::~BSTree()
{
????DestructImpl(m_pRootNode);
}

template<typename?T>
void?BSTree<T>::DestructImpl(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????????return;

????DestructImpl(p->pLeft);
????DestructImpl(p->pRight);
????p->pLeft?=?NULL;
????p->pRight?=?NULL;
????p->pParent?=?NULL;
????delete?p;
????p?=?NULL;
}

template<typename?T>
void?BSTree<T>::Display()
{
????Display(m_pRootNode);
}

//?中序打印出樹中的元素,這樣應(yīng)該是從小到大的順序
template<typename?T>
void?BSTree<T>::Display(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????????return;

????Display(p->pLeft);
????std::cout?<<?"Node?=?"?<<?p->Data?<<?std::endl;
????Display(p->pRight);
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::Insert(const?T&?data)
{
????return?Insert(data,?m_pRootNode);
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::Insert(const?T&?data,?BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????p?=?new?BTreeNode<T>(data);

????????if?(NULL?==?p)
????????{
????????????return?NULL;
????????}
????????else?if?(NULL?==?m_pRootNode)
????????{
????????????m_pRootNode?=?p;
????????}
????}
????else?if?(data?>?p->Data)
????{
????????p->pRight?=?Insert(data,?p->pRight);
????????if?(NULL?!=?p->pRight)
????????{
????????????p->pRight->pParent?=?p;
????????}
????}
????else
????{
????????p->pLeft?=?Insert(data,?p->pLeft);
????????if?(NULL?!=?p->pLeft)
????????{
????????????p->pLeft->pParent?=?p;
????????}
????}

????return?p;
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::Find(const?T&?data)
{
????return?Find(data,?m_pRootNode);
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::Find(const?T&?data,?BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}
????else
????{
????????if?(data?==?p->Data)
????????{
????????????return?p;
????????}
????????else?if?(data?>?p->Data)
????????{
????????????return?Find(data,?p->pRight);
????????}
????????else
????????{
????????????return?Find(data,?p->pLeft);
????????}
????}
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMin()
{
????return?FindMin(m_pRootNode);
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMin(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}

????if?(NULL?!=?p->pLeft)
????{
????????return?FindMin(p->pLeft);
????}
????else
????{
????????return?p;
????}
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMax()
{
????return?FindMax(m_pRootNode);
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMax(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}

????if?(NULL?!=?p->pRight)
????{
????????return?FindMax(p->pRight);
????}
????else
????{
????????return?p;
????}
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::Delete(const?T&?data)
{
????return?Delete(data,?m_pRootNode);
}

template<typename?T>
BTreeNode<T>*?BSTree<T>::Delete(const?T&?data,?BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}
????else?if?(data?<?p->Data)
????{
????????p->pLeft?=?Delete(data,?p->pLeft);
????}
????else?if?(data?>?p->Data)
????{
????????p->pRight?=?Delete(data,?p->pRight);
????}
????else?if?(NULL?!=?p->pLeft?&&?NULL?!=?p->pRight)
????{
????????//?找到結(jié)點(diǎn)且有兩個(gè)子結(jié)點(diǎn)
????????BTreeNode<T>*?pNode;
????????//?找到右子樹中最小的結(jié)點(diǎn),把它的值替換當(dāng)前結(jié)點(diǎn)值,然后刪除找到的那個(gè)結(jié)點(diǎn)
????????pNode?=?FindMin(p->pRight);
????????p->Data?=?pNode->Data;
????????p->pRight?=?Delete(p->Data,?p->pRight);
????}
????else
????{
????????//?找到結(jié)點(diǎn)但是只有一個(gè)或沒有子結(jié)點(diǎn)
????????//?如果有子結(jié)點(diǎn)就用子結(jié)點(diǎn)代替當(dāng)前結(jié)點(diǎn),然后刪除當(dāng)前結(jié)點(diǎn)
????????BTreeNode<T>*?pNode?=?p;
????????if?(NULL?==?p->pLeft)
????????{
????????????p?=?p->pRight;
????????}
????????else?if?(NULL?==?p->pRight)
????????{
????????????p?=?p->pLeft;
????????}
????????delete?pNode;
????????pNode?=?NULL;
????}

????return?p;
}


3)Main.cpp
#include?"BSTree.h"
#include?<stdlib.h>
#include?<time.h>

//?創(chuàng)建一個(gè)數(shù)組,元素值隨機(jī)設(shè)置
void?CreateNewArray(int?array[],?int?length)
{
????for?(int?i?=?0;?i?<?length;?i++)
????{
????????array[i]?=?rand()?%?256;
????}
}

int?main()
{
????int?array[10];
????srand(time(NULL));

????CreateNewArray(array,?10);
????BSTree<int>?tree;
????for?(int?i?=?0;?i?<?10;?++i)
????{
????????tree.Insert(array[i]);
????}
????tree.Display();
????if?(NULL?!=?tree.Find(array[7]))
????{
????????std::cout?<<?"Find!\n";
????}

????BTreeNode<int>*?pNode;

????if?(NULL?!=?(pNode?=?tree.FindMin()))
????{
????????std::cout?<<?"Min?=?"?<<?pNode->Data?<<?std::endl;
????}

????if?(NULL?!=?(pNode?=?tree.FindMax()))
????{
????????std::cout?<<?"Max?=?"?<<?pNode->Data?<<?std::endl;
????}

????tree.Delete(array[7]);
????std::cout?<<?"\nafter?delete?"?<<?array[7]?<<?std::endl;
????tree.Display();

????system("pause");
????return?0;
}

需要說明一點(diǎn):上面做測(cè)試用的Main.cpp如果單獨(dú)寫在一個(gè)文件中就會(huì)在鏈接的時(shí)候報(bào)錯(cuò),報(bào)的錯(cuò)誤是:
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Insert(int const &)" (?Insert@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: __thiscall BSTree<int>::~BSTree<int>(void)" (??1?$BSTree@H@@QAE@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Delete(int const &)" (?Delete@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMax(void)" (?FindMax@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMin(void)" (?FindMin@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Find(int const &)" (?Find@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: void __thiscall BSTree<int>::Display(void)" (?Display@?$BSTree@H@@QAEXXZ) referenced in function _main

所以沒有辦法,我只能將main.cpp中的內(nèi)容copy到BSTree.cpp中才能鏈接過去.

如果哪位朋友知道如何解決上面因?yàn)椴捎昧四０孱惓霈F(xiàn)的鏈接錯(cuò)誤,我不勝感激,謝謝!

posted on 2006-07-29 00:33 那誰 閱讀(6718) 評(píng)論(2)  編輯 收藏 引用 所屬分類: 算法與數(shù)據(jù)結(jié)構(gòu)

評(píng)論

# re: 二叉查找樹的解析與實(shí)現(xiàn)  回復(fù)  更多評(píng)論   

實(shí)際上，模板的實(shí)現(xiàn)應(yīng)該和它的聲明都放在頭文件中，這樣就可以將main.cpp單獨(dú)實(shí)現(xiàn)出來了。
目前標(biāo)準(zhǔn)cpp中有一個(gè)關(guān)鍵字export可以讓模板的實(shí)現(xiàn)和聲明分開在頭文件和.cpp文件中，但是目前只有一個(gè)編譯器實(shí)現(xiàn)了改功能（據(jù)我所知），而且即使分開了來實(shí)現(xiàn)，模板的.cpp實(shí)現(xiàn)也是必須要客戶端可見的（這和普通的.cpp文件那種將具體實(shí)現(xiàn)屏蔽的特性不一樣），而且export關(guān)鍵字引入給cpp帶來了很多麻煩的事情，大家目前對(duì)如何使用export也沒有什么經(jīng)驗(yàn)。
2006-08-27 14:58 | wb

# re: 二叉查找樹的解析與實(shí)現(xiàn)  回復(fù)  更多評(píng)論   

我覺得你的display函數(shù)，中的<<操作符應(yīng)重載后再使用，既然使用了模板，就有可能會(huì)出現(xiàn)<<并不支持的類型。
2008-03-25 23:13 | cndx100
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
国产精品日韩专区|
一区二区三区日韩在线观看
|
欧美在线综合视频|
亚洲在线电影|
欧美不卡视频|
欧美高清影院|
欧美色图五月天|
国产精品青草久久|
激情久久综艺|
9色精品在线|
亚洲欧美日韩精品久久|
久久大综合网|
欧美激情bt|
亚洲一区二区三区高清|
欧美中文在线视频|
欧美精品精品一区|
国产亚洲人成a一在线v站|
国产精品综合久久久|
国语对白精品一区二区|
亚洲国产日韩精品|
亚洲综合精品|
老色批av在线精品|
亚洲日本免费电影|
99精品国产一区二区青青牛奶|
99在线精品观看|
久久精品最新地址|
欧美三级乱人伦电影|
国产日韩欧美亚洲一区|
亚洲伦理精品|
久久久国产一区二区三区|
亚洲国产另类久久精品|
香蕉尹人综合在线观看|
欧美国产精品日韩|
在线观看视频一区二区欧美日韩
|
国产日韩欧美一区在线|
亚洲第一网站|
欧美亚洲视频|
亚洲老板91色精品久久|
久久影视精品|
国产亚洲va综合人人澡精品|
在线亚洲免费|
亚洲国产精品久久久久秋霞蜜臀|
午夜精品久久久99热福利|
欧美日韩精品免费观看视频完整|
国产一区二区三区久久|
午夜精品福利电影|
中文国产亚洲喷潮|
欧美日韩性视频在线|
亚洲国产成人久久|
久久人人爽人人|
亚洲欧美视频一区|
欧美午夜精品理论片a级按摩
|
欧美一级片在线播放|
最新亚洲一区|
欧美精品999|
最新国产乱人伦偷精品免费网站|
久久天天躁夜夜躁狠狠躁2022|
亚洲欧美国产制服动漫|
国产精品久久一区二区三区|
亚洲男女毛片无遮挡|
午夜天堂精品久久久久|
日韩亚洲综合在线|
欧美日韩在线播放|
午夜欧美不卡精品aaaaa|
亚洲视频1区2区|
国产精品手机视频|
午夜免费在线观看精品视频|
午夜精品免费|
国内外成人在线视频|
久久久亚洲国产美女国产盗摄|
欧美一级片在线播放|
国产主播一区二区三区四区|
久久久99精品免费观看不卡|
久久伊人亚洲|
亚洲精品一区在线|
在线视频欧美日韩|
国产一区二区三区自拍|
欧美成人三级在线|
欧美美女日韩|
亚洲欧美一区二区三区极速播放|
欧美在线视频不卡|
亚洲毛片一区二区|
亚洲在线成人精品|
亚洲人成亚洲人成在线观看图片|
亚洲狼人综合|
国内外成人免费激情在线视频网站
|
麻豆久久婷婷|
亚洲午夜久久久久久久久电影网|
亚洲一区二区三区色|
亚洲高清在线播放|
一区二区三区日韩精品视频|
激情五月婷婷综合|
亚洲人人精品|
国产性天天综合网|
亚洲日本中文字幕|
国产性做久久久久久|
亚洲欧洲精品一区二区三区|
国产精品日韩|
亚洲第一中文字幕在线观看|
欧美日韩在线高清|
久久中文字幕导航|
国产精品国产三级国产普通话三级
|
亚洲欧美日韩国产中文|
亚洲欧洲偷拍精品|
欧美一区二区三区视频在线|
日韩一级片网址|
欧美综合第一页|
亚洲色图自拍|
欧美大香线蕉线伊人久久国产精品|
午夜电影亚洲|
免费观看一区|
久久精品国产免费观看|
欧美日韩一级片在线观看|
免费日韩av片|
欧美午夜精品|
亚洲国产美女精品久久久久∴|
欧美午夜影院|
亚洲高清久久网|
国内精品久久久久久久果冻传媒|
国产精品免费视频观看|
国产欧美一区二区精品性|
久久人人爽爽爽人久久久|
欧美日韩一本到|
免费黄网站欧美|
国产午夜精品麻豆|
一区二区三欧美|
一区二区欧美国产|
欧美第一黄色网|
欧美国产专区|
在线观看精品一区|
久久久久免费观看|
欧美在线在线|
国产精品丝袜91|
午夜久久久久|
香蕉成人伊视频在线观看|
亚洲伊人色欲综合网|
欧美人成在线视频|
亚洲区免费影片|
亚洲精品偷拍|
欧美精品久久久久久久久老牛影院|
免费一级欧美片在线观看|
尤物在线精品|
久久亚洲综合色|
农村妇女精品|
1024国产精品|
欧美精品首页|
99国产精品久久久|
亚洲免费影视|
国产日本欧美一区二区三区在线|
午夜精品福利在线观看|
久久精品国产v日韩v亚洲
|
欧美中文字幕视频|
美女主播精品视频一二三四|
亚洲第一区中文99精品|
欧美精品一区视频|
中文有码久久|
久久精品国语|
亚洲欧洲一区二区三区在线观看|
欧美成人a视频|
亚洲伦理一区|
午夜久久电影网|
国内自拍视频一区二区三区|
欧美va天堂在线|
亚洲视频 欧洲视频|
老司机精品久久|
夜夜嗨av一区二区三区免费区|
国产精品成人在线|
久久人人97超碰国产公开结果|
欧美福利网址|
中文久久精品|
精品成人一区|
国产精品久久久久免费a∨|
欧美一区二区三区日韩|
亚洲国内精品|
久久综合图片|
一区二区三区久久久|
国产小视频国产精品|
欧美日韩亚洲综合在线|
久热精品视频在线观看|
亚洲综合精品一区二区|
亚洲福利视频专区|
久久er精品视频|
国产精品99久久久久久白浆小说|
精品va天堂亚洲国产|
欧美色欧美亚洲高清在线视频|
欧美在线啊v|
亚洲影视中文字幕|
亚洲国产精品va在线观看黑人|
亚洲综合色噜噜狠狠|
日韩视频二区|
久久久国产精品一区二区中文|
夜夜嗨av一区二区三区|
亚洲大片在线观看|
国产日韩欧美不卡|
国产精品夜色7777狼人|
欧美日韩免费观看一区=区三区|
久久色在线播放|
欧美亚洲视频在线观看|
亚洲图片在线观看|
亚洲三级毛片|