- 浏览: 372294 次
最新评论
[算法系列之二]二叉树各种遍历
【简介】
树形结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点;深度为k的二叉树至多有2^(k) -1个结点;对任何一棵二叉树T,如果其终端结点数(即叶子结点数)为n0,度为2的结点数为n2,则n0 = n2 + 1。
二叉树的链式存储结构是一类重要的数据结构,其形式定义如下:
- //二叉树结点
- typedefstructBiTNode{
- //数据
- chardata;
- //左右孩子指针
- structBiTNode*lchild,*rchild;
- }BiTNode,*BiTree;
或者
// 二叉树节点结构 struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} };
【二叉树的创建】
通过读入一个字符串,建立二叉树的算法如下:
- //按先序序列创建二叉树
- intCreateBiTree(BiTree&T){
- chardata;
- //按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
- scanf("%c",&data);
- if(data=='#'){
- T=NULL;
- }
- else{
- T=(BiTree)malloc(sizeof(BiTNode));
- //生成根结点
- T->data=data;
- //构造左子树
- CreateBiTree(T->lchild);
- //构造右子树
- CreateBiTree(T->rchild);
- }
- return0;
- }
或者
// 1.创建二叉树 void CreateTree(TreeNode* &root){ int val; //按先序次序输入二叉树中结点的值,‘-1’表示空树 cin>>val; // 空节点 if(val == -1){ root = nullptr; return; }//if root = new TreeNode(val); //构造左子树 CreateTree(root->left); //构造右子树 CreateTree(root->right); }
层次建立二叉树:
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
// 创建二叉树 TreeNode* CreateTreeByLevel(vector<char> num){ int len = num.size(); if(len == 0){ return NULL; }//if queue<TreeNode*> queue; int index = 0; // 创建根节点 TreeNode *root = new TreeNode(num[index++]); // 入队列 queue.push(root); TreeNode *p = NULL; while(!queue.empty() && index < len){ // 出队列 p = queue.front(); queue.pop(); // 左节点 if(index < len && num[index] != -1){ // 如果不空创建一个节点 TreeNode *leftNode = new TreeNode(num[index]); p->left = leftNode; queue.push(leftNode); } index++; // 右节点 if(index < len && num[index] != -1){ // 如果不空创建一个节点 TreeNode *rightNode = new TreeNode(num[index]); p->right = rightNode; queue.push(rightNode); } index++; }//while return root; }
-1代表NULL
创建如上二叉树输入:
15 11 20 8 14 -1 -1 -1 -1 13 -1
【二叉树的遍历】
遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
【递归算法】
- //输出
- voidVisit(BiTreeT){
- if(T->data!='#'){
- printf("%c",T->data);
- }
- }
- //先序遍历
- voidPreOrder(BiTreeT){
- if(T!=NULL){
- //访问根节点
- Visit(T);
- //访问左子结点
- PreOrder(T->lchild);
- //访问右子结点
- PreOrder(T->rchild);
- }
- }
- //中序遍历
- voidInOrder(BiTreeT){
- if(T!=NULL){
- //访问左子结点
- InOrder(T->lchild);
- //访问根节点
- Visit(T);
- //访问右子结点
- InOrder(T->rchild);
- }
- }
- //后序遍历
- voidPostOrder(BiTreeT){
- if(T!=NULL){
- //访问左子结点
- PostOrder(T->lchild);
- //访问右子结点
- PostOrder(T->rchild);
- //访问根节点
- Visit(T);
- }
- }
【非递归算法】
【先序遍历】
【思路】:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
- /*先序遍历(非递归)
- 思路:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
- */
- voidPreOrder2(BiTreeT){
- stack<BiTree>stack;
- //p是遍历指针
- BiTreep=T;
- //栈不空或者p不空时循环
- while(p||!stack.empty()){
- if(p!=NULL){
- //存入栈中
- stack.push(p);
- //访问根节点
- printf("%c",p->data);
- //遍历左子树
- p=p->lchild;
- }
- else{
- //退栈
- p=stack.top();
- stack.pop();
- //访问右子树
- p=p->rchild;
- }
- }//while
- }
// 先序遍历 void PreOrder(TreeNode* root){ if(root == NULL){ return; } stack<TreeNode*> stack; stack.push(root); TreeNode *p = NULL; while(!stack.empty()){ p = stack.top(); stack.pop(); cout<<p->val<<endl; // 右子节点不空压入栈中 if(p->right){ stack.push(p->right); } // 左子节点不空压入栈中 if(p->left){ stack.push(p->left); } }//while }
【中序遍历】
【思路】:T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。
先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。
- voidInOrder2(BiTreeT){
- stack<BiTree>stack;
- //p是遍历指针
- BiTreep=T;
- //栈不空或者p不空时循环
- while(p||!stack.empty()){
- if(p!=NULL){
- //存入栈中
- stack.push(p);
- //遍历左子树
- p=p->lchild;
- }
- else{
- //退栈,访问根节点
- p=stack.top();
- printf("%c",p->data);
- stack.pop();
- //访问右子树
- p=p->rchild;
- }
- }//while
- }
【后序遍历】
【思路】:T是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。需要判断根结点的左右子树是否均遍历过。
- //后序遍历(非递归)
- typedefstructBiTNodePost{
- BiTreebiTree;
- chartag;
- }BiTNodePost,*BiTreePost;
- voidPostOrder2(BiTreeT){
- stack<BiTreePost>stack;
- //p是遍历指针
- BiTreep=T;
- BiTreePostBT;
- //栈不空或者p不空时循环
- while(p!=NULL||!stack.empty()){
- //遍历左子树
- while(p!=NULL){
- BT=(BiTreePost)malloc(sizeof(BiTNodePost));
- BT->biTree=p;
- //访问过左子树
- BT->tag='L';
- stack.push(BT);
- p=p->lchild;
- }
- //左右子树访问完毕访问根节点
- while(!stack.empty()&&(stack.top())->tag=='R'){
- BT=stack.top();
- //退栈
- stack.pop();
- BT->biTree;
- printf("%c",BT->biTree->data);
- }
- //遍历右子树
- if(!stack.empty()){
- BT=stack.top();
- //访问过右子树
- BT->tag='R';
- p=BT->biTree;
- p=p->rchild;
- }
- }//while
- }
或者
vector<int> postorderTraversal(TreeNode *root) { vector<int> result; if(root == nullptr){ return result; }//if stack<TreeNode*> s; s.push(root); TreeNode *node; while(!s.empty()){ node = s.top(); s.pop(); result.insert(result.begin(),node->val); // 左子树 if(node->left){ s.push(node->left); }//if // 右子树 if(node->right){ s.push(node->right); }//if }//while return result; }
【层次遍历】
【思路】:按从顶向下,从左至右的顺序来逐层访问每个节点,层次遍历的过程中需要用队列。
- //层次遍历
- voidLevelOrder(BiTreeT){
- BiTreep=T;
- //队列
- queue<BiTree>queue;
- //根节点入队
- queue.push(p);
- //队列不空循环
- while(!queue.empty()){
- //对头元素出队
- p=queue.front();
- //访问p指向的结点
- printf("%c",p->data);
- //退出队列
- queue.pop();
- //左子树不空,将左子树入队
- if(p->lchild!=NULL){
- queue.push(p->lchild);
- }
- //右子树不空,将右子树入队
- if(p->rchild!=NULL){
- queue.push(p->rchild);
- }
- }
- }
【测试】
输入:(先序)
15 11 8 -1 -1 14 13 -1 -1 -1 20 -1 -1
输出:
代码一:
/*------------------------------------- * 日期:2015-03-25 * 作者:SJF0115 * 题目: 二叉树各种遍历 * 来源: * 博客: ------------------------------------*/ #include <iostream> #include <vector> #include <stack> #include <queue> using namespace std; // 二叉树节点结构 struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} }; // 1.创建二叉树 void CreateTree(TreeNode* &root){ int val; //按先序次序输入二叉树中结点的值,‘-1’表示空树 cin>>val; // 空节点 if(val == -1){ root = nullptr; return; }//if root = new TreeNode(val); //构造左子树 CreateTree(root->left); //构造右子树 CreateTree(root->right); } // 2.1 递归先序遍历 void PreOrder(TreeNode* root,vector<int> &result){ if(root == nullptr){ return; }//if result.push_back(root->val); // 左子树 PreOrder(root->left,result); // 右子树 PreOrder(root->right,result); } // 2.2 非递归先序遍历 void PreOrder2(TreeNode* root,vector<int> &result){ if(root == nullptr){ return; }//if stack<TreeNode*> s; s.push(root); TreeNode *node; while(!s.empty()){ node = s.top(); s.pop(); result.push_back(node->val); // 右子树 if(node->right){ s.push(node->right); }//if // 左子树 if(node->left){ s.push(node->left); }//if }//while } // 3.1 递归中序遍历 void InOrder(TreeNode* root,vector<int> &result){ if(root == nullptr){ return; }//if // 左子树 InOrder(root->left,result); result.push_back(root->val); // 右子树 InOrder(root->right,result); } // 3.2 非递归中序遍历 void InOrder2(TreeNode* root,vector<int> &result){ if(root == nullptr){ return; }//if stack<TreeNode*> s; TreeNode *node = root; while(node != nullptr || !s.empty()){ // 左子树 if(node != nullptr){ s.push(node); node = node->left; }//if // 右子树 else{ node = s.top(); s.pop(); result.push_back(node->val); node = node->right; } }//while } // 4.1 递归后序遍历 void PostOrder(TreeNode* root,vector<int> &result){ if(root == nullptr){ return; }//if // 左子树 PostOrder(root->left,result); // 右子树 PostOrder(root->right,result); result.push_back(root->val); } // 4.2 非递归后序遍历 void PostOrder2(TreeNode *root,vector<int> &result) { if(root == nullptr){ return; }//if stack<TreeNode*> s; s.push(root); TreeNode *node; while(!s.empty()){ node = s.top(); s.pop(); result.insert(result.begin(),node->val); // 左子树 if(node->left){ s.push(node->left); }//if // 右子树 if(node->right){ s.push(node->right); }//if }//while } // 5 层次遍历 void LevelOrder(TreeNode* root,vector<int> &result){ if(root == nullptr){ return; }//if queue<TreeNode*> queue; queue.push(root); TreeNode *node; while(!queue.empty()){ node = queue.front(); queue.pop(); result.push_back(node->val); // 左子树 if(node->left){ queue.push(node->left); }//if // 右子树 if(node->right){ queue.push(node->right); }//if }//while } // 输出结果 void Print(vector<int> result){ int size = result.size(); for(int i = 0;i < size;++i){ cout<<result[i]<<" "; }//for cout<<endl; } int main(){ freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin); TreeNode* root = nullptr; vector<int> result; // 创建二叉树 cout<<"1. 创建二叉树"<<endl; CreateTree(root); cout<<"-----------------------------"<<endl; cout<<"2.1 递归先序遍历"<<endl; PreOrder(root,result); Print(result); result.clear(); cout<<"-----------------------------"<<endl; cout<<"2.2 非递归先序遍历"<<endl; PreOrder2(root,result); Print(result); result.clear(); cout<<"-----------------------------"<<endl; cout<<"3.1 递归中序遍历"<<endl; InOrder(root,result); Print(result); result.clear(); cout<<"-----------------------------"<<endl; cout<<"3.2 非递归中序遍历"<<endl; InOrder2(root,result); Print(result); result.clear(); cout<<"-----------------------------"<<endl; cout<<"4.1 递归后序遍历"<<endl; PostOrder(root,result); Print(result); result.clear(); cout<<"-----------------------------"<<endl; cout<<"4.2 非递归后序遍历"<<endl; PostOrder2(root,result); Print(result); result.clear(); cout<<"-----------------------------"<<endl; cout<<"5 层次遍历"<<endl; LevelOrder(root,result); Print(result); result.clear(); cout<<"-----------------------------"<<endl; return 0; }
测试用例:
输入:
ABC##DE#G##F###
输出:
代码二:
- #include<iostream>
- #include<stack>
- #include<queue>
- usingnamespacestd;
- //二叉树结点
- typedefstructBiTNode{
- //数据
- chardata;
- //左右孩子指针
- structBiTNode*lchild,*rchild;
- }BiTNode,*BiTree;
- //按先序序列创建二叉树
- intCreateBiTree(BiTree&T){
- chardata;
- //按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
- scanf("%c",&data);
- if(data=='#'){
- T=NULL;
- }
- else{
- T=(BiTree)malloc(sizeof(BiTNode));
- //生成根结点
- T->data=data;
- //构造左子树
- CreateBiTree(T->lchild);
- //构造右子树
- CreateBiTree(T->rchild);
- }
- return0;
- }
- //输出
- voidVisit(BiTreeT){
- if(T->data!='#'){
- printf("%c",T->data);
- }
- }
- //先序遍历
- voidPreOrder(BiTreeT){
- if(T!=NULL){
- //访问根节点
- Visit(T);
- //访问左子结点
- PreOrder(T->lchild);
- //访问右子结点
- PreOrder(T->rchild);
- }
- }
- //中序遍历
- voidInOrder(BiTreeT){
- if(T!=NULL){
- //访问左子结点
- InOrder(T->lchild);
- //访问根节点
- Visit(T);
- //访问右子结点
- InOrder(T->rchild);
- }
- }
- //后序遍历
- voidPostOrder(BiTreeT){
- if(T!=NULL){
- //访问左子结点
- PostOrder(T->lchild);
- //访问右子结点
- PostOrder(T->rchild);
- //访问根节点
- Visit(T);
- }
- }
- /*先序遍历(非递归)
- 思路:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
- */
- voidPreOrder2(BiTreeT){
- stack<BiTree>stack;
- //p是遍历指针
- BiTreep=T;
- //栈不空或者p不空时循环
- while(p||!stack.empty()){
- if(p!=NULL){
- //存入栈中
- stack.push(p);
- //访问根节点
- printf("%c",p->data);
- //遍历左子树
- p=p->lchild;
- }
- else{
- //退栈
- p=stack.top();
- stack.pop();
- //访问右子树
- p=p->rchild;
- }
- }//while
- }
- /*中序遍历(非递归)
- 思路:T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。
- 先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。
- */
- voidInOrder2(BiTreeT){
- stack<BiTree>stack;
- //p是遍历指针
- BiTreep=T;
- //栈不空或者p不空时循环
- while(p||!stack.empty()){
- if(p!=NULL){
- //存入栈中
- stack.push(p);
- //遍历左子树
- p=p->lchild;
- }
- else{
- //退栈,访问根节点
- p=stack.top();
- printf("%c",p->data);
- stack.pop();
- //访问右子树
- p=p->rchild;
- }
- }//while
- }
- //后序遍历(非递归)
- typedefstructBiTNodePost{
- BiTreebiTree;
- chartag;
- }BiTNodePost,*BiTreePost;
- voidPostOrder2(BiTreeT){
- stack<BiTreePost>stack;
- //p是遍历指针
- BiTreep=T;
- BiTreePostBT;
- //栈不空或者p不空时循环
- while(p!=NULL||!stack.empty()){
- //遍历左子树
- while(p!=NULL){
- BT=(BiTreePost)malloc(sizeof(BiTNodePost));
- BT->biTree=p;
- //访问过左子树
- BT->tag='L';
- stack.push(BT);
- p=p->lchild;
- }
- //左右子树访问完毕访问根节点
- while(!stack.empty()&&(stack.top())->tag=='R'){
- BT=stack.top();
- //退栈
- stack.pop();
- BT->biTree;
- printf("%c",BT->biTree->data);
- }
- //遍历右子树
- if(!stack.empty()){
- BT=stack.top();
- //访问过右子树
- BT->tag='R';
- p=BT->biTree;
- p=p->rchild;
- }
- }//while
- }
- //层次遍历
- voidLevelOrder(BiTreeT){
- BiTreep=T;
- //队列
- queue<BiTree>queue;
- //根节点入队
- queue.push(p);
- //队列不空循环
- while(!queue.empty()){
- //对头元素出队
- p=queue.front();
- //访问p指向的结点
- printf("%c",p->data);
- //退出队列
- queue.pop();
- //左子树不空,将左子树入队
- if(p->lchild!=NULL){
- queue.push(p->lchild);
- }
- //右子树不空,将右子树入队
- if(p->rchild!=NULL){
- queue.push(p->rchild);
- }
- }
- }
- intmain()
- {
- BiTreeT;
- CreateBiTree(T);
- printf("先序遍历:\n");
- PreOrder(T);
- printf("\n");
- printf("先序遍历(非递归):\n");
- PreOrder2(T);
- printf("\n");
- printf("中序遍历:\n");
- InOrder(T);
- printf("\n");
- printf("中序遍历(非递归):\n");
- InOrder2(T);
- printf("\n");
- printf("后序遍历:\n");
- PostOrder(T);
- printf("\n");
- printf("后序遍历(非递归):\n");
- PostOrder2(T);
- printf("\n");
- printf("层次遍历:\n");
- LevelOrder(T);
- printf("\n");
- return0;
- }
相关推荐
包括了二叉树的各种递归与非递归的遍历算法 还可对二叉树所有结点求和
二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
一、实验名称:二叉树的遍历方法 二、实验目的: (1)熟悉C语言的上机环境,进一步掌握C语言的结构特点; (2)掌握二叉树的储存结构的定义及C语言实现; (3)掌握二叉树的三种遍历方法,即先序遍历,中序遍历,...
实验八:二叉树的遍历算法 以下是二叉树建立的两种方法,三种遍历和计算结点数的综合程序.(读者有建议可提出)
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
二叉树 各种遍历算法 C#实现
C++二叉树的前序,中序,后序,层序遍历的递归算法
(1)以二叉链为存储结构,建立二叉树 (2)用递归算法和非递归算法实现二叉树的中序遍历 (3)二叉树中序遍历的演示
使用C++模板、类的技术实现了二叉树的中序遍历,在BC3.1已经测试成功
二叉树遍历算法,包括创建二叉树,先序,中序以及后序遍历等。
编写程序,用先序递归遍历法建立二叉树的二叉链表存储结构,然后输出其先序、中序、后序以及层次遍历结点访问次序。其中层次遍历的实现需使用循环队列。二叉树结点数据类型建议选用字符类型
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
数据结构课程设计报告-二叉树的遍历.docx
C语言二叉树遍历前序非递归算法,简单易懂,正确无误
/* 设栈元素为二叉树的指针类型 */ typedef struct { QElemType *base; int front; /* 头指针,若队列不空,指向队列头元素 */ int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */ } SqQueue; ...
二叉树的建立和遍历算法 数据结构课程设计用
二叉树遍历算法应用各种算法包括遍历创建求深度等
二叉树的递归算法:建立二叉树、遍历二叉树.doc 多多指教
二叉树的创建与遍历二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法...