首页 > 其他分享 >二叉树遍历

二叉树遍历

时间：2023-08-02 15:13:26浏览次数：36  
标签：Node 遍历 temp vec node1 new left 二叉树

递归实现：

前序遍历

将根结点输入容器，然后对左子树进行先序遍历，再对右子树进行先序遍历

 1 void frontfind(Node* node,  vector<int>& vec) {
 2     if (node == nullptr) {
 3         return;
 4     }
 5     //非终止条件，非递归入口，只需考虑如果只有一个结点需要做什么
 6     vec.push_back(node->data_);
 7     //递归入口的参数是，性质相同但是规模更小的子问题，比如左子树它本身就是一个树但是相对于整个树而言它是一个规模更小的子问题
 8     frontfind(node->left,vec);
 9     frontfind(node->right,vec);
10 }
11 int main() {
12     Node* node1 = new Node(6);
13     Node* node2 = new Node(3);
14     Node* node3 = new Node(9);
15     Node* node4 = new Node(1);
16     Node* node5 = new Node(4);
17     Node* node6 = new Node(8);
18     Node* node7 = new Node(0);
19     node1->left = node2;
20     node1->right = node3;
21     node2->left = node4;
22     node2->right = node5;
23     node3->left = node6;
24     node4->left = node7;
25     vector<int>vec;
26     frontfind(node1, vec);
27     for (auto& v : vec) {
28         cout << v << endl;
29     }
30 }

6310498

中序遍历

对左子树进行先序遍历，然后将根结点输入容器，再对右子树进行先序遍历

 1 void medfind(Node* node,  vector<int>& vec) {
 2     if (node == nullptr) {
 3         return;
 4     }
 5     frontfind(node->left,vec);
 6     vec.push_back(node->data_);
 7     frontfind(node->right,vec);
 8 }
 9 int main() {
10     Node* node1 = new Node(6);
11     Node* node2 = new Node(3);
12     Node* node3 = new Node(9);
13     Node* node4 = new Node(1);
14     Node* node5 = new Node(4);
15     Node* node6 = new Node(8);
16     Node* node7 = new Node(0);
17     node1->left = node2;
18     node1->right = node3;
19     node2->left = node4;
20     node2->right = node5;
21     node3->left = node6;
22     node4->left = node7;
23     vector<int>vec;
24     frontfind(node1, vec);
25     for (auto& v : vec) {
26         cout << v << endl;
27     }
28 }

0134689

后序遍历

对左子树进行先序遍历，再对右子树进行先序遍历，然后将根结点输入容器

 1 void behindfind(Node* node,  vector<int>& vec) {
 2     if (node == nullptr) {
 3         return;
 4     }
 5     frontfind(node->left,vec);
 6     frontfind(node->right,vec);
 7     vec.push_back(node->data_);
 8 }
 9 int main() {
10     Node* node1 = new Node(6);
11     Node* node2 = new Node(3);
12     Node* node3 = new Node(9);
13     Node* node4 = new Node(1);
14     Node* node5 = new Node(4);
15     Node* node6 = new Node(8);
16     Node* node7 = new Node(0);
17     node1->left = node2;
18     node1->right = node3;
19     node2->left = node4;
20     node2->right = node5;
21     node3->left = node6;
22     node4->left = node7;
23     vector<int>vec;
24     frontfind(node1, vec);
25     for (auto& v : vec) {
26         cout << v << endl;
27     }
28 }

0143896

迭代实现(使用栈)

如果某元素遍历到它立即就要将它装进vector中，我们就要将它压栈之后立即弹栈，如果某元素遍历到它不立即将它装进vector中，我们就要将它压栈之后，再压入其他元素

先序遍历

  • 先将根节点压栈此时根节点为栈顶，然后将栈顶弹栈，如果栈顶的右子树根节点不为空就将它压入栈中，然后左子树根节点不为空就将它压入栈中，然后继续弹栈，继续将栈顶的右子树和左子树压入栈中(如果它们不为空)

 

  • 开头的二叉树使用迭代遍历的思路：

