数据结构与程序设计(王丽苹)24二叉树

《数据结构与程序设计(王丽苹)24二叉树》由会员分享，可在线阅读，更多相关《数据结构与程序设计(王丽苹)24二叉树（39页珍藏版）》请在装配图网上搜索。

1、5/5/2021 数 据 结 构 与 程 序 设 计 1 数 据 结 构 与 程 序 设 计 (24)Chapter Binary Tree 二 叉 树 王 丽 苹 5/5/2021 数 据 结 构 与 程 序 设 计 2 Treen 树 tree的 定 义n (1) 无 结 点 的 树 空 树 n (2) 非 空 树n 仅 有 一 个 根 结 点n 其 余 结 点 分 为 若 干n 互 不 相 交 的 子 树n 在 树 形 结 构 中 每 个 结 点 最 多 只 有 一 个 前 驱 ， 但可 有 多 个 后 继 的 结 构 。 它 表 示 了 一 种 具 有 层 次的 分 支 关 系 。 5

2、/5/2021 数 据 结 构 与 程 序 设 计 3subtree Treen Root（ 根 ） : node without parent (A)n Siblings（ 兄 弟 ） : nodes share the same parentn Internal node: node with at least one child (A, B, C, F)n External node (leaf ): node without children (E, I, J, K, G, H, D)n Ancestors of a node: parent, grandparent, grand-g

3、randparent, etc. n Descendant of a node: child, grandchild, grand-grandchild, etc.n Depth of a node: number of ancestorsn Height of a tree: maximum depth of any node (3)n Degree of a node: the number of its childrenn Degree of a tree: the maximum number of its node. AB DCG HE FI J Kn Subtree: tree c

4、onsisting of a node and its descendants 5/5/2021 数 据 结 构 与 程 序 设 计 4 Tree PropertiesAB CD GE FIH Property ValueNumber of nodes 9Height 4 Root Node ALeaves Interior nodesAncestors of H （ G， E， B， A）Descendants of BSiblings of ERight subtree of ADegree of this tree 5/5/2021 数 据 结 构 与 程 序 设 计 5 Chapter

5、 10 Binary Tree n DEFINITION A binary tree is either empty, or it consists of a node called the root （ 根 ）together with two binary trees called the left subtree (左 子 树 ) and the right subtree （ 右 子树 ） of the root. 5/5/2021 数 据 结 构 与 程 序 设 计 6 5/5/2021 数 据 结 构 与 程 序 设 计 7深 度 (Height)为 k， 结 点 至 多 2k+1

6、-1个 ， 深 度 为 最 大 层 数第 i层 结 点 至 多 2i个 在 本 书 ， 层 数 从 0开 始 计 算 。 设 有 n2个 2度 点则 有 n2+1个 叶 片AB CD E F GH I J 5/5/2021 数 据 结 构 与 程 序 设 计 8 Binary Treen 满 二 叉 树 ： 如 果 一 棵 二 叉 树 的 深 度 为 k,结 点 数2k+1-1,每 层 结 点 数 都 最 大 ， 则 此 二 叉 树 称 作 满二 叉 树 。n 完 全 二 叉 树 ： 如 果 一 棵 二 叉 树 至 多 只 有 最 下 面的 两 层 结 点 度 数 可 以 小 于 2， 其 余

7、 各 层 结 点 度数 都 必 须 为 2， 并 且 最 下 面 一 层 的 结 点 都 集 中在 该 层 最 左 边 的 若 干 位 置 上 ， 则 此 二 叉 树 称 为完 全 二 叉 树 。 即 为 ， 满 二 叉 树 去 掉 最 下 层 最 右边 若 干 结 点 5/5/2021 数 据 结 构 与 程 序 设 计 9 Binary Tree 5/5/2021 数 据 结 构 与 程 序 设 计 10 AB CD E F GH I J完 全 二 叉 树 K L Mn个 结 点 ,深 度 k=log2(n) 下 取 整n个 结 点 ,深 度 为 k:2k-1 n2k+1-12k n 2k

