二叉树 | 前、中、后序递归遍历及层次遍历
2021/9/20 6:06:54
本文主要是介绍二叉树 | 前、中、后序递归遍历及层次遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉树的前、中、后序递归遍历及层次遍历
运行结果
- 二叉树采用二叉排序树生成法,所以中序输出递增序列
想描述的都在代码里了,这些都比较简单,直接看代码里的注释吧。
#include<iostream> // 定义二叉树结点类型,以二叉链表作为存储二叉树的数据结构 typedef struct BTNode { int data; struct BTNode* lchild; struct BTNode* rchild; // 默认构造 BTNode() :data(0), lchild(0), rchild(0) {} // 带参构造函数 BTNode(int _data) : data(_data) { this->lchild = 0, this->rchild = 0; } } BTNode; // 二叉排序树的插入 int BSTInsert(BTNode*& bt, int key) { if (bt == 0) { bt = new BTNode; bt->lchild = bt->rchild = 0; bt->data = key; return 1; // 插入成功标志 } else { if (key == bt->data) return 0; // 插入失败返回 0 else if (key < bt->data) return BSTInsert(bt->lchild, key); // 关键字小于根结点值,作为左孩子插入 else return BSTInsert(bt->rchild, key); // 关键字大于根结点值,作为右孩子插入 } } // 构造二叉排序树 void CreateBST(BTNode*& bt, int key[], int n) { bt = 0; // 将树清空 for (int i = 0; i < n; ++i) { BSTInsert(bt, key[i]); // 依次将每个关键字插入到二叉排序树中 } } void visit(BTNode* p) { std::cout << p->data << '\t'; } // 先序遍历 (NLR) void preOrder(BTNode* p) { if (!p) return; visit(p); preOrder(p->lchild); preOrder(p->rchild); } // 中序遍历 (LNR) void inOrder(BTNode* p) { if (!p) return; inOrder(p->lchild); visit(p); inOrder(p->rchild); } // 后序遍历 (LRN) void postOrder(BTNode* p) { if (!p) return; postOrder(p->lchild); postOrder(p->rchild); visit(p); } // 层次遍历 void level(BTNode* p) { int front, rear; const int maxSize = 20; BTNode* que[maxSize]; // 定义一个循环队列,用来记录将要访问的层次上的结点 front = rear = 0; BTNode* q; if (p != 0) { rear = (rear + 1) % maxSize; // 结点不为空,入队 que[rear] = p; while (front != rear) { front = (front + 1) % maxSize; q = que[front]; // 队头出队 visit(q); // 访问、打印队头结点 if (q->lchild != 0) { // 如果左子树不空,则左子树的根结点入队 rear = (rear + 1) % maxSize; que[rear] = q->lchild; } if (q->rchild != 0) { // 如果右子树不空,则右子树的根结点入队 rear = (rear + 1) % maxSize; que[rear] = q->rchild; } } } } int main() { int key[]{ 5,2,7,1,4,6,8,3 }; // 测试数组 std::cout << "打印测试数组:\n"; for (auto& i : key) { std::cout << i << '\t'; } BTNode* root = new BTNode; // 构造二叉排序树 CreateBST(root, key, sizeof(key) / sizeof(key[0])); std::cout << "\n前序输出:\n"; preOrder(root); std::cout << '\n'; std::cout << "中序输出:\n"; inOrder(root); std::cout << '\n'; std::cout << "后序输出:\n"; postOrder(root); std::cout << '\n'; std::cout << "层次输出:\n"; level(root); std::cout << '\n'; system("pause"); return 0; }
这篇关于二叉树 | 前、中、后序递归遍历及层次遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南