首页 > 编程语言 >C++数据结构(树)

C++数据结构(树)

时间:2023-04-26 09:15:14浏览次数:35  
标签:int void BinaryTree C++ BinaryTreeNode 二叉树 数据结构 节点

树是一种递归定义的数据结构,如果树中节点的各子树从左到右是有次序的,不能互换,则称该树为有序树,否则叫无序树。

关于树的节点:

  1. 节点拥有的子树的个数叫做节点的度
  2. 如果度为0,那么该节点叫做叶节点或终端节点,除了根节点外的分支节点称为内部节点
  3. 树的度是各节点度的最大值。节点的子树的根称为该节点的子节点,某个节点只能有一个父节点。
  4. 节点的子树的根称为该节点的子节点
  5. 节点的层次从树根开始计算,树的深度或高度是树中节点的最大层数
  6. 相同父节点的孩子之间互称兄弟节点

二叉树的特点是每个节点最多有两棵子树,这意味着每个节点的度不会大于2,并且是一棵有序树

关于满二叉树:

  1. 所有分支节点都存在左子树和右子树
  2. 所有叶节点都在同一层
  3. 不存在非0或非2的节点
  4. 高度为H,含有(2^H-1)个节点

关于完全二叉树:

  1. 叶节点在最底下两层
  2. 最后一层叶节点都靠左侧排列,除了最后一层,其他层的节点个数达到最大
  3. 倒数第二层如果有叶节点,则叶节点都靠右排列
  4. 如果节点度为 1,则该节点只有左子树,不可以只有右子树。而且最多只有一个度为 1 的节点
  5. 高度为 H,每个节点都与高度为 H 的满二叉树中编号为 1~n 的节点一一对应

由此可见,满二叉树一定是完全二叉树,反之不一定成立

判断完全二叉树:

  1. 按照满二叉树的情形给二叉树的节点逐层编号,编号出现空缺则不是完全二叉树
  2. 一棵满二叉树,依次把编号最大的 1 到多个节点去掉,得到的就是一棵完全二叉树
  3. 如果一个完全二叉树有 n 个节点,当节点的编号≤(n/2) 时,这些节点就是分支节点,而当节点的编号>(n/2) 时,这些节点就是叶节点(n/2 如果没有整除则去掉小数部分)

二叉树的性质:

  1. 在二叉树的第i层上,最多有2^(i-1)个节点
  2. 高度为K的二叉树至多有(2^K-1)个节点
  3. 二叉树节点的总数量等于节点的总度数+1
  4. 对于任何一棵二叉树,如果其叶节点数量为n0,度为 2 的节点数量为n2,则叶节点的数量比有两棵子树的节点数量多一个,即n0=n2+ 1
  5. 具有 n(n>0)个节点的完全二叉树的高度为⌈log2(n+1)⌉ 或者 ⌊log2n⌋ +1。

顺序存储

顺序存储方式用一段连续的内存单元依次从上到下、从左到右存储二叉树各个节点元素

假设存储的是一棵完全二叉树,如果将根节点存储在数组下标i=1的位置,则左子树下标为i*2=2的位置,右子树在3的位置

如果存储的是一棵非完全二叉树,也按照完全二叉树的编号来存储,但会浪费较多的内存空间

#include <iostream>
#include <cmath>

#define MaxSize 100

enum ECCHILDSIGN {
    E_Root,      // 树根
    E_ChildLeft, // 左孩子
    E_ChildRight // 右孩子
};

template <typename T>
struct BinaryTreeNode {
    T data;       // 数据域
    bool isValid; // 节点是否有效
};

template <typename T>
class BinaryTree {
public:
    BinaryTree() {
        for (int i=0;i<=MaxSize;i++) {
            // 初始时节点无效
            SeqBiTree[i].isValid = false;
        }
    }
    ~BinaryTree() {};

public:
    // 创建节点
    int CreateNode(int parindex,ECCHILDSIGN pointSign,const T &e);
    
    // 获取父节点下标
    int getParentIdx(int sonindex) {
        if (ifValidRangeIdx(sonindex) == false) {
            return -1;
        }
        if (SeqBiTree[sonindex].isValid == false) {
            return -1;
        }
        return int(sonindex / 2);
    }

