二叉树

；否则其左孩子 LCHILD(i)是节点 2i。 ③ 如果 2i+1n，则节点 i无右孩子；否则其右孩子 RCHILD(i) 是节点 2i+1。 二叉树的存储结构 • 顺序存储 以节点在向量中的相对位置来表示节点间的关系。 不足：一般的二叉树也必须按完全二叉树的形式来存储，势必会造成存储的浪费。 53214( a ) 二叉树T∧22∧1 14 ∧∧5 ∧345∧3 ∧ ∧214 ∧∧5 ∧∧3

CTBox nodes[MaxTreeSize]。 int n, root。 // 结点数和根的位置 }。 树结构 : 数据结构 树和二叉树 A B C D E F G A B C E D F G root A B C E D F G 三、树的二叉链表 (孩子 兄弟）存储表示法 数据结构 树和二叉树 struct CSNode{ Elem data。 CSNode *firstchild,

er)遍历：若树为空，执行空操作；否则依次执行：  中序遍历左子树 L；  访问根结点 D；  中序遍历右子树 R。 2. 先序 (PreOrder)遍历：若树为空，执行空操作；否则依次执行：  访问根结点 D；  先序遍历左子树 L；  先序遍历右子树 R。 3. 后序 (PostOrder)遍历：若树为空，执行空操作；否则依次执行：  后序遍历左子树 L；  后序遍历右子树

trightChild=createBinaryTree(LRV+k,LVR+k+1,nk1)。 A D C B E F G H I J //从后序的 LRV+k 开始，对中序的 k+1 到 n1 右子序列的 nk1 个元素建立右子树 return t。 }。 执行文件如下： 首先进行后序序列以及中序序列的输入，然后构建出二叉树，接着输出前序序列进行验证，看是否程序准确运行。 void

二叉搜索树 45 12 57 8 20 60 3 11 59 50 二叉搜索树的作用： 排序 ， 检索 二叉搜索树 ifndef BINARY_SEARCH_TREE_CLASS define BINARY_SEARCH_TREE_CLASS include include ifndef NULL const int NULL = 0。 endif // NULL include

template class Type int BinaryTreeType :: Height ( const BinTreeNode Type * t ) const { if ( t == NULL ) return 1。 else return 1 + Max ( Height ( tleftChild ), Height ( trightChild ) )。 }

性数据结构，其中一树和二叉树最重要。 树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构够可以用树来形象表示。 树在计算机领域中也得到了广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。 二叉树是一种非线性数据结构，对它进行操作时总需要对每个数据逐一进行操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作问题

11    kkikiii层的最大结点数第167。 二叉树及其基本性质 性质 3 ： 对任何一棵二叉树，度为 0的叶子结点总是比度为 2 的结点多一个，则必存在关系式： n0 = n2+1。 证明： n1为二叉树 T中度为 1的结点数 因为：二叉树中所有结点的度均小于或等于 2 所以：其结点总数 n=n0+n1+n2 又二叉树中 ， 除根结点外 ， 其余结点都只有一个分支进入。