二叉樹(C/C++)

\color{red}{先拋出一個(gè)問題:什么是二叉樹,它能用來干嘛,答案在文中湿蛔。}

二叉樹的種類

?二叉樹的種類網(wǎng)上介紹的很多,這里簡(jiǎn)單用幾張圖描述一下县爬。
注意:二叉樹每個(gè)結(jié)點(diǎn)最多只有兩棵子樹阳啥,這意味著任意結(jié)點(diǎn)的度小于等于2。子樹有左右之分财喳;某個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)察迟,它位于左邊和右邊組成的是不同的樹斩狱。

滿二叉樹

?除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。很顯然扎瓶,按照這個(gè)定義所踊,上面的圖示二叉樹就不是滿二叉樹。

完全二叉樹

1.滿二叉樹一定是完全二叉樹概荷,完全二叉樹不一定是滿二叉樹

  1. 某結(jié)點(diǎn)的度如果為1秕岛,則它只有左孩子
    3.葉子結(jié)點(diǎn)只能出現(xiàn)在最后兩層(考慮樹2)
    4.相同結(jié)點(diǎn)的樹中,完全二叉樹的深度最小

斜數(shù)(特殊的鏈表)

如果一棵二叉樹只有左孩子误证,則稱該樹為左斜樹继薛,類似的如果只有右孩子,就稱為右斜樹雷厂,他們統(tǒng)稱為斜樹惋增。這時(shí)候樹就演化成了鏈表。樹的深度就是樹的結(jié)點(diǎn)個(gè)數(shù)改鲫。

二叉搜索樹

二叉搜索樹是一個(gè)有序樹。
·若它的左子樹不空林束,則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值像棘;
·若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值壶冒;
·它的左缕题、右子樹也分別為二叉排序樹

平衡二叉搜索樹

左右兩個(gè)子樹的高度差不超過1的二叉搜索樹。
之前的map的底層實(shí)現(xiàn)就是平衡二叉搜索樹胖腾,但是unordered_map的底層實(shí)現(xiàn)是用哈希表烟零,所以map的時(shí)間復(fù)雜度是logn,而unordred_map不是咸作,unordered_map時(shí)間復(fù)雜度不穩(wěn)定锨阿,平均為O(c),取決于哈希函數(shù)记罚。極端情況下可能為O(n)

存儲(chǔ)方式

鏈?zhǔn)酱鎯?chǔ)

數(shù)組存儲(chǔ)

父節(jié)點(diǎn)的數(shù)組下表是i墅诡,那么它的左孩子就是i * 2 + 1,右孩子就是 i * 2 + 2桐智。(一般使用鏈表末早,這個(gè)看看就好了)

怎么建立一個(gè)二叉樹

先看一下怎么定義一個(gè)二叉樹

struct TreeNode   
{  
    int val;  
    struct TreeNode *left;  
    struct TreeNode *right;  
};  

遞歸

struct TreeNode* CreateTree(vector<int>num, int n, int start)  
{  
    if (num[start] == 0)  
    {  
        return NULL;  
    }  
    // 根  
    TreeNode *root = new TreeNode;    
    root->val = num[start];  
    root->left = NULL;  
    root->right = NULL;  
    // 左子樹  
    int lnode = 2 * start + 1;  
    int rnode = 2 * start + 2;  
    if (lnode > n - 1)  
    {  
        root->left = NULL;  
    }  
    else  
    { 
        root->left = CreateTree(num, n, lnode);  
    }   
    if (rnode > n - 1)  
    {  
        root->right = NULL;  
    }  
    else  
    {  
        root->right = CreateTree(num, n, rnode);  
    }  
    return root;  
}  

二叉樹的遍歷方式

1.深度優(yōu)先遍歷:先往深走,遇到葉子節(jié)點(diǎn)再往回走说庭。
2.廣度優(yōu)先遍歷:一層一層的去遍歷然磷。
·深度優(yōu)先遍歷
先序遍歷(遞歸法,迭代法)
中序遍歷(遞歸法刊驴,迭代法)
后序遍歷(遞歸法姿搜,迭代法)
·廣度優(yōu)先遍歷
層次遍歷(迭代法)
這里前中后序遍歷,其實(shí)指的就是中間節(jié)點(diǎn)的遍歷順序。
先序遍歷:中左右
中序遍歷:左中右
后序遍歷:左右中

遞歸求解先中后序遍歷

1.先序