    // 获取指定节点所在高度
    int getPointLevel(int index) {
        if (ifValidRangeIdx(index) == false) {
            return -1;
        }
        if (SeqBiTree[index].isValid == false) {
            return -1;
        }
        int level = int(log(index)/log(2)+1);
        return level;
    }

    // 获取二叉树深度
    int getLevel() {
        if (SeqBiTree[1].isValid == false) {
            return 0;
        }

        int i;
        for (i = MaxSize;i >= 1;i--) {
            // 找到最后一个有效节点
            if (SeqBiTree[i].isValid == true) {
                break;
            }
        }
        return getPointLevel(i);
    }

    // 判断是否为完全二叉树
    bool ifCompleteBT() {
        if (SeqBiTree[1].isValid == false) {
            return false;
        }
        int i;
        for (i = MaxSize;i >= 1;i--) {
            // 找到最后一个节点
            if (SeqBiTree[i].isValid == true) {
                break;
            }
        }
        for (int k = 1;k <= i;k++) {
            // 所有节点有效
            if (SeqBiTree[k].isValid == false) {
                return false;
            }
        }
        return true;
    }

    void preOrder() {
        if (SeqBiTree[1].isValid == false) {
            return;
        }
        preOrder(1);
    }

    void preOrder(int index) {
        if (ifValidRangeIdx(index) == false) {
            return;
        }
        if (SeqBiTree[index].isValid == false) {
            return;
        }
        std::cout << (char)SeqBiTree[index].data << "";
        preOrder(2 * index);
        preOrder(2 * index + 1);
    }

private:
    bool ifValidRangeIdx(int index) {
        if (index < 1 || index > MaxSize) {
            return false;
        }
        return true;
    }
private:
    BinaryTreeNode<T> SeqBiTree[MaxSize + 1];
};

template <class T>
int BinaryTree<T>::CreateNode(int parindex,ECCHILDSIGN pointSign,const T &e) {
    if (pointSign != E_Root) {
        if (ifValidRangeIdx(parindex) == false) {
            return -1;
        }
        if (SeqBiTree[parindex].isValid == false) {
            return -1;
        }
    }

    int index = -1;
    if (pointSign == E_Root) {
        index = 1; // 根节点下标为1
    } else if (pointSign == E_ChildLeft) {
        // 左孩子
        index = 2 * parindex;
        if (ifValidRangeIdx(index) == false) {
            return -1;
        }
    } else {
        // 右孩子
        index = 2 * parindex + 1;
        if (ifValidRangeIdx(index) == false) {
            return -1;
        }
    }
    SeqBiTree[index].data = e;
    // 标记该下标中有效数据
    SeqBiTree[index].isValid = true;
    return index;
}

int main(void) {
    BinaryTree<int> tree;
    int indexRoot = tree.CreateNode(-1,E_Root,'A');
    int indexNodeB = tree.CreateNode(indexRoot,E_ChildLeft,'B');
    int indexNodeC = tree.CreateNode(indexRoot,E_ChildRight,'C');

    int indexNodeD = tree.CreateNode(indexNodeB,E_ChildLeft,'D');
    int indexNodeE = tree.CreateNode(indexNodeC,E_ChildRight,'E');

    int iParentIndexE = tree.getParentIdx(indexNodeE);
    std::cout << "node E parent node index: " << iParentIndexE << std::endl;

    int iLevel = tree.getPointLevel(indexNodeD);
    std::cout << "the height of node D: " << iLevel << std::endl;

    iLevel = tree.getPointLevel(indexNodeE);
    std::cout << "the height of node E: " << iLevel << std::endl;
    std::cout << "the depth of binary tree: " << tree.getLevel() << std::endl;
    std::cout << "compelete binary tree: " << tree.ifCompleteBT() << std::endl;

    std::cout << "-----------------" << std::endl;
    std::cout << "preorder: ";
    tree.preOrder();

    return 0; 
}

链式存储

链式存储要存储额外的左右子节点,多用于存储普通的二叉树

#include <iostream>

enum ECCHILDSIGN {
    E_Root,       // 树根
    E_ChildLeft,  // 左孩子
    E_ChildRight  // 右孩子
};

