二叉树

发布时间: 更新时间: 总字数:262 阅读时间:1m 作者: IP上海 分享 网址

二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。

介绍

二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。

  • golang 示例
/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

遍历方式

  • 前序遍历:根节点 - 左子树 - 右子树
  • 中序遍历:左子树 - 根节点 - 右子树
  • 后序遍历:左子树 - 右子树 - 根节点

二叉搜索树

定义如下:

  • 节点的左子树只包含 小于 当前节点的数
  • 节点的右子树只包含 大于 当前节点的数
  • 所有左子树和右子树自身必须也是二叉搜索树
Home Archives Categories Tags Statistics
本文总阅读量 次 本站总访问量 次 本站总访客数