void tree(TreeNode* root, vector<int>& vec)   
{  
    if (root== NULL) return;
    vec.push_back(cur->val);    // 中  
    tree(root->left, vec);  // 左  
    tree(root->right, vec); // 右 
}   
  1. 中序
void tree(TreeNode* root, vector<int>& vec)     
{    
    if (root== NULL) return;  
    tree(root->left, vec);  // 左  
    vec.push_back(root->val);    // 中  
    tree(root->right, vec); // 右  
}     

3.后序

void tree(TreeNode* root, vector<int>& vec)   
{  
    if (root== NULL) return;
    tree(root->left, vec);  // 左
    tree(root->right, vec); // 右
    vec.push_back(root->val);    // 中
}   

迭代法求二叉樹

這里需要用到棧痪欲,還不清楚的可以看一下我的另一篇淺談棧與隊(duì)列悦穿。

vector<int> pre(TreeNode* root)  
 {  
    stack<TreeNode*> qwe;  
    vector<int> result;  
    qwe.push(root);   
    while (!qwe.empty())   
{      
        TreeNode* node = qwe.top();                        // 中     
        qwe.pop();    
        if (node != NULL) result.push_back(node->val);  
        else 
            continue;  
        qwe.push(node->right);                           // 右  
        qwe.push(node->left);                            // 左   
    }  
    return result; 
}  

層序遍歷

vector<vector<int>> levelOrder(TreeNode* root) {  
        queue<TreeNode*> que;  
        if (root != NULL) que.push(root);  
        vector<vector<int>> result;  
        while (!que.empty()) {  
            int size = que.size();  
            vector<int> vec;  
            // 這里一定要使用固定大小size,不要使用que.size()业踢,因?yàn)閝ue.size是不斷變化的  
            for (int i = 0; i < size; i++) {  
                TreeNode* node = que.front();  
                que.pop();  
                vec.push_back(node->val);   
                if (node->left) que.push(node->left);  
                if (node->right) que.push(node->right);   
            }  
            result.push_back(vec);  
        }  
        return result;  
    }  

文章參考:https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末栗柒,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子知举,更是在濱河造成了極大的恐慌瞬沦,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,734評(píng)論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件雇锡,死亡現(xiàn)場(chǎng)離奇詭異逛钻,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)锰提,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,931評(píng)論 3 394
  • 文/潘曉璐 我一進(jìn)店門曙痘,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人立肘,你說我怎么就攤上這事边坤。” “怎么了谅年?”我有些...
    開封第一講書人閱讀 164,133評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵茧痒,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我融蹂,道長(zhǎng)旺订,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,532評(píng)論 1 293
  • 正文 為了忘掉前任超燃,我火速辦了婚禮区拳,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘淋纲。我一直安慰自己劳闹,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,585評(píng)論 6 392
  • 文/花漫 我一把揭開白布洽瞬。 她就那樣靜靜地躺著本涕,像睡著了一般。 火紅的嫁衣襯著肌膚如雪伙窃。 梳的紋絲不亂的頭發(fā)上菩颖,一...
    開封第一講書人閱讀 51,462評(píng)論 1 302
  • 那天,我揣著相機(jī)與錄音为障,去河邊找鬼晦闰。 笑死放祟,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的呻右。 我是一名探鬼主播跪妥,決...
    沈念sama閱讀 40,262評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼声滥!你這毒婦竟也來了眉撵?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,153評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤落塑,失蹤者是張志新(化名)和其女友劉穎纽疟,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體憾赁,經(jīng)...
    沈念sama閱讀 45,587評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡污朽,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,792評(píng)論 3 336
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了龙考。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蟆肆。...
    茶點(diǎn)故事閱讀 39,919評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖洲愤,靈堂內(nèi)的尸體忽然破棺而出颓芭,到底是詐尸還是另有隱情,我是刑警寧澤柬赐,帶...
    沈念sama閱讀 35,635評(píng)論 5 345
  • 正文 年R本政府宣布,位于F島的核電站官紫,受9級(jí)特大地震影響肛宋,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜束世,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,237評(píng)論 3 329
  • 文/蒙蒙 一酝陈、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧毁涉,春花似錦沉帮、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,855評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至其屏,卻和暖如春喇勋,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背偎行。 一陣腳步聲響...
    開封第一講書人閱讀 32,983評(píng)論 1 269
  • 我被黑心中介騙來泰國打工川背, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留贰拿,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,048評(píng)論 3 370
  • 正文 我出身青樓熄云,卻偏偏與公主長(zhǎng)得像膨更,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子缴允,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,864評(píng)論 2 354