歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

二叉排序樹實現(C++封裝)

設計思路

設計一個類,根結點只可讀取,具備構造二叉樹、插入結點、刪除結點、查找、 查找最大值、查找最小值、查找指定結點的前驅和後繼等功能接口。

二叉排序樹概念

它或者是一棵空樹;或者是具有下列性質的二叉樹:
(1)若左子樹不空,則左子樹上所有結點的值均小於它的根結點的值; (2)若右子樹不空,則右子樹上所有結點的值均大於它的根結點的值;
(3)左、右子樹也分別為二叉排序樹。

二叉排序樹的各種操作

插入新節點
這是一個遞歸操作,遞歸設計時要找到最源頭,才能得到最簡設計。一種設計是判斷葉子節點,把新節點作為葉子節點的孩子插入;一種是永遠當作根進行插入,插入節點永遠是當前子樹的根!看代碼:


//root為二級指針的原因是,如果樹為空,需要將根修改反饋回來
bool BinaryTree::InsertNode(pNode * cuRoot, int data, pNode self)
{  //遞歸設計時找到最源頭,才能得到最簡設計
    if (*cuRoot == nullptr){
        pNode node = new Node;
        if (node == nullptr)
            return false;
        node->data = data;
        node->lChild = node->rChild = node->parent = nullptr;
        (*cuRoot) = node;
        node->parent = self;
        return true;
    }
    if (data > (*cuRoot)->data)
        InsertNode(&(*cuRoot)->rChild, data, *cuRoot);
    else
        InsertNode(&(*cuRoot)->lChild, data, *cuRoot);
    return true;
}

 

構造函數
一共兩個重載函數:一個無參,一個接受數組利用插入函數直接構造二叉排序樹。

 

BinaryTree::BinaryTree(int * datum, int len)
{
    root = nullptr;
    for (int i = 0; i < len; i++)
        InsertNode(&root, datum[i], root);
}

BinaryTree::BinaryTree()
{
    root = nullptr;
}

 

查找函數
這也是一個遞歸操作,為了對外隱藏root(根節點),因此編寫了一個私有函數,進行真正的查找操作。

 

//真正的查找函數
BinaryTree::pNode BinaryTree::_searchKey(pNode root, int key){
    if (root == nullptr)
        return nullptr;
    if (root->data == key)    //找到了
        return root;
    else if (root->data > key)//值偏小,到左子樹找
        return _searchKey(root->lChild, key);
    else                      //值偏大,到右子樹找
        return _searchKey(root->rChild, key);
}
//對外接口
BinaryTree::pNode BinaryTree::SearchKey(int key){
    return _searchKey(root, key);
}

 

找前驅節點
要麼為左子樹中最大者,要麼一直追溯其父節點鏈,第一個是其父節點的右孩子的父節點,即為所求。

 

BinaryTree::pNode BinaryTree::SearchPredecessor(pNode node){
    if (node == nullptr)
        return nullptr;
    else if (node->lChild != nullptr)
        return SearchMaxNode(node->lChild);
    else
    {
        if (node->parent == nullptr)
            return nullptr;
        while (node)
        {
            if (node->parent->rChild == node)
                break;
            node = node->parent;
        }
        return node->parent;
    }
}

 

找後繼節點
與找前驅節點基本相似。 要麼為右子樹中最小者,要麼一直追溯其父節點鏈,第一個是其父節點的左孩子的父節點,即為所求。

 

BinaryTree::pNode BinaryTree::SearchSuccessor(pNode node){
    if (node == nullptr)
        return nullptr;
    else if (node->rChild != nullptr)
        return SearchMinNode(node->rChild);
    else
    {
        if (node->parent == nullptr)
            return nullptr;
        while (node)
        {
            if (node->parent->lChild == node)
                break;
            node = node->parent;
        }
        return node->parent;
    }
}

 

找最小值

 

BinaryTree::pNode BinaryTree::SearchMinNode(pNode curNode){
    if (curNode == nullptr)
        return nullptr;
    //一直找到左子樹為空的節點,即為最小值
    while (curNode->lChild != nullptr)
        curNode = curNode->lChild;
    return curNode;
}

 

找最大值

 

