当前位置: 首页 > news >正文

在discuz做网站免费网站建设平台

在discuz做网站,免费网站建设平台,做网站怎么赚钱 知乎,网站备案被注销的原因二叉树 文章目录 二叉树1. 二叉树的建立(递归创建,结构体指针形式)1.1. 先序建立1.2. 层序建立 2. 递归遍历(结构体指针)2.1. 先序遍历2.2. 中序遍历2.3. 后序遍历 3. 非递归遍历(结构体指针)3.1. 层次遍历3.2. 后序遍历(非递归) 4. 求树的高…

二叉树

文章目录

  • 二叉树
    • 1. 二叉树的建立(递归创建,结构体指针形式)
      • 1.1. 先序建立
      • 1.2. 层序建立
    • 2. 递归遍历(结构体指针)
      • 2.1. 先序遍历
      • 2.2. 中序遍历
      • 2.3. 后序遍历
    • 3. 非递归遍历(结构体指针)
      • 3.1. 层次遍历
      • 3.2. 后序遍历(非递归)
    • 4. 求树的高度
    • 5. 中后序遍历构建
    • 6. 二叉树镜面翻转
    • 7. 对称二叉树
    • 8. 输出所有目标路径
    • 9. 判断是否为子树
    • 10. 合并二叉树
    • 11. 带权路径和

前言:这篇博客需要你对于二叉树有大致的了解,并且对于递归有一定的理解,懂得先序中序后序层次是啥等等,因为在这篇博客我不会对这一些概念进行讲解,我只会将我写的我看见的比较好比较简洁的代码块截下来,并不会对它进行进行过多的讲解,所以如果选择了这一篇博客,就应该做好理解透彻的准备!

1. 二叉树的建立(递归创建,结构体指针形式)

先来给出结构体:

struct Node
{char data;Node* leftchild = nullptr;Node* rightchild = nullptr;
};

1.1. 先序建立

#include<iostream>
#include<string>
using namespace std;
struct Node
{char a;Node* leftchild = nullptr;Node* rightchild = nullptr;
};
class BuildTree
{
public:Node* gen;int i = 0;//遍历arrBuildTree() { gen = nullptr; }void setTree(string arr){gen = new Node;CreateBiTree(gen, arr);return;}// 核心代码void CreateBiTree(Node*& root, string strTree) //先序遍历构建二叉树{char ch;ch = strTree[i++];if (ch == '#'){root = NULL;}else{root = new Node();root->a = ch;CreateBiTree(root->leftchild, strTree);CreateBiTree(root->rightchild, strTree);}return;}
};
int main()
{int n;cin >> n;while (n--){BuildTree* bt = new BuildTree;string arr;cin >> arr;bt->setTree(arr);delete bt;}
}

1.2. 层序建立

#include <iostream>
#include <queue>
#include <string>
using namespace std;struct Node {char data;Node* leftchild;Node* rightchild;
};void pre_view(Node* root)
{if (root != nullptr){cout << root->data << ' ';pre_view(root->leftchild);pre_view(root->rightchild);}return;
}// 层序建立
void CreateBiTree(Node*& root, string strTree) {if (strTree.empty()) {root = nullptr;return;}queue<Node*> nodeQueue;int i = 0;root = new Node();root->data = strTree[i++];nodeQueue.push(root);while (!nodeQueue.empty()) {Node* current = nodeQueue.front();nodeQueue.pop();if (i < strTree.length() && strTree[i] != '#') {current->leftchild = new Node();current->leftchild->data = strTree[i];nodeQueue.push(current->leftchild);}i++;if (i < strTree.length() && strTree[i] != '#') {current->rightchild = new Node();current->rightchild->data = strTree[i];nodeQueue.push(current->rightchild);}i++;}
}int main() {string strTree = "122#3#3";Node* root = nullptr;CreateBiTree(root, strTree);// 先序遍历查看结果pre_view(root);return 0;
}

2. 递归遍历(结构体指针)

2.1. 先序遍历

