二叉树的前序、序、后序遍历
二叉树的定义
二叉树是一种数据结构,它由一组称为节点的元素组成,这些节点通过边连接。每个节点最多可以有两个子节点,分别称为左子节点和右子节点。
树的深度优先遍历
深度优先遍历又根据处理某个子树的根结点的顺序不同,可以分为:前序遍历、中序遍历、后序遍历。
- 前序遍历:先访问根结点,再访问左子结点,最后访问右子结点。
- 中序遍历:先访问左子结点,再访问根结点,最后访问右子结点。
- 后序遍历:先访问左子结点,再访问右子结点,最后访问根结点。
js代码实现
根据流程描述,使用递归实现是最简单的方式。代码非常的简单,也很容易理解。
const tree = {
val: 1,
left: {
val: 2,
left: { val: 4 },
right: { val: 5}
},
right: {
val: 3,
left: { val: 6 },
right: { val: 7}
}
}
// 前序遍历:中 左 右
// 1 2 4 5 3 6 7
function preOrder(root) {
if (!root) return;
console.log(root.val);
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历:左 中 右
// 4, 2, 5, 1, 6, 3, 7
function inOrder(root) {
if (!root) return;
inOrder(root.left);
console.log(root.val);
inOrder(root.right);
}
// 后序遍历:左 右 中
// 4, 5, 2, 6, 7, 3, 1
function postOrder(root) {
if (!root) return;
postOrder(root.left);
postOrder(root.right);
console.log(root.val);
}
递归本身其实是语法内部帮我们调用了语言本身的栈实现(函数的调用栈)。如果我们想要非递归实现,则需要手动调用栈。
// 前序遍历:中 左 右
function preOrderStack(root) {
if (!root) return;
let stack = [root];
while (stack.length) {
let node = stack.pop();
console.log(node.val);
// 栈是后进先出的,所以先入栈右子节点
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
}
// 中序遍历:左 中 右
// 1、当前指针指向根节点
// 2、如果指针不为空,当前指针指向的节点入栈。指针指向左子节点。
// 3、如果指针为空,出栈一个节点。指针指向右子节点。
function inOrderStack(root) {
if (!root) return;
let stack = []; // 控制节点的访问顺序
let cur = root; // 当前指针指向根节点
while (stack.length || cur) {
while(cur) {
stack.push(cur); // 当前指针指向的节点入栈
cur = cur.left; // 访问左子节点
}
cur = stack.pop();
console.log(cur.val);
cur = cur.right; // 访问右子节点
}
}
// 后序遍历:左 右 中
// 非递归实现非常的繁琐,网上的方法都不太容易理解。这里给出的思路是,先访问父节点,再访问右子节点,最后访问左子节点。
// 把元素放入新栈中,最后出栈,正好访问顺序反转。
function postOrderStack(root) {
if (!root) return;
let stack = [root];
let res = [];
while (stack.length) {
// 这里访问的顺序是 中 右 左,加入到新的栈中
// 然后访问新的栈中的节点,顺序变成 左 右 中
let node = stack.pop();
res.push(node);
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
while(res.length){
console.log(res.pop().val);
}
}
go代码实现
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func NewTreeNode(val int) *TreeNode {
return &TreeNode{Val: val}
}
func (t *TreeNode) AddLeftChild(child *TreeNode) {
t.Left = child
}
func (t *TreeNode) AddRightChild(child *TreeNode) {
t.Right = child
}
// 前序遍历
func preOrder(root *TreeNode) {
if root == nil {
return
}
fmt.Println(root.Val)
preOrder(root.Left)
preOrder(root.Right)
}
func preOrderStack(root *TreeNode) {
stack := make([]*TreeNode, 0)
stack = append(stack, root)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(node.Val)
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
}
// 中序遍历
func inOrder(root *TreeNode) {
if root == nil {
return
}
inOrder(root.Left)
fmt.Println(root.Val)
inOrder(root.Right)
}
func inOrderStack(root *TreeNode) {
stack := make([]*TreeNode, 0)
cur := root
for len(stack) > 0 || cur != nil {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(cur.Val)
cur = cur.Right
}
}
// 后序遍历
func postOrder(root *TreeNode) {
if root == nil {
return
}
postOrder(root.Left)
postOrder(root.Right)
fmt.Println(root.Val)
}
func postOrderStack(root *TreeNode) {
stack := make([]*TreeNode, 0)
stack = append(stack, root)
res := make([]*TreeNode, 0)
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, node)
if node.Right != nil {
stack = append(stack, node.Left)
}
if node.Left != nil {
stack = append(stack, node.Right)
}
}
for len(res) > 0 {
fmt.Println(res[len(res)-1].Val)
res = res[:len(res)-1]
}
}
非递归实现二叉树的遍历十分地繁琐,建议使用递归,简单且不易出错。非递归实现后序遍历还有其他方法,笔者认为太过繁琐不易理解,就没有深入研究了,感兴趣的话可以自己搜索一下资料。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgajfef
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01