Electronic Joint Business

Solution for E-Business

二叉树

原文 原作者: Nick Parlante 本文的主旨是介绍二叉树(binary-tree)的基本概念,并通过 C/C++ 和 Java 的实现来解决一系列的实际问题。二叉树有很优雅的递归指针结构,所以也是个学习递归指针算法的好机会。 二叉树简介 二叉树由节点组成,其中每个节点包含一个“左”指针,一个“右”指针和一个数据元素。”根”指针指向树的最顶层节点。左、右的指针以递归方式指向两边较小的”子树”。空指针则表示二叉树不带任何元素 —-— 空的树。正规的递归的定义如下:一个既不是空的(用空指针表示)也不是由单一节点组成的二叉树,其左右节点(recursive definition ahead) 各指向一个二叉树。 “二叉搜索树”(BST) 或”有序二叉树”是一种节点按顺序排列的二进制树:对于每一个节点,其左子树中的所有元素都是小于等于该节点 (< =),和其右子树的所有元素均大于该节点 (>)。满足上面条件的树是二叉搜索树–例如 “根”节点是 5,和其左子树节点 (1、 3、 4) 是小于等于 5,和其右子树节点(6 9) 均大于 5。递归的,每个子树都必须遵循二进制搜索树约束: 在 (1、 3、 4) 子树,3 是根节点,而且 1 < = 3 和 4 > 3。请注意:描述问题要特别注意措词 — “二叉搜索树”和”二叉树”是不同的。 树的底端的节点的子树为空,因此被称为“叶”节点(1,4,6)而其他的节点则成为“内部”节点(3,5,9)。 Binary Search Tree Niche 基本上,二叉搜索树的插入和查询都是很快速的。下一节会演示这两个算法的代码。利用二叉搜索树算法,在有序的 N 个节点的树上查找一个节点,平均需要费时 […]

Comments are currently closed.