8、+1k log2n k+1k=log2(n) 下 取 整1个 结 点 深 度 为 02-3个 结 点 深 度 为 14-7个 结 点 深 度 为 2 8-15个 结 点 深 度 为 3 5/5/2021 数 据 结 构 与 程 序 设 计 11 01 23 4 5 6 7 8 9完 全 二 叉 树 10 11 12结 点 i的 左 子 结 点 是 2i+1 右 子 结 点 是 2i+2结 点 i的 父 结 点 是 (i-1)/2堆 排 序 利 用 了 这 种 特 点 。 5/5/2021 数 据 结 构 与 程 序 设 计 12 10.1.2 Traversal of Binary Trees

9、n With preorder traversal （ 前 序 ） we first visit a node, then traverse its left subtree, and then traverse its right subtree.n With inorder traversal （ 中 序 ） we first traverse the left subtree, then visit the node, and then traverse its right subtree. n With postorder traversal（ 后 序 ） we first trave

10、rse the left subtree, then traverse the right subtree, and finally visit the node. 5/5/2021 数 据 结 构 与 程 序 设 计 13 写 出 这 棵 树 的 前 序 ， 后 序 ， 中序 访 问 的 结 果 5/5/2021 数 据 结 构 与 程 序 设 计 14 5/5/2021 数 据 结 构 与 程 序 设 计 15 5/5/2021 数 据 结 构 与 程 序 设 计 16 5/5/2021 数 据 结 构 与 程 序 设 计 17完 全 二 叉 树 的 数 组 表 示 一 般 二 叉 树 的

11、 数 组 表 示 二 叉 树 的 表 示 1. 5/5/2021 数 据 结 构 与 程 序 设 计 18 二 叉 树 的 表 示2. 链 表 表 示 5/5/2021 数 据 结 构 与 程 序 设 计 19 10.1.3 二 叉 树 的 链 式 实 现 5/5/2021 数 据 结 构 与 程 序 设 计 20 Implement of Binary Tree链 式 实 现 方 式 -节 点 的 数 据 结 构n template n struct Binary_node n / data members:n Entry data; n Binary_node *left; /指 向 左