BinaryTree::pNode BinaryTree::SearchMaxNode(pNode curNode){
    if (curNode == nullptr)
        return nullptr;
    //一直找到右子樹為空的節點,即為最大值
    while (curNode->rChild != nullptr)
        curNode = curNode->rChild;
    return curNode;
}

 

中序遍歷

 

void BinaryTree::_visitMiddle(pNode root){
    if (root != nullptr){
        _visitMiddle(root->lChild);
        printf("%d;", root->data);
        _visitMiddle(root->rChild);
    }
}

void BinaryTree::VisitMiddle(){
    _visitMiddle(root);
}

 

刪除節點
這個是最麻煩的操作,分四種情況分別處理,最麻煩的是被刪節點左右子樹都存在的情況,這時將被刪節點內容換成其後繼內容,刪除其後繼(遞歸)。

 

bool BinaryTree::DeleteNode(int key){
    //return _deleteNode(root, key);
    pNode node = SearchKey(key);
    if (!node)
        return false;
    //被刪節點為葉子結點
    if (node->lChild == nullptr && node->rChild == nullptr){
        if (node->parent == nullptr){
            root = nullptr;
        }
        else
        {
            if (node->parent->lChild == node)
                node->parent->lChild = nullptr;
            else
                node->parent->rChild = nullptr;
        }
        delete node;
    }
    //被刪節點只有左子樹
    else if (node->lChild != nullptr && node->rChild == nullptr){
        //將左孩子的父親指向被刪節點的父親
        node->lChild->parent = node->parent;
        //被刪節點為根,修改根節點
        if (node->parent == nullptr)
            root = node->lChild;
        else if(node->parent->lChild == node)
            node->parent->lChild = node->lChild;
        else
            node->parent->rChild = node->lChild;
        delete node;
    }
    //被刪節點只有右子樹
    else if (node->lChild == nullptr && node->rChild != nullptr){
        //將右孩子的父親指向被刪節點的父親
        node->rChild->parent = node->parent;
        //被刪節點為根,修改根節點
        if (node->parent == nullptr)
            root = node->rChild;
        else if (node->parent->lChild == node)
            node->parent->lChild = node->rChild;
        else
            node->parent->rChild = node->rChild;
        delete node;
    }
    //被刪節點左、右子樹都有
    else {  //用後繼節點取代刪除節點,並刪除後繼
        pNode successor = SearchSuccessor(node);
        int temp = successor->data;
        DeleteNode(temp);
        node->data = temp;
    }
}

 

柝構函數
函數超出作用域范圍時,清理占用內存。

 

BinaryTree::~BinaryTree()
{
    _delAllNode(root);
}
void BinaryTree::_delAllNode(pNode root){
    if (root != nullptr && root!=NULL){
        _delAllNode(root->lChild);
        _delAllNode(root->rChild);     
        DeleteNode(root->data);
    }
}

 

類的定義(頭文件)

 

#pragma once

#include<stdio.h> 
#include<stdlib.h>

class BinaryTree
{
private:
    typedef struct Node{
        struct Node * parent;
        struct Node * lChild;
        struct Node * rChild;
        int data;
    }*pNode;
    pNode root;
    void _visitMiddle(pNode root);
    pNode _searchKey(pNode root, int key);
    void _delAllNode(pNode root);
public:
    BinaryTree();
    BinaryTree(int * datum, int len);
    pNode SearchMaxNode(pNode node);
    pNode SearchMinNode(pNode node);
    pNode GetRoot();
    pNode SearchKey(int key);
    bool DeleteNode(int key);
    pNode SearchPredecessor(pNode node);
    pNode SearchSuccessor(pNode node);
    void VisitMiddle();
    bool InsertNode(pNode * cuRoot, int data, pNode self);
    ~BinaryTree();
};

調用示例

#include <conio.h>
#include "BinaryTree.h"

int main()
{
    int arrs[] = { 23, 65, 12, 3, 8, 76,  90, 21, 75, 34,345, 61 };
    int len = sizeof(arrs) / sizeof(arrs[0]);
    BinaryTree bTree(arrs,len);
    bTree.DeleteNode(90);
    bTree.VisitMiddle();
    getch();
    return 0;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

Copyright © Linux教程網 All Rights Reserved