6压栈，6弹栈装入容器，同时将9压栈，然后3压栈，3弹栈装入容器，同时4压栈，然后1压栈，1弹栈装入容器，1的右子树为空，然后让0压栈，0弹栈装入容器，0的右子树为空，0的左子树为空，4弹栈装入容器，4的右子树为空，4的左子树为空，9弹栈装入容器，9的左子树为空，8压栈，8弹栈装入容器，栈为空终止

 

 1 void frontfind(Node* node, vector<int>& vec) {
 2     stack<Node*>st;
　　　　if(node==nullptr) return;
 3     st.push(node);
 4     Node* temp;
 5     while (!st.empty()) {
 6         vec.push_back(st.top()->data_);
 7         temp = st.top();
 8         st.pop();
 9         if (temp->right) {
10             st.push(temp->right);
11         }
12         if (temp->left) {
13             st.push(temp->left);
14         }
15     }
16 }
17 int main() {
18     Node* node1 = new Node(6);
19     Node* node2 = new Node(3);
20     Node* node3 = new Node(9);
21     Node* node4 = new Node(1);
22     Node* node5 = new Node(4);
23     Node* node6 = new Node(8);
24     Node* node7 = new Node(0);
25     node1->left = node2;
26     node1->right = node3;
27     node2->left = node4;
28     node2->right = node5;
29     node3->left = node6;
30     node4->left = node7;
31     vector<int>vec;
32     frontfind(node1, vec);
33     for (auto& v : vec) {
34         cout << v << endl;
35     }
36 }

后序遍历

在前序遍历基础上更改，改为：先将左子树的根节点压栈，然后再把右子树的根节点压栈，函数的最后发生一次反转

 1 void reverse(vector<int>& vec) {
 2     auto beg = vec.begin(), end = vec.end() - 1;
 3     int temp;
 4     while (beg < end) {
 5         temp = *beg;
 6         *beg++ = *end;
 7         *end-- = temp;
 8     }
 9 }
10 void behindfind(Node* node, vector<int>& vec) {
11     stack<Node*>st;
　　　　if(node==nullptr) return;
12     st.push(node);
13     Node* temp;
14     while (!st.empty()) {
15         vec.push_back(st.top()->data_);
16         temp = st.top();
17         st.pop();
18         if (temp->left) {
19             st.push(temp->left);
20         }
21         if (temp->right) {
22             st.push(temp->right);
23         }
24     }
25     reverse(vec);
26 }
27 
28 int main() {
29     Node* node1 = new Node(6);
30     Node* node2 = new Node(3);
31     Node* node3 = new Node(9);
32     Node* node4 = new Node(1);
33     Node* node5 = new Node(4);
34     Node* node6 = new Node(8);
35     Node* node7 = new Node(0);
36     node1->left = node2;
37     node1->right = node3;
38     node2->left = node4;
39     node2->right = node5;
40     node3->left = node6;
41     node4->left = node7;
42     vector<int>vec;
43     frontfind(node1, vec);
44     for (auto& v : vec) {
45         cout << v << endl;
46     }
47 }

 

中序遍历

定义一个temp用来记录当前结点

遍历到的结点不为空就将它压栈，然后将temp->left给temp

否则

当前结点为空的时候将stack.top给temp,并将stack.top装入vector容器，然后弹栈，然后将temp->right给temp

 

总的来说：浏览到的结点不为空就把该节点压栈，然后浏览该节点左侧，如果为空就将栈顶弹出，然后浏览栈顶的右侧

 1 void medfind(Node* node, vector<int>& vec) {
 2     stack<Node*>st;
　　　　if(node==nullptr) return;
 3     Node* temp = node;
 4     //只有temp为空的情况下采取判断st是否为空
 5     while ((temp!=nullptr)||(!st.empty())) {
 6         if (temp) {
 7             st.push(temp);
 8             temp = temp->left;
 9         }
10         else {
11             temp = st.top();
12             st.pop();
13             vec.push_back(temp->data_);
14             temp = temp->right;
15         }
16     }
17 }
18 
19 int main() {
20     Node* node1 = new Node(6);
21     Node* node2 = new Node(3);
22     Node* node3 = new Node(9);
23     Node* node4 = new Node(1);
24     Node* node5 = new Node(4);
25     Node* node6 = new Node(8);
26     Node* node7 = new Node(0);
27     node1->left = node2;
28     node1->right = node3;
29     node2->left = node4;
30     node2->right = node5;
31     node3->left = node6;
32     node4->left = node7;
33     vector<int>vec;
34     medfind(node1, vec);
35     for (auto& v : vec) {
36         cout << v << endl;
37     }
38 }

层序遍历