template <typename T>
struct BinaryTreeNode {
    T data;  // 数据域
    BinaryTreeNode *leftChild;
    BinaryTreeNode *rightChild;
};

template <typename T>
class BinaryTree {
public:
    BinaryTree();
    ~BinaryTree();
public:
    // 创建节点
    BinaryTreeNode<T> *CreateNode(BinaryTreeNode<T> *parentnode,ECCHILDSIGN pointSign,const T &e);
    void ReleaseNode(BinaryTreeNode<T> *pnode);  // 释放树节点
    void CreateBTreeAccordPT(char *pstr);  // 前序遍历顺序创建BTree
public:
    // 前序遍历
    void preOrder() {
        preOrder(root);
    }
    void preOrder(BinaryTreeNode<T> *tNode) {
        if (tNode != nullptr) {
            std::cout << (char)tNode->data << " ";
            preOrder(tNode->leftChild);
            preOrder(tNode->rightChild);
        }
    }

    // 中序遍历
    void inOrder() {
        inOrder(root);
    }
    void inOrder(BinaryTreeNode<T> *tNode) {
        if (tNode != nullptr) {
            inOrder(tNode->leftChild);
            std::cout << (char)tNode->data << " ";
            inOrder(tNode->rightChild);
        }
    }

    // 后序遍历
    void postOrder() {
        postOrder(root);
    }
    void postOrder(BinaryTreeNode<T> *tNode) {
        if (tNode != nullptr) {
            postOrder(tNode->leftChild);
            postOrder(tNode->rightChild);
            std::cout << (char)tNode->data << " ";
        }
    }

private:
    BinaryTreeNode<T> *root;
    void CreateBTreeAccordPTRecu(BinaryTreeNode<T>* &tnode,char* &pstr);
};

template <class T>
BinaryTree<T>::BinaryTree() {
    root = nullptr;
}

template <class T>
BinaryTree<T>::~BinaryTree() {
    ReleaseNode(root);
}

template <class T>
void BinaryTree<T>::ReleaseNode(BinaryTreeNode<T> *pnode) {
    if (pnode != nullptr) {
        ReleaseNode(pnode->leftChild);
        ReleaseNode(pnode->rightChild);
    }
    delete pnode;
}

template <class T>
BinaryTreeNode<T> *BinaryTree<T>::CreateNode(BinaryTreeNode<T> *parentnode,ECCHILDSIGN pointSign,const T &e) {
    BinaryTreeNode<T> *tmpnode = new BinaryTreeNode<T>;
    tmpnode->data = e;
    tmpnode->leftChild = nullptr;
    tmpnode->rightChild = nullptr;

    if (pointSign == E_Root) {
        root = tmpnode;
    }
    if (pointSign == E_ChildLeft) {
        parentnode->leftChild = tmpnode;
    } else if (pointSign == E_ChildRight) {
        parentnode->rightChild = tmpnode;
    }
    return tmpnode;
}

template <class T>
void BinaryTree<T>::CreateBTreeAccordPT(char *pstr) {
    CreateBTreeAccordPTRecu(root,pstr);
}

template <class T>
void BinaryTree<T>::CreateBTreeAccordPTRecu(BinaryTreeNode<T> *&tnode,char *&pstr) {
    if (*pstr == '#') {
        tnode = nullptr;
    } else {
        tnode = new BinaryTreeNode<T>;
        tnode->data = *pstr;
        CreateBTreeAccordPTRecu(tnode->leftChild,++pstr);
        CreateBTreeAccordPTRecu(tnode->rightChild,++pstr);
    }
}

int main(void) {
    BinaryTree<int> tree;
    BinaryTreeNode<int> *rootpoint = tree.CreateNode(nullptr,E_Root,'A');
    BinaryTreeNode<int> *subpoint = tree.CreateNode(rootpoint,E_ChildLeft,'B');
    subpoint = tree.CreateNode(subpoint,E_ChildLeft,'D');
    subpoint = tree.CreateNode(rootpoint,E_ChildRight,'C');
    subpoint = tree.CreateNode(subpoint,E_ChildRight,'E');

    // tree.CreateBTreeAccordPT((char*)"ABD###C#E##"); // 直接通过前序遍历创建二叉树

    std::cout << "preorder: ";
    tree.preOrder();
    std::cout << std::endl;

    std::cout << "inorder: ";
    tree.inOrder();
    std::cout << std::endl;

    std::cout << "postorder: ";
    tree.postOrder();
    std::cout << std::endl;
    
    return 0;
}

