C++二叉树的创建与一些基本使用
这里写目录标题
- C++二叉树的一些基本使用
C++二叉树的一些基本使用
二叉树的基本组成
结构体和类的构造和使用方法非常像，所以，在C++中，结构体也存在无参和有参构造；可以根据自己的需求来定义。
struct BiNode{ int val; BiNode *lchild,*rchild; //BiNode() : val(0), lchild(nullptr), rchild(nullptr) {} // BiNode(int x) : val(x), lchild(nullptr), rchild(nullptr) {} // BiNode(int x, BiNode *lchild, BiNode *rchild) : val(x), lchild(lchild), rchild(rchild) {}};创建二叉树
这里我是通过队列的方式来创建二叉树的
每创建一个节点，就拿出一个数
void CreateTree(BiNode* &root,queue<int>& dp){ //通过队列创建二叉树 if(dp.empty()) return ; int n=dp.front(); dp.pop(); if(n==0){ //等于0时，就是空节点 return; } else{ root =new BiNode(); root->val=n; CreateTree(root->lchild,dp); CreateTree(root->rchild,dp); }}二叉树的4种常用遍历
先序遍历
void preOrder(BiNode* root){ //前序遍历 if(root){ cout<<root->val<<" "; preOrder(root->lchild); preOrder(root->rchild); }}中序遍历
void inOrder(BiNode* root){ //中序遍历 if(root!=NULL){ inOrder(root->lchild); cout<<root->val<<" "; inOrder(root->rchild); }}后序遍历
void postOrder(BiNode* root){ //后序遍历 if(root){ postOrder(root->lchild); postOrder(root->rchild); cout<<root->val<<" "; }}层序遍历
前面的三种先、中、后遍历方法，很常用，也很简单，基本上学会了其中一种，另外两种自然也就会了，只要调换一下位置就行了，原理非常简单；
第四种方法：层序遍历，也是非常的常用，使用的场景也很多，我这里是使用两重vector容器，把它的每一层都单独放在一起，在一般的做题或者其他场景，不需要这么细致的话，使用一维vector也是一样的。
vector<vector<int>> levelOrder(BiNode*& root) { //层序遍历 vector<vector<int>> res; if(root==NULL) return res;queue<BiNode*> dp; dp.push(root); while(!dp.empty()){ //如果队列为空，则已经遍历完毕 int n=dp.size(); //获取队列的大小，也就是这一层的节点数 res.push_back(vector<int> ()); for(int i=1;i<=n;i++){ //每一次都把这一层的所有节点输出，遍历完这一层的，队列剩下的就是下一层的 auto p=dp.front();dp.pop(); res.back().push_back(p->val); if(p->lchild) dp.push(p->lchild); //把非空的节点加入队列 if(p->rchild) dp.push(p->rchild); } } return res;}在二叉树中查找值为val的节点
思路：
1、当root == NULL； return NULL;
2、当root->val ==num； return root;
3、当root->val!=num ； 则先去左子树中找,FindNode(root->lchild,num);
4、以上都不满足，则去右子树找
BiNode* FindNode(BiNode* &root,int num){ BiNode* p; if(!root) return NULL;//节点为空 else if (root->val==num) return root; else{ p=FindNode(root->lchild,num); if(p){ return p; } else{ return FindNode(root->rchild,num); } }}二叉树的高度（深度）
直接递归左右子树，比大小
int HeightTree(BiNode* root){ if(!root) return 0; return max(HeightTree(root->lchild),HeightTree(root->rchild))+1;}查找二叉树中的叶子节点
通过叶子节点性质，直接查找左右子节点都为空的节点，把它加入进vector数组
void FindLeaf(BiNode* &root,vector<BiNode*> &leafnode){ if(root){ if(!root->lchild && !root->rchild){ leafnode.push_back(root); return; } if(root->lchild) FindLeaf(root->lchild,leafnode); if(root->rchild) FindLeaf(root->rchild,leafnode); }}以上就是本次介绍的关于二叉树的创建以及一些基本的使用
这是本次演示所使用的二叉树，下面附上一下演示的代码
#include#includeusing namespace std;#includestruct BiNode{ int val; BiNode *lchild,*rchild; //BiNode() : val(0), lchild(nullptr), rchild(nullptr) {} // BiNode(int x) : val(x), lchild(nullptr), rchild(nullptr) {} // BiNode(int x, BiNode *lchild, BiNode *rchild) : val(x), lchild(lchild), rchild(rchild) {}};void CreateTree(BiNode* &root,queue<int>& dp); //创建二叉树void preOrder(BiNode* root); //先序遍历void inOrder(BiNode* root); //中序遍历void postOrder(BiNode* root); //后序遍历vector<vector<int>> levelOrder(BiNode*& root); //层序遍历，一层层的输出//template BiNode* FindNode(BiNode* &root,int val); //查找值为val 的结点，找到了返回该节点地址，没找到则返回NULLint HeightTree(BiNode* root); //求二叉树的高度(深度)void FindLeaf(BiNode* &root,vector<BiNode*> &leafnode); //查找到叶子节点，并输出//中间的函数在上面，就不再写了int main(){ BiNode* root; queue<int> dp; dp.push(1); dp.push(2); dp.push(4); dp.push(0); dp.push(6); dp.push(0); dp.push(0); dp.push(0); dp.push(3); dp.push(0); dp.push(5); dp.push(0); dp.push(0); //创建二叉树 CreateTree(root,dp); //先、中、后三中遍历 cout<<"preOrder: "<<endl; preOrder(root); cout<<"\ninOrder: "<<endl; inOrder(root); cout<<"\npostOrder: "<<endl; postOrder(root); cout<<"\nlevelOrder: "<<endl;//层序遍历，一层层的输出 vector<vector<int>> res=levelOrder(root); for(auto &ch:res){ //一层一层的输出 for(auto &num:ch){ cout<<num<<" "; } cout<<endl; }//查找指定节点，这里我是没有定义，直接给了一个固定值10，纯属是为了演示 BiNode* findnode; findnode=FindNode(root,10); if(findnode){ cout<<"findnode->val="<<findnode->val<<endl; } else{ cout<<"This node does not exist in this binary tree! "<<endl; }//定义了一个ans,接收该二叉树的高度 int ans=HeightTree(root); cout<<"The height of the binary tree is "<<ans<<endl;//查找该二叉树的叶子节点，并输出 vector<BiNode*> leafnode(dp.size()); FindLeaf(root,leafnode); for(auto& leaf:leafnode){ cout<<leaf->val<<" "; } cout<<endl;}疑问，希望有大佬能够帮忙解惑！
以上便是我本次学习所得，不过有一个疑问，
在我用struct定义二叉树的基本结构的时候，如果我写了无参构造
BiNode() : val(0), lchild(nullptr), rchild(nullptr) {}那么我在创建二叉树的时候，无论是
BiNode* root =new BiNode();亦或是
BiNode* root =new BiNode;都可以运行，且得出的答案都一样，
但如果我不写这个无参构造
那么第二种定义，在vscode中，虽然不会报错，但不会得出答案，便直接结束了。在网上找了很久，依然没有找到，希望有懂得大佬看到了能帮忙解惑，先谢谢了！