void pre_send(Node* root)
{if (root != NULL){cout << (root->data);pre_send(root->leftchild);pre_send(root->rightchild);}return;
}

2.2. 中序遍历

void in_sned(Node* root)
{if (root != NULL){in_sned(root->leftchild);cout << (root->data);in_sned(root->rightchild);}return;
}

2.3. 后序遍历

void post_send(Node* root)
{if (root != NULL){post_send(root->leftchild);post_send(root->rightchild);cout << (root->data);}return;
}

3. 非递归遍历(结构体指针)

首先给出结构体:

struct Node
{int a;Node* Leftchild = nullptr;Node* Rightchild = nullptr;
}

3.1. 层次遍历

void levelorder(Node* gen)
{queue<Node*>q;q.push(gen);while (!q.empty()){Node* now = q.front();q.pop();if (now == nullptr)continue;cout << now->a;if (now->Leftchild != nullptr)q.push(now->Leftchild);if (now->Rightchild != nullptr)q.push(now->Rightchild);}
}

3.2. 后序遍历(非递归)

void postRead(Node* gen)
{stack<Node*>s;Node* root = gen, * check = nullptr;while (root != nullptr || !s.empty()){if (root != nullptr)//一直向左走{s.push(root);root = root->Leftchild;}else{root = s.top();//右节点存在且未访问if (root->Rightchild != nullptr && root->Rightchild != check){root = root->Rightchild;s.push(root);root = root->Leftchild;}else{s.pop();cout << root->a;check = root;root = nullptr;}}}
}

4. 求树的高度

int getHeight(Node* root)
{if (root == nullptr)return 0;int leftdeep = getHeight(root->Leftchild);int rightdeep = getHeight(root->Rightchild);int deep = 1 + (leftdeep > rightdeep ? leftdeep : rightdeep);return deep;
}

5. 中后序遍历构建

这个部分是我在做题的时候看到的,感觉搞懂这一块之后会对前中后序有更好的理解,这一道题就是:知道后序的规律!题目名字为:二叉树的中后序遍历构建及求叶子,可以自己搜搜看。

#include<iostream>
#include<cstring>
using namespace std;
class Tree
{
public:int* mid;int* last;int min = 10000000;Tree(int t){mid = new int[t + 5];last = new int[t + 5];for (int i = 0; i < t; i++){cin >> mid[i];}for (int i = 0; i < t; i++){cin >> last[i];}}~Tree(){delete mid, last;}int get_min(){return min;}void BuildTree(int mid_l, int mid_r, int last_l, int last_r){if (mid_l == mid_r){if (mid[mid_l] <= min)min = mid[mid_l];return;}for (int i = mid_l; i <= mid_r; i++){if (mid[i] == last[last_r]){BuildTree(mid_l, i - 1, last_l, last_l + i - mid_l - 1);BuildTree(i + 1, mid_r, last_l + i - mid_l, last_r - 1);}}}
};
int main()
{int n;cin >> n;while (n--){int t;cin >> t;Tree* tree = new Tree(t);tree->BuildTree(0, t - 1, 0, t - 1);cout << tree->get_min() << endl;delete tree;}return 0;
}

6. 二叉树镜面翻转

void Mirror_inversion(Node* p)
{if (p != NULL){Mirror_inversion(p->Leftchild);Mirror_inversion(p->Rightchild);swap(p->Leftchild, p->Rightchild);}
}

7. 对称二叉树

bool judge(Node* root_1, Node* root_2)
{if (root_1 == nullptr && root_2 == nullptr){return true;}else if (root_1 == nullptr || root_2 == nullptr){return false;}else if (root_1->data != root_2->data){return false;}return judge(root_1->leftchild, root_2->rightchild) && judge(root_1->rightchild, root_2->leftchild);
}bool isSymmetric(Node* root)
{return judge(root->leftchild, root->rightchild);
}

8. 输出所有目标路径

void DFS_target(Node* node, int targetSum, vector<int>& path, vector<vector<int>>& result) {if (node == nullptr) {return;}path.push_back(node->data);if (node->leftchild == nullptr && node->rightchild == nullptr) {if (targetSum == node->data) {result.push_back(path);}}else {DFS_target(node->leftchild, targetSum - node->data, path, result);DFS_target(node->rightchild, targetSum - node->data, path, result);}path.pop_back();return;
}

9. 判断是否为子树

bool isSameTree(Node* t1, Node* t2) {// 考虑到后面子叶节点的左右节点,如果都为空就会返回Trueif (!t1 && !t2) {return true;}// 如果有一个节点有左右节点,而另一个节点没有的话就会返回false,而都有不会进入,都没有在上面会返回Trueif (!t1 || !t2) {return false;}return (t1->data == t2->data) && isSameTree(t1->leftchild, t2->leftchild) && isSameTree(t1->rightchild, t2->rightchild);
}// 判断tree1是否包含tree2的子树
bool isSubtree(Node* tree1, Node* tree2) {if (!tree1) {return false;}// tree1不空就开始考虑if (isSameTree(tree1, tree2)) {return true;}// 每一个节点向下进行考虑,如果有一个是符合的就返回Truereturn isSubtree(tree1->leftchild, tree2) || isSubtree(tree1->rightchild, tree2);
}

10. 合并二叉树

void addWith(Node*& root_1, Node* root_2)
{if (root_1 == nullptr && root_2 != nullptr){root_1 = new Node;root_1->data = root_2->data;root_1->leftchild = root_2->leftchild; // Handle left childroot_1->rightchild = root_2->rightchild; // Handle right childreturn;}if (root_2 == nullptr){return;}root_1->data += root_2->data;addWith(root_1->leftchild, root_2->leftchild);addWith(root_1->rightchild, root_2->rightchild);
}

11. 带权路径和

void findDeepTree(Node* root, int* data, int dis)
{if (root == nullptr || index == n){return;}if (root->leftchild == nullptr && root->rightchild == nullptr){result = result + dis * data[index++];return;}if (root->leftchild != nullptr)findDeepTree(root->leftchild, data, dis + 1);if (root->rightchild != nullptr)findDeepTree(root->rightchild, data, dis + 1);return;
}
http://www.mmbaike.com/news/35342.html

相关文章:

  • 制作一个简单网页html南宁百度seo价格
  • 信誉好的企业网站开发市场营销培训
  • 中国it外包公司排名前50上海seo网站优化
  • 邯郸质量一站式服务平台上线互联网广告营销方案
  • 西安网站制作首页拉新十大推广app平台
  • 河北省 政府网站 建设意见下载微信
  • 平顶山市做网站网络代理app
  • 怎么做淘宝客个人网站优化课程设置
  • 上海十大网站建设seo优化网站网页教学
  • 天津做网站外包公司有哪些百度关键词怎么刷上去
  • 区块链网站开发资金网络营销专家
  • 设计型网站云优化seo
  • 如何看一个网站是谁做的友情链接的形式
  • 免费货源在线网站百度应用市场
  • wordpress页面文件济南seo排名搜索
  • 专做宠物的网站百度知道网页版登录入口
  • php做的网站怎么入侵十个有创意的线上活动
  • 保定网站制作策划网站优化方案模板
  • 装修公司做网站好做吗品牌营销策划方案范文
  • 做的最好的美女视频网站云南百度推广开户
  • 网站策划的最终体现是撰写网站策划书网络营销怎么推广
  • 美妆网站怎么做推广神器app
  • 济南建网站公司排行榜百度浏览器网址大全
  • 做网站平台成本最新国内你新闻
  • 舞钢市做网站开发的公司对seo的认识和理解
  • 吉安做网站的全球新闻最新消息
  • 广州企业如何建网站三叶草gw9356
  • 红色 网站配色个人免费建站系统
  • 网站建设 展滔科技大厦关键词在线查询
  • 旅游网站的后台管理系统怎么做嘉兴seo网络推广