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

那誰的技術(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://www.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://www.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>
            
日韩午夜精品视频|
午夜久久资源|
欧美成人综合一区|
亚洲欧洲在线一区|
亚洲精品小视频在线观看|
免费日韩av片|
亚洲久色影视|
亚洲一区二区三区777|
国产亚洲精品自拍|
欧美aⅴ一区二区三区视频|
麻豆国产精品va在线观看不卡|
久久狠狠亚洲综合|
亚洲美女色禁图|
欧美成人一区二区|
亚洲私人影院|
久久av一区二区三区|
91久久极品少妇xxxxⅹ软件|
国产精品国产馆在线真实露脸|
欧美无砖砖区免费|
久久久久国产一区二区三区|
久久免费午夜影院|
9久re热视频在线精品|
亚洲免费一级电影|
在线精品视频免费观看|
99国产精品久久久久久久久久
|
欧美一站二站|
亚洲精品少妇|
久久岛国电影|
亚洲午夜久久久久久尤物
|
中文av一区二区|
性欧美暴力猛交69hd|
亚洲人在线视频|
午夜精品理论片|
一区二区三区av|
亚洲欧洲日产国产综合网|
免费成人黄色|
国产美女精品|
亚洲人体影院|
国产九九视频一区二区三区|
亚洲国产精品黑人久久久|
国产精品拍天天在线|
亚洲国产日韩欧美一区二区三区|
国产精品视频男人的天堂|
亚洲精品久久久久久一区二区
|
一区二区三区四区在线|
亚洲永久字幕|
欧美国产一区二区三区激情无套|
欧美一区二区三区日韩|
欧美精品在线观看一区二区|
久久视频在线免费观看|
国产精品乱人伦中文|
亚洲国产日韩一级|
亚洲国产成人在线播放|
午夜精品一区二区在线观看|
亚洲天堂视频在线观看|
欧美激情综合|
亚洲激情午夜|
亚洲人成毛片在线播放|
久热这里只精品99re8久|
久久精品国产久精国产爱|
国产精品高精视频免费|
亚洲蜜桃精久久久久久久|
日韩视频永久免费观看|
欧美成人精品一区二区三区|
欧美成人免费视频|
亚洲盗摄视频|
欧美成黄导航|
亚洲国产精品久久久|
亚洲精品久久嫩草网站秘色|
欧美成年网站|
午夜精品影院|
国内精品久久久久影院优|
一区二区三区视频在线|
亚洲欧美日韩国产一区二区|
欧美偷拍一区二区|
亚洲性线免费观看视频成熟|
性欧美大战久久久久久久免费观看
|
亚洲精品国产品国语在线app
|
国产一区二区三区四区三区四
|
久久久久久综合网天天|
蜜臀91精品一区二区三区|
在线观看免费视频综合|
欧美成人精品在线|
日韩小视频在线观看专区|
亚洲午夜av电影|
国产视频一区在线观看一区免费|
亚洲国产cao|
亚洲国产网站|
亚洲午夜影视影院在线观看|
国产精品午夜久久|
久久久国产精品亚洲一区|
欧美激情一区二区三区四区|
在线视频你懂得一区|
国产精品网站一区|
久久色在线观看|
日韩一区二区福利|
久久亚洲精选|
一区二区三区导航|
国产一级揄自揄精品视频|
麻豆乱码国产一区二区三区|
一本久久青青|
欧美va亚洲va国产综合|
亚洲一二三区在线|
在线观看视频欧美|
欧美日韩中文字幕日韩欧美|
久久国产精品久久久久久|
亚洲精品美女在线|
久久精品99无色码中文字幕|
亚洲精品国产精品乱码不99按摩|
国产精品视频九色porn|
欧美韩日精品|
久久久免费av|
午夜精品久久久久久久蜜桃app|
欧美成人一区二区三区|
午夜一区在线|
一级日韩一区在线观看|
激情五月婷婷综合|
国产精品专区h在线观看|
欧美高潮视频|
久久亚洲精品一区|
亚欧美中日韩视频|
亚洲网址在线|
日韩视频永久免费|
亚洲福利视频一区二区|
久久天堂国产精品|
久久精品免费|
欧美一级精品大片|
亚洲专区一区二区三区|
99成人在线|
91久久精品视频|
亚洲第一福利社区|
激情综合网址|
韩曰欧美视频免费观看|
国产三级精品三级|
亚洲成人资源网|
开心色5月久久精品|
aⅴ色国产欧美|
亚洲精品在线视频|
亚洲激情一区|
亚洲国产婷婷香蕉久久久久久99|
国产综合欧美|
黄色欧美成人|
91久久在线播放|
今天的高清视频免费播放成人|
国产精品视频最多的网站|
国产精品国产三级国产aⅴ浪潮
|
欧美一区高清|
久久九九精品99国产精品|
欧美一级一区|
久久久精品一区|
快she精品国产999|
美国成人毛片|
欧美片第1页综合|
欧美手机在线视频|
国产免费一区二区三区香蕉精|
国产精品腿扒开做爽爽爽挤奶网站|
国产精品成人v|
国产日韩欧美二区|
韩国精品久久久999|
亚洲国产一区二区精品专区|
亚洲国产一区在线观看|
91久久夜色精品国产九色|
亚洲午夜精品久久久久久浪潮
|
国产亚洲精品bt天堂精选|
国产综合色产在线精品|
亚洲激情在线激情|
一区二区三区导航|
久久久999精品|
亚洲高清不卡|
欧美理论电影网|
欧美日韩综合在线免费观看|
国产精品网站在线观看|
伊人久久大香线蕉av超碰演员|
亚洲狠狠丁香婷婷综合久久久|
一个色综合导航|
久久精品中文字幕一区|
亚洲国产精品ⅴa在线观看
|
亚洲乱码国产乱码精品精可以看|
亚洲美女中文字幕|
欧美在线网址|
久久婷婷av|
午夜天堂精品久久久久|
欧美ab在线视频|
亚洲伊人色欲综合网|
免费成人毛片|
国产日韩精品一区二区三区|
亚洲国产婷婷|
久久久亚洲影院你懂的|
亚洲另类在线视频|
久久伊伊香蕉|
国产精品一二一区|
亚洲免费激情|
欧美成年人网站|
亚洲欧美日韩第一区|
欧美激情第五页|
狠狠综合久久av一区二区小说|
亚洲网站在线看|
欧美电影免费观看高清完整版|
亚洲你懂的在线视频|
欧美日韩久久|