12、孩 子 的 指 针n Binary_node *right; /指 向 右 孩 子 的 指 针n / constructors:n Binary_node( ); /默 认 的 不 带 参 数 的 构 造 函 数n Binary_node(const Entry /带 有 一 个 参 数 的 构 造 函 数n ; 5/5/2021 数 据 结 构 与 程 序 设 计 21 Implement of Binary Tree链 式 实 现 方 式 -节 点 的 实 现n #include Binary_node.hn template n Binary_node : Binary_node() n

13、 left = NULL;n right = NULL;n n template n Binary_node : Binary_node(const Entry n left = NULL; n right = NULL;n 5/5/2021 数 据 结 构 与 程 序 设 计 22 二 叉 树 的 基 本 方 法n 1. 遍 历n void preorder(void (*visit)(Entry n void inorder(void (*visit)(Entry n void postorder(void (*visit)(Entry n 2. 访 问 方 法n bool empty(

14、) const; n int size( ) const;n int height( ) const; /求 高 度 5/5/2021 数 据 结 构 与 程 序 设 计 23 二 叉 树 的 基 本 方 法n 3. 更 新 操 作n void insert(Entry n /插 入 一 个 新 的 节 点n 4. 构 造 二 叉 树n Binary_tree( ); n /构 造 函 数 。 5/5/2021 数 据 结 构 与 程 序 设 计 24 Implement of Binary Tree链 式 实 现 的 头 文 件n #include Binary_node.cppn temp

15、late n class Binary_tree n public: n Binary_tree( );n bool empty( ) const;n void preorder(void (*visit)(Entry n void inorder(void (*visit)(Entry n void postorder(void (*visit)(Entry n int size( ) const;n int height( ) const;n void insert(Entry 5/5/2021 数 据 结 构 与 程 序 设 计 25 Implement of Binary Tree二

16、叉 树 定 义 的 头 文 件n protected:n / Add auxiliary function prototypes here.n void recursive_preorder(Binary_node *sub_root, void (*visit)(Entry n void recursive_inorder(Binary_node *sub_root, void (*visit)(Entry n void recursive_postorder(Binary_node *sub_root, void (*visit)(Entry n Binary_node *root; /二

17、 叉 树 的 根 节 点n int count;n ; 5/5/2021 数 据 结 构 与 程 序 设 计 26 Implement of Binary Tree构 造 函 数 的 实 现n template n Binary_tree : Binary_tree( )n /* Post: An empty binary tree has been created. */n n root = NULL;n count = 0;n n template n bool Binary_tree : empty( ) constn /* Post: A result oftrue is return

18、ed if the binary tree is empty. Otherwise,false isn returned. */ n n return root = NULL;n 5/5/2021 数 据 结 构 与 程 序 设 计 27 Implement of Binary Tree二 叉 树 的 前 序 遍 历n template n void Binary_tree : preorder(void (*visit)(Entry n n template n void Binary_tree : recursive_preorder(Binary_node *sub_root, void

19、 (*visit)(Entry n recursive_preorder(sub_root-left, visit);n recursive_preorder(sub_root-right, visit);n n 5/5/2021 数 据 结 构 与 程 序 设 计 28 Implement of Binary Tree二 叉 树 的 中 序 遍 历n template n void Binary_tree : inorder(void (*visit)(Entry n n template n void Binary_tree : recursive_inorder(Binary_node

20、*sub_root, void (*visit)(Entry n (*visit)(sub_root-data);n recursive_inorder(sub_root-right, visit);n n 5/5/2021 数 据 结 构 与 程 序 设 计 29 Implement of Binary Tree二 叉 树 的 后 序 遍 历n template n void Binary_tree : postorder(void (*visit)(Entry n n template n void Binary_tree : recursive_postorder(Binary_node

21、 *sub_root, void (*visit)(Entry n recursive_postorder(sub_root-right, visit);n (*visit)(sub_root-data);n n 5/5/2021 数 据 结 构 与 程 序 设 计 30 Implement of Binary Tree求 二 叉 树 的 高 度n 假 设 当 前 二 叉 树 为 一 棵 完 全 二 叉 树 ， 则 如 何 求 其 高 度 ？n 启 发 ， 根 据 前 面 的 讨 论 ， 设 二 叉 树 的 节 点 数 为 n,， 完全 二 叉 树 的 高 度 为 ： log2n的 值 下 取

22、 整 。 n 则 有 2K=n; k为 满 足 条 件 的 最 大 整 数n 实 现 方 法 ：n K=0； tmp=20n 当 tmp = n时 ， K= K+1， tmp= tmp*2； / 2Kn 退 出 循 环 时 K的 值 ， 即 为 完 全 二 叉 树 的 高 度 。 5/5/2021 数 据 结 构 与 程 序 设 计 31 Implement of Binary Tree求 二 叉 树 的 高 度n template n int Binary_tree : size( ) constn n return count;n n template /该 方 法 适 用 于 完 全 二

23、 叉 树 ， 当 前 的 对 象 必 须 为 完 全 二 叉 树 。n int Binary_tree : height( ) const n n int count=size();n if(count=0)return 0; n int tmp=1;n for(int k=0; tmp=count; k+) tmp*=2;n return k;n 5/5/2021 数 据 结 构 与 程 序 设 计 32 插 入 ： 新 插 入 的 节 点 在 最 后 一 个 叶 子 结点 之 后 01 23 4 5 67 8 结 点 i的 左 子 结 点 是 2i+1 右 子 结 点 是 2i+2结 点

24、i的 父 结 点 是 (i-1)/2 5/5/2021 数 据 结 构 与 程 序 设 计 33 插 入 ： 新 插 入 的 节 点 在 最 后 一个 叶 子 结 点 之 后n 如 何 在 完 全 二 叉 树 的 末 尾 插 入 一 个 新 的 节 点 ： 只 需 要知 道 插 入 位 置 的 父 节 点 的 信 息 即 可 ， 即 父 节 点 的 指 针 。n 如 何 获 取 父 节 点 的 信 息 ： 必 须 从 根 节 点 一 层 一 层 访 问 ，获 取 父 节 点 的 信 息 。 n 实 现 :(1)当 前 插 入 点 的 编 号 tmpcount = size();n (2) 计

25、算 tmpcount是 左 孩 子 还 是 右 孩 子 。 将 信 息 入 栈 保 存 ;n (3) 计 算 tmpcount的 父 节 点 ， tmpcount= (tmpcount -1)/2;n (4) 当 tmpcount不 是 根 节 点 ， 继 续 步 骤 (2);n 经 过 上 述 计 算 之 后 ， 栈 内 保 存 了 从 根 到 插 入 点 的 路 径 。n (5) 依 次 将 信 息 出 栈 ， 逐 一 访 问 路 径 上 的 节 点 ， 获 取 父 节 点 的指 针 。n (6) 将 当 前 信 息 插 入 到 树 中 。 5/5/2021 数 据 结 构 与 程 序 设

26、 计 34 插 入 ： 新 插 入 的 节 点 在 最 后 一个 叶 子 结 点 之 后n template n void Binary_tree : insert(Entry n count+;n return;n 5/5/2021 数 据 结 构 与 程 序 设 计 35 Implement of Binary Treen MyStack numbers;n int item=0;n int tmpcount=size();n while(tmpcount0)n if(tmpcount%2=0)/the node is right childn numbers.push(2);/2 sta

27、nd for right child n n else/the node is left childn numbers.push(1);/1 stand for left childn n tmpcount=(tmpcount-1)/2;/get to the parentn 5/5/2021 数 据 结 构 与 程 序 设 计 36 Implement of Binary Treen Binary_node *current=root;n while (numbers.size()1) /出 栈 ， 直 到 栈 内 剩 余 一 个 节 点n numbers.top(item); n if(i

28、tem=1)current=current-left;n if(item=2)current=current-right;n numbers.pop(); n n numbers.top(item); /链 接 新 节 点n if(item=1)current-left=new Binary_node(x);n if(item=2)current-right=new Binary_node(x);n count+;n 5/5/2021 数 据 结 构 与 程 序 设 计 37 Implement of Binary Treen template n void print(Entry n n v

29、oid main() n Binary_tree mytree;n for(int i=0; i10; i+)mytree.insert(Record(i);n coutTree size is: mytree.size()endl;n coutTree height is: mytree.height()endl;n coutPreorder:endl;n mytree.preorder(print);n coutendl;n coutinorder:endl; n mytree.inorder(print);n coutendl;n coutPostorder:endl;n mytree.

30、postorder(print);n coutendl;n cin.get();n 5/5/2021 数 据 结 构 与 程 序 设 计 38 Implement of Binary Treen 目 录 Binary_Tree下 例 程n Tree size is: 10n Tree height is: 4n Preorder:n 0 1 3 7 8 4 9 2 5 6n inorder:n 7 3 8 1 9 4 0 5 2 6 n Postorder:n 7 8 3 9 4 1 5 6 2 0 01 23 4 5 67 8 9 5/5/2021 数 据 结 构 与 程 序 设 计 39 课 后 作 业 P441n （ 1） E5 用 递 归 的 方 法 计 算 二 叉 树 的 叶子 节 点 数 。n （ 2） E6 用 递 归 的 方 法 计 算 二 叉 树 的 高度 。