06树和二叉树探析.ppt

第六章 树;6.1树的定义和基本术语;A;基本术语;兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m?0)棵互不相交的树的集合;A;(１) 有确定的根； (２) 树根和子树根之间为有向关系。;线性结构;基本操作：查 找 类;插入类;删除类;6.2 二叉树;基本形态;二叉树的基本操作 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());;InitBiTree(T); Assign(T, e, value); CreateBiTree(T, definition); InsertChild(T, p, LR, c); ClearBiTree(T); DestroyBiTree(T); DeleteChild(T, p, LR);;二、二叉树性质;性质2：深度为k的二叉树至多有 个结点(k?1);性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1;几种特殊形式的二叉树 满二叉树 定义：;1;性质4;性质5;应用;三、二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点：结点间关系蕴含在其存储位置中；浪费空间，适于存满二叉树和完全二叉树。 定义： #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE＋1]; // 1号单元存储根结点 SqBiTree bt;;a;链式存储结构 二叉链表;A;三叉链表;A;6.3二叉树的遍历和线索化;对“二叉树”而言，可以有三条有哪些信誉好的足球投注网站路径;先左后右的遍历方法 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点;A;A;A;-;void preorder(BiTree *bt){ if(!bt){ printf(%d\t,bt-data); preorder(bt-lchild); preorder(bt-rchild); } };二、算法描述;先序遍历的非??归算法;中序遍历的非递归算法;后序遍历的非递归算法;后序遍历的非递归算法;求二叉树深度 作业：642统计二叉树中叶子结点个数 销毁二叉树 643所有结点的左右子树交换 633结点的前后代判断 判断二叉树是否对称 作业：636判断两棵树是否相似 作业：652求一棵二叉树的繁茂度;非递归算法执行流程;p;A;A;建树操作;几种特殊的二叉树;三、遍历算法应用;算法描述;6.3.2线索二叉树;实现;A;A;A;A;中序遍历的第一个结点？ 左子树上处于“最左下”（没有左子树）的结点。 在中序线索化链表中结点的后继？ 若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。;void InOrderTraverse_Thr(BiThrTree T) { p = T-lchild; // p指向根结点 while (p != T) { // 空树或遍历结束时， while (p-LTag==Link) p = p-lchild; // 第一个结点 Visit(p-data); while (p-RTag==Thread p-rchild!=T){ p = p-rchild; Visit(p-data); }// 访问后继结点 p = p-rchild; // p进