假定一层的结点数为n，每个for循环都执行n次“出队，并将左子树的根节点入队，将右子树的根节点入队”的过程

 1 void ceng(Node* node, vector<vector<int>>& result) {
 2     queue<Node*>qu;
 3     qu.push(node); 4     int size = 0;
 5     //只有temp为空的情况下采取判断st是否为空
 6     while (!qu.empty()) {
 7         size = qu.size();
 9         vector<int>vec;
10         for (int i = 0; i < size; i++) {12             vec.push_back(qu.front()->data_);
13             qu.pop();
14             if (qu.front()->left) {
15                 qu.push(temp->left);
16             }
17             if (qu.front()->right) {
18                 qu.push(temp->right);
19             }
20         }
21         result.push_back(vec);
22     }
23 }
24 
25 int main() {
26     Node* node1 = new Node(6);
27     Node* node2 = new Node(3);
28     Node* node3 = new Node(9);
29     Node* node4 = new Node(1);
30     Node* node5 = new Node(4);
31     Node* node6 = new Node(8);
32     Node* node7 = new Node(0);
33     node1->left = node2;
34     node1->right = node3;
35     node2->left = node4;
36     node2->right = node5;
37     node3->left = node6;
38     node4->left = node7;
39     vector<vector<int>>result;
40     ceng(node1, result);
41     for (auto& v : result) {
42         for (auto& in : v) {
43             cout << in << endl;
44         }
45     }
46 }

 

标签：Node,遍历,temp,vec,node1,new,left,二叉树
From： https://www.cnblogs.com/Sandals-little/p/17600697.html

相关文章

  • Java list的遍历方法
    1.把List当作一个数组，从数组的第一个位置开始循环到数组的最后位置for(inti=0;i<list.size();i++){System.out.println(list.get(i));}2.foreach 方法语法:for(数据类型变量名:数组){需要执行的语句块;//这里的变量名可以直接用}for(Integernum:li......
  • 什么是递归？如果你以前从来没写过递归函数，尝试着写一个（比如用递归函数进行目录树遍历）。
    递归是一种在算法或函数中调用自身的方法。在递归过程中，问题会被分解成一个或多个相似的子问题，然后这些子问题又会进一步被分解，直到达到最简单的情况，从而得到解决。递归在编程中是一种强有力的工具，特别适合解决那些具有递归结构的问题。举个例子，我们可以使用递归函数来实现目录树......
  • freemeker 遍历map嵌套list数据结构
    遍历嵌套数据结构渲染map中value是list的内容<#ifnodes??&&(nodes?size>0)>【节点明细】<#listnodes?keysasalarmLevel>${alarmLevel+":"}<#if(nodes[alarmLevel])??><#list(nodes[alarmLevel])asnode>${node.nodeNo}<#sep>,&......
  • 二叉树的结点个数
    二叉树的节点个数假设二叉树如下图所示：要想知道二叉树的节点个数，我们通常会想到遍历二叉树的同时使用一个变量来记录，假设变量为size，使用前序遍历，每遍历一个结点让size++，可设置程序如下：intTreeSize(BTNode*root){ intsize=0; if(root==NULL) { return0; } size......
  • 遍历xml
    递归遍历xml节点 voidTravelXmlNode(QDomElement&element){QDomNodenode=element.firstChild();while(!node.isNull()){QDomElementchildElement=node.toElement();//trytoconvertthenodetoanelement.if(!childElemen......
  • 110. 平衡二叉树
    给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例1：输入：root=[3,9,20,null,null,15,7]输出：true#Definitionforabinarytreenode.#classTreeNode:#def__init__(se......
  • 树与二叉树
    树的概念：根有子节点，子节点又是一个子树的根T1,T2,T3换一个顺序就不是原来的树了，就称为有序树，T1,T2,T3换一个顺序就还是原来的树，就称为无序树二叉树不是树的特殊情况，二叉树中的一个结点必须表明该结点是左节点还是右节点，即便它没有兄弟结点。而树不必区分左右。  二叉......
  • 104. 二叉树的最大深度
    给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7]，3/\920/\157返回它的最大深度 3。#Definitionforabinarytreenode.......
  • 二叉树的广度优先遍历
    二叉树的广度优先遍历层序遍历设二叉树的根节点所在层数为第一层，层序遍历就是从二叉树的根节点出发，先访问第一层的根节点，然后从左到右访问第2层上的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。要想用代码实现队列的层序遍历我们需要借助队列：1、先把根......
  • 101. 对称二叉树
    给你一个二叉树的根节点 root ，检查它是否轴对称。示例1：输入：root=[1,2,2,3,4,4,3]输出：true示例2：输入：root=[1,2,2,null,3,null,3]输出：false#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#s......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99