数据结构之树：二叉树的实现

马谦马谦马谦

615
文章

17
评论

2018年3月25日18:05:06数据结构和算法评论850字数 501阅读1分40秒阅读模式

相对于栈和链表等数据结构来说，树有着更复杂的结构。正如我们平常生活中看到的树一样，它有很多分支，而且分支上面还会有分支。

树的用途十分广泛，最常见的树是二叉树，衍生了很多类型的树，红黑树，搜索树等等，被用来查找效率十分高，一个最典型的应用就是mysql中的索引。

树是由很多个节点构成，要实现一个树最最主要的就是实现树的节点。

一、二叉树节点实现

1.1 二叉树节点的定义

template <typename T>
class CBinNode
{
private:
    T data;
    CBinNode *parent, *lChild, *rChild;
public:
    CBinNode() : parent(0), lChild(0), rChild(0), data(0) {};
    CBinNode(const T data, CBinNode<T> *parent = 0, CBinNode<T> *lc = 0, CBinNode<T> *rc = 0)
        : data(data), parent(parent), lChild(lc), rChild(rc) {};
    ~CBinNode();

    T getData() const { return data; }
    CBinNode<T>* getParent() const { return parent; }
    CBinNode<T>* getLChild() const { return lChild; }
    CBinNode<T>* getRChild() const { return rChild; }

    void setLChild(CBinNode<T>* node);
    void setRChild(CBinNode<T>* node);

    // 作为左节点插入
    CBinNode<T>* insertAsLChild(const T&);
    // 作为右节点插入
    CBinNode<T>* insertAsRChild(const T&);

    // 总结点数
    int size() const;
    // 树的深度
    int height() const;
    // 叶子节点数
    int leaf() const;

    // 是否为根节点
    bool isRoot() const;
    // 是否为叶子节点
    bool isLeaf() const;
    // 是否为左子节点
    bool isLChild() const;
    // 是否为右子节点
    bool isRChild() const;
    // 是否有左子节点
    bool hasLChild() const;
    // 是否有右子节点
    bool hasRChild() const;
    // 是否有子节点
    bool hasChild() const;
    // 是否有两个子节点
    bool hasTwoChild() const;
};

template <typename T>

class CBinNode

{

private:

T data;

CBinNode *parent, *lChild, *rChild;

public:

CBinNode() : parent(0), lChild(0), rChild(0), data(0) {};

CBinNode(const T data, CBinNode<T> *parent = 0, CBinNode<T> *lc = 0, CBinNode<T> *rc = 0)

: data(data), parent(parent), lChild(lc), rChild(rc) {};

~CBinNode();

T getData() const { return data; }

CBinNode<T>* getParent() const { return parent; }

CBinNode<T>* getLChild() const { return lChild; }

CBinNode<T>* getRChild() const { return rChild; }

void setLChild(CBinNode<T>* node);

void setRChild(CBinNode<T>* node);

// 作为左节点插入

CBinNode<T>* insertAsLChild(const T&);

// 作为右节点插入

CBinNode<T>* insertAsRChild(const T&);

// 总结点数

int size() const;

// 树的深度

int height() const;

// 叶子节点数

int leaf() const;

// 是否为根节点

bool isRoot() const;

// 是否为叶子节点

bool isLeaf() const;

// 是否为左子节点

bool isLChild() const;

// 是否为右子节点

bool isRChild() const;

// 是否有左子节点

bool hasLChild() const;

// 是否有右子节点

bool hasRChild() const;

// 是否有子节点

bool hasChild() const;

// 是否有两个子节点

bool hasTwoChild() const;

};

1.2 二叉树节点的实现

1.2.1 析构函数

对于一个即将被删除的节点，除了删除本身之外，应该把子节点也删掉。

template<typename T>
CBinNode<T>::~CBinNode()
{
    // 移除左节点及其下属节点
    if (lChild) {
        delete lChild;
        //delete tmp;
    }

    // 移除右节点极其下属节点
    if (this->hasRChild()) {
        CBinNode<T> * tmp = rChild;
        delete tmp;
    }

    lChild = 0;
    rChild = 0;
    parent = 0;
}

template<typename T>

CBinNode<T>::~CBinNode()

{

// 移除左节点及其下属节点

if (lChild) {

delete lChild;

//delete tmp;

}

// 移除右节点极其下属节点

if (this->hasRChild()) {

CBinNode<T> * tmp = rChild;

delete tmp;

}

lChild = 0;

rChild = 0;

parent = 0;

}

1.2.2 获取节点信息

// 求当前结点的度
template<typename T>
int CBinNode<T>::size() const {
    return this == 0 ? 0 : 1 + lChild->size() + rChild->size();
}

// 求高度
template<typename T>
inline int CBinNode<T>::height() const {
    if (!this) return 0;
    int lLen = 0, rLen = 0;
    // 高度取左右节点中更大的一个即可
    if (lChild) lLen = 1 + lChild->height();
    if (rChild) rLen = 1 + rChild->height();
    return lLen > rLen ? lLen : rLen;
}

