《数据结构》复习笔记--二叉树1

《数据结构》复习笔记--二叉树1

二叉树：

在​​计算机科学​​中，二叉树是每个节点最多有两个子树的​​树结构​​。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现​​二叉查找树​​​和​​二叉堆​​。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^(i-1)个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n1，度为2的结点数为n2，则n1=n2+1

一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

与树不同，树的结点个数至少为1，而二叉树的结点个数可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分。

二叉树的抽象数据类型定义

类型名称：二叉树数据对象集：一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。操作集： BT BinTree, Item  ElementType，重要操作有：1、Boolean IsEmpty( BinTree BT )： 判别BT是否为空；2、void Traversal( BinTree BT )：遍历，按某顺序访问每个结点；3、BinTree CreatBinTree( )：创建一个二叉树。

常用的遍历方法有：void PreOrderTraversal( BinTree BT )：先序----根、左子树、右子树；void InOrderTraversal( BinTree BT )： 中序---左子树、根、右子树；void PostOrderTraversal( BinTree BT )：后序---左子树、右子树、根void LevelOrderTraversal( BinTree BT )：层次遍历，从上到下、从左到右

二叉树的遍历

（1）先序遍历：

根节点--》先序遍历左子树--》先序遍历右子树。

void PreOrderTraversal(BinTree bt)/*先序遍历*/{ if(bt) { printf("%d",bt->data); PreOrderTraversal(bt->left); PreOrderTraversal(bt->right); }}

（2）中序遍历：

中序遍历左子树--》根节点--》中序遍历右子树

void InOrderTraversal( BinTree bt){ if(bt) { InOrderTraversal(bt->Left); printf(“%d”,bt->Data); InOrderTraversal(bt->Right); }}

（3）后序遍历

后序遍历左子树--》根节点--》后续遍历右子树

void PostOrderTraversal( BinTree bt ){ if(bt) { PostOrderTraversal(bt->Left ); PostOrderTraversal(bt->Right); printf(“%d”,bt->Data); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。