这两天回顾了二叉树的上和下的算法专栏,先用这篇博客来记录我的学习笔记。
本.txt,我将再一次学习二叉树这种数据结构! 前面我们都只是讲了线性表结构而已,比如:栈和队列等数据结构。那么今天我们将来讲解一种非线性表结构---树! 树这种数据结构比线性表的数据结构要复杂得多!内容也比较多,因此专栏的王老师分为了4节课去讲解! 二叉树的存储方式主要有2种方式,分别是 链式存储 和 顺序存储 所谓的链式存储其实就是用链表list来do树这种数据结构! 所谓的顺序存储其实就是用数组arr来do树这种数据结构! e / a b / / c d i f 这里的每个元素我们都叫做是节点,用来连接相邻节点之间的关系 我们就叫做“父子关系” 树的一些基本概念(必须掌握): 1-父节点:e是a和b的父亲节点 2-子节点:a和b都是e的子节点 3-兄弟节点:父亲节点都是同一个的结点就互称之为兄弟节点。比如:a和b的父节点都是e,因此a和b之间互称为兄弟节点 4-根节点:没有父亲节点的结点就称之为根节点,比如e就是根节点 5-叶子节点(叶节点):没子节点的结点就称之为叶子节点,比如c d i f都是叶子节点 (用生活中的例子来记忆这种数据结构的特点,非常快!) 6-节点的高度:(类比生活中你判断一栋大楼的高度是多少,我们就从第0层开始计算,从下往上计算!) 7-节点的深度:(类比生活中你判断水下的鱼在哪个水深(深度)处,是从水平面为0开始计算,从上往下计算!) 8-节点的层数:(和节点深度的计算差不多,只不过层数是从1开始计算的,也是从上往下计算,比如根节点的层数就是1) 9-树的高度:== 跟节点的高度 == 最大层数-1 例子: 高度 深度 层 这个树的高度== 3 o ---> 3 0 1 / o o ---> 2 1 2 / / o o o o ---> 1 2 3 / / o o o ---> 0 3 4 树的结构多种多样,不过我们最常用的还是二叉树! 二叉树(binary tree) :二叉树,顾名思义,就是每一个节点最多有2个“叉”,也就是有2个子节点,分别是 左子节点 和 右子节点 。不过,二叉树并不要求每个节点都有2个子节点,有的结点只有左子节点 而有的结点则只有右子节点。下面这3个图都是二叉树的三种常见的例子! 二叉树的分类: 1-普通二叉树:一般二叉树都是普通二叉树 2-满二叉树:叶子节点全部都在最底层,并且除了叶子节点外,每个节点都有左右2个子节点 3-完全二叉树:作为完全二叉树必须要满足2个特点: ①除了最底层外,其他层节点个数达到最大(也即除去最底层后这个二叉树会变成满二叉树的意思!) ②最底层的叶子节点从左边依次排列过来,并且中间没有断开过 完全二叉树 和 满二叉树 是比较适合于用数组做顺序存储的!因为它们的节点数目都比较多,不会浪费数组的存储空间 除了0下标外,其他的元素都可以按顺序的按照索引来存储。 而其他类型的二叉树就比较适合用链表来do存储了! o / o o / / o o / o o / o o (1) (这是普通的二叉树!) o / o o / / o o o o / / / / o o o o o o o o (2) (满二叉树:是满二叉树的一种特殊的case!!!) o / o o / / o o o o / / o o o (3)(完全二叉树) o / o o / / o o o o / / o o o (4) (这就是个普通的二叉树,非完全二叉树,因为虽然满足除了最底层外其他层的节点个数达到最大) (但是最底层的叶子节点们的节点是断开过的,并不连续!) 那么下面我们就来实现一下一棵二叉树: 我们有2种方法: 一种是基于指针or引用的二叉链式存储法(一个节点有3份字段,一份存data,另外2份分别存储指向左右子节点的指针) 一种是基于数组的顺序存储法!(下标为0的空间会浪费掉,用下标为1的空间来存储根节点root,然后用2*i的下标位置存储左子节点,用2*i+1的下标位置存储右子节点) 我们先来看比较简单和直观的 链式存储法: 所谓的二叉树的链式存储法,其实就是:一个节点有3个字段,一个存储data,另外2个是分别指向其左右节点的指针! 比如: data / left right / data data / / left right left right 我们再来看不那么直观的 数组存储法:我们会用一个数组来存储二叉树种的all的节点元素 其中,浪费一个下标为0的数组空间,然后用下标为1的空间存储二叉树的根节点,然后用2*1 = 2的位置存储它的左子节点 然后用2*1+1 = 3的位置来存储它的右子节点,用2*2=4的位置存储根节点的左字节点的左子节点,用2*2+1=5的位置存储根节点的右子节点 的右子节点,然后以此类推。 比如: (1) a / b(2) c(3) / / d(4) e(5) f(6) g(7) ......................以此类推! [] [a] [b] [c] [d] [e] [f] [g] ....[] [] [] [] 0 1 2 3 4 5 6 7 8 9 10 11 当然,这仅仅是把完全二叉树用数组的存储方式表示出来,如果你是一个普通一点的二叉树甚至是单臂树的话,这样就会非常的浪费存储空间! so: 总结: 如果是满二叉树或者是完全二叉树的话,那么用数组的存储方式来表示是完全没问题的,也无疑是最节省内存的一种方式 ,但是对于别的形式的二叉树,一般我们都是用链式存储方式来存储的! 当然我们学习到 堆和堆排序时,你就会发现, 堆其实就是一种完全二叉树,其最常用的存储方式就是数组 下面我们来看二叉树中非常重要的 *** 作,也即二叉树的遍历,这也是非常常见的面试题! 我们如何将所有的节点都遍历打印出来呢? 经典的方法有3种: 前序遍历、中序遍历和后序遍历 其中,何为之前序中序和后序呢?其实就是表示:节点与它的左右子树节点遍历打印的先后顺序! 1-前序遍历:对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树 (本身 左 右) 2-中序遍历:对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后才打印它的右子树(左 本身 右) 3-后序遍历:对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后再打印这个节点本身(左 右 本身) 从以上的概念中,你就可以清晰的认识到所谓的前中后序遍历是啥意思了, -前序就是要本身在前,左右在后 -中序就是要本身在左右的中间 -后序就是要本山在最后,左右在前 (实际上呢,二叉树的前中后序遍历其实就是一个递归的过程。比如:前序遍历,其实就是先打印根节点,然后再递归地打印左子树,最后递归地打印右子树) (上面这个本质的思想一定要建立起来!不能有所含糊,不然你就会搞不懂怎么对二叉树进行前中后序的遍历了!) 而写递归代码的关键,其实就是看你能不能写出递归的递推公式!以及递归的终止条件了。 写递归的递推公式的关键就是,如果要解决问题a,就假设子问题b和c已经被解决了,然后再来看如何利用b和c来deal问题a 比如下面来几个例子(帮助我理解一下这几个概念): 前序遍历: a / b c / / d e f g result: a->b->d->e->c->f->g 中序遍历: 1 / -2 3 / / -3 -1 2 4 result: -3 -> -2 -> -1 -> 2 -> 3 -> 4 从这里我们可以看出来对于二叉树的中序遍历,可以输出有序(升序)的数据序列,且时间复杂度为O(n),这是非常高效的! 因此二叉查找树也被称之为二叉排序树。 后序遍历: a / b c / / d e f g result: d->e->b->f->g->c->a 前面我们学习了树、二叉树、二叉树的遍历,那么今天我们再来学习一种特殊的二叉树---二叉查找树。 二叉查找树之最大的特点就是:支持动态数据集合的快速插入、删除、查找 *** 作。 我们之前说过,散列表也是支持这些 *** 作的,并且散列表的这些 *** 作比二叉查找树更加地高效,且时间复杂度为O(1). 那么既然有了这么高效的散列表,使用二叉树的地方是不是都可以替换成散列表呢?有没有哪些地方是散列表所do不了的呢? 有什么地方是必须要使用二叉树来do的呢? 二叉查找树(也称之为二叉搜索树或者说二叉排序树):Binary Search Tree 二叉查找树是二叉树中最为常用的一种类型,也叫做二叉搜索树。顾名思义呢,二叉查找树是为了实现快速查找而生的。 只不过呢,它不仅仅是支持快速查找一个数据这一种 *** 作的,它还支持快速的插入、删除一个数据。它是怎么做到这些的呢? 二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树中的每个节点的值都大于这个节点的值。 就比如: 13 16 10 / / / 10 16 10 9 14 / / / / 9 11 14 9 13 13 16 (1) / / 11 14 11 (2) (3)
下面是我根据理论知识手动敲出来的二叉查找树的代码:
MyTreeNode.hpp:
#ifndef MYTREENODE #define MYTREENODE #includeusing namespace std; template class MyTreeNode//无prevFather节点的二叉搜索树! { public: typedef MyTreeNode Node; T data; Node* left; Node* right; public: //构造函数 MyTreeNode() :data(0), left(nullptr), right(nullptr) {} MyTreeNode(T d) :data(d), left(nullptr), right(nullptr) {} MyTreeNode(T d, Node* l, Node* r) :data(d), left(l), right(r) {} //拷贝构造函数 MyTreeNode(const Node*& node) { this->data = node->data; this->left = new Node(node->left->data,node->left->left,node->right->right); this->right = new Node(node->right->data, node->right->left, node->right->right); } //拷贝赋值函数 Node*& operator=(const Node*& node) { Node* tempNode = new Node; tempNode->data = node->data; tempNode->left = new Node(node->left->data, node->left->left, node->right->right); tempNode->right = new Node(node->right->data, node->right->left, node->right->right); return tempNode; } }; #endif // !MYTREENODE
MyBinSearchTree.hpp:
#ifndef MYBINSEARCHTREE #define MYBINSEARCHTREE #include#include"MyTreeNode.hpp" using namespace std; template class MyBinSearchTree//无prevFather节点的二叉搜索树! { public: typedef MyTreeNode Node; Node* root; public: //构造函数 MyBinSearchTree() :root(nullptr) {} MyBinSearchTree(T rootData) { this->root = new Node;//对于树的根节点,当你创建一颗树的时候就必须要new一个root了! this->root->data = rootData; } //创建一个二叉查找树的函数 void createMyTree(T val, Node* &temp); //二叉查找树的find查找的函数 MyTreeNode * find(T val); //二叉查找树的insert插入节点的函数 bool insert(T val); void findPreFatherOfP(MyTreeNode * & pPrev, MyTreeNode * &p, T val); //二叉查找树的delete节点的函数 bool deleteNode(T val); //前序遍历 void preOrder(Node* tree); //中序遍历 void middleOrder(Node* tree); //后序遍历 void lastOrder(Node* tree); }; //二叉查找树的find查找的函数 template MyTreeNode * MyBinSearchTree ::find(T val) { Node* temp = this->root; while (temp != nullptr) { if (val == temp->data) { return temp; } if (val < temp->data) { temp = temp->left; continue; } if (val > temp->data) { temp = temp->right; continue; } } return nullptr;//if都找不到就返回nullptr! } template void MyBinSearchTree ::findPreFatherOfP(MyTreeNode * &pPrev, MyTreeNode * &p,T val) { while (p != nullptr && p->data != val) { pPrev = p; if (val < p->data) { p = p->left; } else if (val > p->data) { p = p->right; } } } //二叉查找树的delete节点的函数 template bool MyBinSearchTree ::deleteNode(T val) { Node* node = MyBinSearchTree ::find(val); if (node == nullptr) { return false; //你 在这一棵二叉查找树中连找都找不到这个元素当然删除失败啦! } //这个元素存在的大case下你才能删除啊对吧? Node* p = this->root; Node* pPrev = nullptr; if (node->left == nullptr && node->right == nullptr) {//小case1:若值等于给定值的这个节点既没有左子树也没有右子树 findPreFatherOfP(pPrev, p, val); //删除元素 if (p->data < pPrev->data) { pPrev->left = nullptr; return true; cout << "删除成功!" << endl; } else if (p->data > pPrev->data) { pPrev->right = nullptr; return true; cout << "删除成功!" << endl; } } if (node->left != nullptr && node->right == nullptr) {//小case2:若值等于给定值的这个节点有左子树但没有右子树 findPreFatherOfP(pPrev, p, val); //删除元素 Node* thisdeleteNode = p; p = p->left; if (p->data < pPrev->data) { pPrev->left = p; } else if (p->data > pPrev->data) { pPrev->right = p; } thisdeleteNode = nullptr; cout << "删除成功!" << endl; return true; } if (node->left == nullptr && node->right != nullptr) { //小case3:若值等于给定值的这个节点没有左子树但有右子树 findPreFatherOfP(pPrev, p, val); //删除元素 Node* thisdeleteNode = p; p = p->right; if (p->data < pPrev->data) { pPrev->left = p; } else if (p->data > pPrev->data) { pPrev->right = p; } thisdeleteNode = nullptr; cout << "删除成功!" << endl; return true; } if (node->left != nullptr && node->right != nullptr) {//小case4:若值等于给定值的这个节点既有左子树也有右子树 findPreFatherOfP(pPrev, p, val); Node* minP = p->right;//保存找待删除节点的右子树中值等于最小值的当前节点 Node* minPP = p;//保存找待删除节点的右子树中值等于最小值的父亲节点 //左子树不为空的case下! if (minP->left != nullptr) { while (minP->left != nullptr) { minPP = minP; minP = minP->left; } p->data = minP->data;//只需要把待删除节点的值赋值为其右子树中的最小值 minPP->left = minP->right; //我不管你当前最小值是否还存在右子树, //我都把他的父亲节点的左子树赋值为该最小值节点的右子树 //(当然,左子树肯定是不存在的,因为最小了,就必须不存在左子树了!否则就不是二叉查找树了啊!) minP = nullptr; cout << "删除成功!" << endl; return true; }//左子树为空的case下! else { if (minP->right != nullptr) { p->data = minP->data;//只需要把待删除节点的值赋值为其右子树中的最小值 minPP->right = minP->right; minP = nullptr; cout << "删除成功!" << endl; return true; } else { p->data = minP->data; minPP->right = nullptr; minP = nullptr; cout << "删除成功!" << endl; return true; } } } return false; } //二叉查找树的insert插入节点的函数 template bool MyBinSearchTree ::insert(T val) { if (MyBinSearchTree ::find(val) != nullptr) { cout << "我的二叉查找树不允许存在重复的"< root; while (temp != nullptr) { if (val < temp->data && temp->left==nullptr) { temp->left = new Node(val); return true; } if (val > temp->data && temp->right == nullptr) { temp->right = new Node(val); return true; } if (val < temp->data && temp->left != nullptr) { temp = temp->left; continue; } if (val > temp->data && temp->right != nullptr) { temp = temp->right; continue; } } return false; } //前序遍历 template void MyBinSearchTree ::preOrder(Node* tree)//中左右 { Node* temp = tree; if (temp != nullptr) { cout << temp->data << endl; } if (temp->left != nullptr) { MyBinSearchTree ::preOrder(temp->left); } if (temp->right != nullptr) { MyBinSearchTree ::preOrder(temp->right); } } //中序遍历 template void MyBinSearchTree ::middleOrder(Node* tree)//左中右 { Node* temp = tree; if (temp->left != nullptr) { MyBinSearchTree ::middleOrder(temp->left); } if (temp != nullptr) { cout << temp->data << endl; } if (temp->right != nullptr) { MyBinSearchTree ::middleOrder(temp->right); } } //后序遍历 template void MyBinSearchTree ::lastOrder(Node* tree)//左右中 { Node* temp = tree; if (temp->left != nullptr) { MyBinSearchTree ::lastOrder(temp->left); } if (temp->right != nullptr) { MyBinSearchTree ::lastOrder(temp->right); } if (temp != nullptr) { cout << temp->data << endl; } } template void MyBinSearchTree ::createMyTree(T val, Node* &temp) { if (temp == nullptr) { cout << "插入成功!" << endl; temp = new Node(val); } else { if (temp->data == val) { cout << "我不允许二叉查找(搜索)树中存在从重复元素!" << endl; } else if (val < temp->data) { createMyTree(val, temp->left); } else if (val > root->data) { createMyTree(val, temp->right); } } } #endif // !MYBINSEARCHTREE
MyBinTree.cpp:
#include#include"MyTreeNode.hpp" #include"MyBinSearchTree.hpp" using namespace std; void createMyTree(MyBinSearchTree * &myTree) { //创建一个二叉树 int val = 0; while (1) { cout << "请输入你要插入的节点的val值:(-999 to quit!)" << endl; cin >> val; if (val == -999) { cout << "结束创建二叉树!" << endl; break; } myTree->createMyTree(val, myTree->root); } } void testMyTree() { int v = 0; cout << "请输入你所要创建的二叉搜索树的root根节点的val值:" << endl; cin >> v; MyBinSearchTree * myTree = new MyBinSearchTree (v); //创建一个二叉树 createMyTree(myTree); //前序遍历 cout << "前序遍历:" << endl; myTree->preOrder(myTree->root); //中序遍历 cout << "中序遍历:" << endl; myTree->middleOrder(myTree->root); //后序遍历 cout << "后序遍历:" << endl; myTree->lastOrder(myTree->root); //查找val值 cout << "查找操作:" << endl; MyTreeNode * t = myTree->find(-6); if (t) { cout << "查找元素:" << t->data << "成功!"< insert(5); if (ret) { cout << "插入5成功!" << endl; } else cout << "插入5失败!" << endl; //用前序遍历来show 一下当前的二叉查找树中的all元素! myTree->preOrder(myTree->root); bool ret2 = myTree->insert(6); if (ret2){ cout << "插入6成功!" << endl; } else cout << "插入6失败!" << endl; //用前序遍历来show 一下当前的二叉查找树中的all元素! myTree->preOrder(myTree->root); //删除值为val的节点 cout << "删除操作:" << endl; bool retDeleteResult = myTree->deleteNode(18); if (retDeleteResult) cout << "删除成功!" << endl; else cout << "删除失败!" << endl; //用前序遍历来show 一下当前的二叉查找树中的all元素! myTree->preOrder(myTree->root); } int main(void) { testMyTree(); system("pause"); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)