// 求叶子节点数
template<typename T>
inline int CBinNode<T>::leaf() const {
    if (!this) return 0;
    // 只有没有左右子节点才算叶子结点
    if (!lChild && !rChild) return 1;
    return lChild->leaf() + rChild->leaf();
}

// 求当前结点的度

template<typename T>

int CBinNode<T>::size() const {

return this == 0 ? 0 : 1 + lChild->size() + rChild->size();

}

// 求高度

template<typename T>

inline int CBinNode<T>::height() const {

if (!this) return 0;

int lLen = 0, rLen = 0;

// 高度取左右节点中更大的一个即可

if (lChild) lLen = 1 + lChild->height();

if (rChild) rLen = 1 + rChild->height();

return lLen > rLen ? lLen : rLen;

}

// 求叶子节点数

template<typename T>

inline int CBinNode<T>::leaf() const {

if (!this) return 0;

// 只有没有左右子节点才算叶子结点

if (!lChild && !rChild) return 1;

return lChild->leaf() + rChild->leaf();

}

1.2.3 插入操作

template<typename T>
CBinNode<T>* CBinNode<T>::insertAsLChild(const T& x) {
    if (!this) return 0;
    // 删除所有的左节点
    if (lChild) delete lChild;
    return lChild = new CBinNode(x, this);
}

template<typename T>
CBinNode<T>* CBinNode<T>::insertAsRChild(const T& x)
{
    if (!this) return 0;
    // 删除所有的右节点
    if (rChild) delete rChild;
    return rChild = new CBinNode(x, this);
}

template <typename T>
void CBinNode<T>::setLChild(CBinNode<T> *node) {
    if (!this) return 0;
    if (lChild) delete lChild;
    lChild = node;
}

template <typename T>
void CBinNode<T>::setRChild(CBinNode<T> *node) {
    if (!this) return 0;
    if (rChild) delete rChild;
    rChild = node;
}

template<typename T>

CBinNode<T>* CBinNode<T>::insertAsLChild(const T& x) {

if (!this) return 0;

// 删除所有的左节点

if (lChild) delete lChild;

return lChild = new CBinNode(x, this);

}

template<typename T>

CBinNode<T>* CBinNode<T>::insertAsRChild(const T& x)

{

if (!this) return 0;

// 删除所有的右节点

if (rChild) delete rChild;

return rChild = new CBinNode(x, this);

}

template <typename T>

void CBinNode<T>::setLChild(CBinNode<T> *node) {

if (!this) return 0;

if (lChild) delete lChild;

lChild = node;

}

template <typename T>

void CBinNode<T>::setRChild(CBinNode<T> *node) {

if (!this) return 0;

if (rChild) delete rChild;

rChild = node;

}

1.2.4 其他属性操作

template<typename T>
bool CBinNode<T>::isRoot() const {
    return parent == 0;
}

template<typename T>
bool CBinNode<T>::isLeaf() const {
    return (lChild == 0 && rChild == 0);
}

template<typename T>
bool CBinNode<T>::isLChild() const {

    return parent == 0 ? false : this == parent->getLChild();
}

template<typename T>
bool CBinNode<T>::isRChild() const {
    return parent == 0 ? false : this == parent->getRChild();
}

template<typename T>
bool CBinNode<T>::hasLChild() const {
    return lChild != 0;
}

template<typename T>
bool CBinNode<T>::hasRChild() const {
    return rChild != 0;
}

template<typename T>
bool CBinNode<T>::hasChild() const {
    return (lChild || rChild);
}

template<typename T>
bool CBinNode<T>::hasTwoChild() const {
    return (lChild && rChild);
}

template<typename T>

bool CBinNode<T>::isRoot() const {

return parent == 0;

}

template<typename T>

bool CBinNode<T>::isLeaf() const {

return (lChild == 0 && rChild == 0);

}

template<typename T>

bool CBinNode<T>::isLChild() const {

return parent == 0 ? false : this == parent->getLChild();

}

template<typename T>

bool CBinNode<T>::isRChild() const {

return parent == 0 ? false : this == parent->getRChild();

}

template<typename T>

bool CBinNode<T>::hasLChild() const {

return lChild != 0;

}

template<typename T>

bool CBinNode<T>::hasRChild() const {

return rChild != 0;

}

template<typename T>

bool CBinNode<T>::hasChild() const {

return (lChild || rChild);

}

template<typename T>

bool CBinNode<T>::hasTwoChild() const {

return (lChild && rChild);

}

二、树的实现

树的结构非常简单，包含一个节点作为根就行，其他的节点大多都都间接调用节点接口。

#include"BinNode.h"
using namespace std;

template <typename T>
class CTree {
public:
    CTree();
    ~CTree();
    CTree(T data);
    CTree(CBinNode<T> *root);

