数据结构考研复习(3)

东大计算机 数据结构考研复习(3)

3 基本应用树和二叉树应用 例1 统计二叉树中叶子结点的个数

基本思想 实现这个操作只要对二叉树"遍历"一 遍，并在遍历过程中对"叶子结点计数"即 可。显然这个遍历的次序可以随意，即先 序或中序或后序均可，只是为了在遍历的 同时进行计数，需要在算法的参数中设一 个"计数器"。

东大计算机 数据结构考研复习(3)

3 基本应用先序遍历统计叶子结点的个数void CountLeaf (BiTree T, int& count) { // 以 count 返回二叉树中叶子结点的数目 if ( T ) { if ((!T->Lchild)&& (!T->Rchild)) count++; // 对叶子结点计数 CountLeaf( T->Lchild, count); CountLeaf( T->Rchild, count); } // if } // CountLeaf

东大计算机 数据结构考研复习(3)

3 基本应用例2 求二叉树的深度基本思想 二叉树的深度为树中叶子结点所在层 次的最大值。而结点的层次需从根结点起 递推，根结点为第一层的结点，第 k 层结 点的子树根在第 k+1 层。由此需要在先序 遍历二叉树的过程中求每个结点的层次数， 并将其中的最大值设为二叉树的深度。

东大计算机 数据结构考研复习(3)

3 基本应用(1)先序遍历求二叉树的深度void BiTreeDepth1 (BiTree T, int level, int &depth) { // T指向二叉树的根，level 为 T 所指结 //点所在层次，其初值为1,depth 为当前 //求得的最大层次,其初值为0

东大计算机 数据结构考研复习(3)

3 基本应用if (T){ if (level>depth) depth=level; BiTreeDepth(T->Lchild, level+1, depth); BiTreeDepth(T->Rchild, level+1, depth); }// if }// BiTreeDepth

东大计算机 数据结构考研复习(3)

3 基本应用(2)后序遍历求二叉树的深度int BiTreeDepth2 (BiTree T ){ // 返回二叉树 的深度 if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild );

东大计算机 数据结构考研复习(3)

3 基本应用if (depthLeft > depthRight) depthval =depthLeft+1; else depthval =depthRight+1; } // else return depthval; }// BiTreeDepth2

东大计算机 数据结构考研复习(3)

3 基本应用例3 复制二叉树 基本思想 复制二叉树，其实质就是就是按照原 二叉树的二叉链表另建立一个新的二叉链 表。 先分别复制已知二叉树的左、右子树， 然后生成一个新的根结点，则复制得到的 两棵子树的根指针应是这个新生成的结点 的左、右指针域的值。“访问”操作是生 成二叉树的一个结点。

东大计算机 数据结构考研复习(3)

3 基本应用基本操作为：生成一个结点。 NEWT T 根元素 左子树 右子树 左子树 根元素 右子树

东大计算机 数据结构考研复习(3)

3 基本应用newT二叉树的复制过程^B E^ C^ ^F^ A

AB E

CD H G

F

^D^^H^

G^K^

K

东大计算机 数据结构考研复习(3)

3 基本应用后序遍历复制二叉树 BiTNode *CopyTree(BiTNode *T){ // T为已知二叉树的根指针，算法返回 //它的复制品的根指针 if (!T ) return NULL; // 复制一棵空树

东大计算机 数据结构考研复习(3)

3 基本应用if (T->Lchild) newlptr = CopyTree(T->Lchild); // 复制(遍历)左子树 else newlptr = NULL; if (T->Rchild) newrptr = CopyTree(T->Rchild); // 复制(遍历)右子树 else newrptr = NULL;

东大计算机 数据结构考研复习(3)

3 基本应用newnode = GetTreeNode(T->data, newlptr, newrptr); // 生成根结点 return newnode;}

东大计算机 数据结构考研复习(3)

3 基本应用BiTNo

de *GetTreeNode (TElemType item, BiTNode *lptr, BiTNode *rptr) { // 生成一个其元素值为 item,左 //指针为 lptr,右指针为 rptr 的结点 T = new BiTNode; T-> data = item; T-> Lchild = lptr; T-> Rchild = rptr; return T; }

东大计算机 数据结构考研复习(3)

3 基本应用例4 建立二叉树的二叉链表结构 假设二叉树以由“根”、“左 子树串”和“右子树串” 联接而成 的字符串表示。例如，空树以“#” 表示，只有一个根结点A的二叉树 以“A##”表示。

东大计算机 数据结构考研复习(3)

3 基本应用先序建立二叉链表二叉树的算法描述 [1] 若输入的字符是‘#’, 则建立空树； 否则，建立根结点； [2] 读取字符，转[1], 递归建立左子树； [3] 读取字符，转[1], 递归建立右子树。