标签:int,void,BinaryTree,C++,BinaryTreeNode,二叉树,数据结构,节点
From: https://www.cnblogs.com/N3ptune/p/17354591.html

相关文章

  • C++ 多线程并发
    C++参考手册-并发支持库《C++ConcurrencyinAction》https://segmentfault.com/a/1190000040628584?utm_source=sf-similar-articlehttps://zhuanlan.zhihu.com/p/547312117bilibiliC++多线程并发基础入门教程1创建线程C++11之前原生不支持多线程,C++11起逐步引......
  • 什么是数据结构?
    数据结构研究计算机数据间关系,包括数据的逻辑结构和存储结构及其操作。我们接触一种数据结构,一定要掌握这三个方面基本概念1.数据(Data)数据即信息的载体,是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。2.数据元素(DataElement)数据......
  • 初识数据结构
    什么是数据结构,数据结构可以理解为我们规定数据元素之间具有某种关系或规则,程序员根据这些规则能够更好的管理和操作这些数据。数据元素的关系包括三种:线性关系——1:1线性关系即为数据是一对一的关系,即除了开头的数据元素和最后的数据元素,其他如何应该数据元素有......
  • 用Winsock编写服务端和客户端 (C++)
      在这里先向大家推荐一本不错的入门书籍——《TCPIP网络编程》(尹圣雨著),这本书比较贴近实战,是一本不错的网络编程方向的指导用书。如果需要PDF版本,可以后台私信我! 回归正题,我们欲要使用C++实现一个简易的服务端和客户端控制台程序。代码如下:  服务端:/***************......
  • 2023年电子科技大学ACM-ICPC暑假前集训-数据结构
    Preface学校针对大一新生的暑假前集训的第一个专题DS,由于要求集体写题解就顺便把写好的发上来了由于下面都写了题意所以直接看也能有很多收获,当然非电专的学生的话就没法交题了代码的话由于专题还没结束怕放上来然后被CV导致被爆破,所以应该在这周六专题结束后会放上来下面都是......
  • 山东大学数据结构实验七
    卡片游戏tips:这个题还要参考,同学要加油啦~~要求创建队列类,使用数组描述的循环队列实现卡片游戏描述假设桌上有一叠扑克牌,依次编号为1-n(从上至下)。当至少还有两张的时候,可以进行操作:把第一张牌扔掉,然后把新的第一张(原先扔掉的牌下方的那张牌,即第二张牌)放到整叠牌的最后。......
  • C++第四章课后习题4-12
    定义一个datatype类,能处理包含字符型,整形,浮点型3种类型的数据,给出其构造函数。1#include<iostream>2usingnamespacestd;34classDataType{5private:6chara;7intn;8floatx;9enum{10character,11intege......
  • 山东大学数据结构实验六
    计算表达式tips:不要全文复制,会被查重哦注意因为精度问题,请使用double存数据。要求创建栈类,采用数组描述;计算数学表达式的值。输入数学表达式,输出表达式的计算结果。数学表达式由单个数字和运算符+、-、*、/、(、)构成,例如2+3*(4+5)-6/4。假定表达式输入格式合法。格式......
  • PTA1004 成绩排名(C++)
    一、问题描述:读入 n(>0)名学生的姓名、学号、成绩,分别输出成绩最高和成绩最低学生的姓名和学号。输入格式:每个测试输入包含1个测试用例,格式为第1行:正整数n第2行:第1个学生的姓名学号成绩第3行:第2个学生的姓名学号成绩.........第n+1行:第n个学生的......
  • 山东大学数据结构实验一(2)
    题目描述现有一个有n个元素的序列\(a=[a_{1},a_{2},\cdots,a_{n}]\),定义其价值为\(\sum_{i=1}^{n}a_{i}\oplusi\)给出这样一个序列,求其所有排列的价值\(v_{i}\)的或\(v_{1}|v_{2}|\cdots|v_{n-1}|v_{n}\)其中\(|\)为位运算或操作,\(\oplus\)为位运算异......