ToB企服应用市场:ToB评测及商务社交产业平台

标题: 遍历二叉树 [打印本页]

作者: 水军大提督 时间: 2024-4-11 22:30
标题: 遍历二叉树
二叉树

前言

二叉树的遍历主要有深度优先遍历和广度优先遍历，深度优先遍历是优先访问一个子树上的所有节点，访问的属性是竖向的，而广度优先遍历则是优先访问同一层的所有节点，访问属性是横向的。

深度优先遍历

深度优先遍历主要有三种顺序：

前序遍历 —— 根左右
中序遍历 —— 左根右
后序遍历 —— 左右根

这三种遍历顺序用递归可以很容易实现，主要讲的是非递归的实现方法。而要使用迭代的方法来遍历二叉树，需要用到栈的特性。
前序遍历（非递归C++）

算法：

根节点入栈
访问栈顶元素并将其出栈
将左右子树入栈，由于访问顺序是"根左右"，且使用的是栈，因此右子树先于左子树入栈
重复步骤2、3，直到栈为空

[code]void preOrder(BTNode* root) { stack S; BTNode* cur = NULL; if(root == NULL) return; S.push(root); //根节点入栈 while(!S.empty()) { //访问顺序"根左右" cur = S.top(); coutleft; } //访问最左孩子 cur = S.top(); cout

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)