    int size() const;
    int height() const;
    int leaf() const;
    // 作为根节点插入
    CBinNode<T>* insertAtRoot(T data);
    // 作为左节点插入
    CBinNode<T>* insertNodeAtLeft(CBinNode<T>*node, T data);
    // 作为右节点插入
    CBinNode<T>* insertNodeAtRight(CBinNode<T>*node, T data);
    // 移除节点
    CBinNode<T>* removeNode(CBinNode<T>* node);
private:
    CBinNode<T> *root;
};

template<typename T>
inline CTree<T>::CTree() :root(0) {
}

template<typename T>
inline CTree<T>::~CTree() {
    if (!root) return;
    delete root;
}

template<typename T>
inline CTree<T>::CTree(T data) {
    root = new CBinNode<T>(data);
}

template<typename T>
CTree<T>::CTree(CBinNode<T> *root) : root(root) {
}

template<typename T>
CBinNode<T>* CTree<T>::insertAtRoot(T data) {
    if (root) return;
    root = new CBinNode<T>(data);
}

template<typename T>
CBinNode<T>* CTree<T>::insertNodeAtLeft(CBinNode<T>* node, T data) {
    if (!node || !root) return 0;
    node->insertAsLChild(data);
}

template<typename T>
CBinNode<T>* CTree<T>::insertNodeAtRight(CBinNode<T>* node, T data) {
    if (!node || !root) return 0;
    node->insertAsLChild(data);
}

template<typename T>
inline int CTree<T>::size() const
{
    return !root ? 0 : root->size();
}

template<typename T>
inline int CTree<T>::height() const {
    return root->height();
}

template<typename T>
inline int CTree<T>::leaf() const {
    return root->leaf();
}

template<typename T>
inline CBinNode<T>* CTree<T>::removeNode(CBinNode<T>* node)
{
    if (!node) return 0;
    if (root != node && node->getParent()) {
        CBinNode<T>* p = node->getParent();
        if (node == p->getLChild()) p->setLChild(0);
        if (node == p->getRChild()) p->setRChild(0);
    }
    delete node;
}

#include"BinNode.h"

using namespace std;

template <typename T>

class CTree {

public:

CTree();

~CTree();

CTree(T data);

CTree(CBinNode<T> *root);

int size() const;

int height() const;

int leaf() const;

// 作为根节点插入

CBinNode<T>* insertAtRoot(T data);

// 作为左节点插入

CBinNode<T>* insertNodeAtLeft(CBinNode<T>*node, T data);

// 作为右节点插入

CBinNode<T>* insertNodeAtRight(CBinNode<T>*node, T data);

// 移除节点

CBinNode<T>* removeNode(CBinNode<T>* node);

private:

CBinNode<T> *root;

};

template<typename T>

inline CTree<T>::CTree() :root(0) {

}

template<typename T>

inline CTree<T>::~CTree() {

if (!root) return;

delete root;

}

template<typename T>

inline CTree<T>::CTree(T data) {

root = new CBinNode<T>(data);

}

template<typename T>

CTree<T>::CTree(CBinNode<T> *root) : root(root) {

}

template<typename T>

CBinNode<T>* CTree<T>::insertAtRoot(T data) {

if (root) return;

root = new CBinNode<T>(data);

}

template<typename T>

CBinNode<T>* CTree<T>::insertNodeAtLeft(CBinNode<T>* node, T data) {

if (!node || !root) return 0;

node->insertAsLChild(data);

}

template<typename T>

CBinNode<T>* CTree<T>::insertNodeAtRight(CBinNode<T>* node, T data) {

if (!node || !root) return 0;

node->insertAsLChild(data);

}

template<typename T>

inline int CTree<T>::size() const

{

return !root ? 0 : root->size();

}

template<typename T>

inline int CTree<T>::height() const {

return root->height();

}

template<typename T>

inline int CTree<T>::leaf() const {

return root->leaf();

}

template<typename T>

inline CBinNode<T>* CTree<T>::removeNode(CBinNode<T>* node)

{

if (!node) return 0;

if (root != node && node->getParent()) {

CBinNode<T>* p = node->getParent();

if (node == p->getLChild()) p->setLChild(0);

if (node == p->getRChild()) p->setRChild(0);

}

delete node;

}

数据结构之树：二叉树的实现

一、二叉树节点实现

1.1 二叉树节点的定义

1.2 二叉树节点的实现

二、树的实现

144-二叉树的前序遍历

二叉树的后序遍历

二叉树的先序遍历

数据结构之栈（三）：顺序栈实现

POJ1220-NUMBER BASE CONVERSION（任意进制转换）

[leetcode]199-二叉树的右视图

【每日打卡】[leetcode]72-编辑距离

【每日打卡】[leetcode]460-LFU缓存

[leetcode]125-验证回文串

【每日打卡】[程序员面试宝典]17.16-按摩师

【每日打卡】[leetcode]876-链表的中间节点

【每日打卡】[剑指offer]面试题40-最小的k个数

【每日打卡】[leetcode]-409最长回文子串

【每日打卡】[leetcode]面试题1.6-字符串压缩

加载中...

发表评论

热门搜索

一、二叉树节点实现

1.1 二叉树节点的定义

1.2 二叉树节点的实现

二、树的实现

发表评论