数据结构-二叉树（概念、遍历、重构）

阅读数:0次 2020-06-15

¶概念

深度： 根到当前点的路径长度
**高度：**当前点到叶子的最长路径长度
满二叉树
真二叉树
完全二叉树
树的高度和节点数的关系

¶遍历算法

¶前序

简单的用一个栈，先左孩子，后右孩子：
在这里插入图片描述

¶前序版本2

考虑整体的访问顺序，搞一个左访问链
在这里插入图片描述
主函数：

¶中序遍历

也是一样的，考虑一个左访问链，只是这次是go，不是visit，访问到最后一个再visit。
在这里插入图片描述

¶复杂度分析

递归，看起来是O(N)，但是很慢
分摊分析，每个节点智慧进行一次入栈，不会是N方的。

¶层次遍历

用队列

在这里插入图片描述

¶树的重构

需要中序遍历和前序/后序，可以重构一棵树

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true