第5章 树及二叉树0524.ppt

三种遍历算法的执行轨迹 1. 遍历过程中，每个结点经历过3次： 1）从其双亲到该结点 2）从左子树返回 3）从右子树返回 2. 三种遍历序列即是访问的时刻不同而已 1）从其双亲到该结点—第一次访问（先序） 2）从左子树返回—第二次访问（中序） 3）从右子树返回—第三次访问（后序） template class T BiTree ::BiTree(BiNodeT * root){ creat(root)；this-root=root； } void BiTree ::Creat(BiNodeT * root){ cinch; if (ch==#) root=NULL; else { root=new BiNodeT; root-data=ch; creat(root-lchild); creat(root-rchild); } } 建立二叉递归算法一 5.4 二叉树的存储 templateclass T BiTreeT::BiTree( ) { cout请输入创建一棵二叉树的结点数据endl; this-root = Creat( ); } BiNodeT* BiTreeT::Creat( ){ BiNodeT* root; T ch; cinch; if (ch==#) root = NULL; else{ root = new BiNodeT; //生成一个结点 root-data=ch; root-lchild = Creat( ); //递归建立左子树 root-rchild = Creat( ); //递归建立右子树 } return root; } 建立二叉递归算法二 5.4 二叉树的存储 二叉树算法设计拓展 遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。 void InOrder (BiNodeT *root) { if (root==NULL) return; else { InOrder(root-lchild); coutroot-data; InOrder(root-rchild); } } 二叉树算法设计拓展 设计算法求二叉树的结点个数。 int Count(BiNode *root) { if (!root) return 0； else { return Count(root-lchild) +Count(root-rchild)+1; } } 二叉树算法设计拓展 设计算法按前序次序打印二叉树中的叶子结点。 void PreOrder(BiNode *root) { if (root) { if (!root-lchild !root-rchild) coutroot-data; PreOrder(root-lchild); PreOrder(root-rchild); } } 二叉树算法设计拓展 设计算法求二叉树的深度。 int Depth(BiNode *root) { if (root= =NULL) return 0; else { hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; } } 三叉链表 5.4 二叉树的存储 G F E D B A A B C D E F G ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ C 在二叉链表中，如何求某结点的双亲？ 三叉链表 lchild data parent rchild 在二叉链表的基础上增加了一个指向双亲的指针域。 结点结构 其中：data、lchild和rchild三个域的含义同二叉链表的结点结构； parent域为指向该结点的双亲结点的指针。 5.4 二叉树的存储 A B C D E F