7.3.3递归遍历算法的应用【例7.6】假设二叉树采用二叉链存储结构存储，设计一个算法求一棵给定二叉树中的结点个数。解：求一棵二叉树中的结点个数是以遍历算法为基础的，任何一种遍历算法都可以出一棵二叉树中的结点个数。11/49
【例7.6】假设二叉树采用二叉链存储结构存储，设计一个算法求一棵给 定二叉树中的结点个数。 解：求一棵二叉树中的结点个数是以遍历算法为基础的，任何一种遍 历算法都可以出一棵二叉树中的结点个数。 11/49
public static int Nodecount1（BTreeclassbt）//基于先序遍历求结点个数(return NodeCount1i(bt.b);7private static int NodeCountii(BTNode<character> t)int m,n,k;//空树结点个数为0if(t==null)return o;k=1;1/根结点计数1，相当于访间根结点1/遍历求左子树的结点个数m=NodeCount11(t.lchild);n=NodeCount11(t.rchild);//遍历求右子树的结点个数return k+m+n;12/49
public static int NodeCount1(BTreeClass bt) //基于先序遍历求结点个数 { return NodeCount11(bt.b); } private static int NodeCount11(BTNode<Character> t) { int m,n,k; if (t==null) //空树结点个数为0 return 0; k=1; //根结点计数1，相当于访问根结点 m=NodeCount11(t.lchild); //遍历求左子树的结点个数 n=NodeCount11(t.rchild); //遍历求右子树的结点个数 return k+m+n; } 12/49
public static int Nodecount2（BTreeclassbt）//基于中序遍历求结点个数(return NodeCount21(bt.b);7private static int NodeCount2i(BTNode<Character> t)int m,n,k;T//空树结点个数为0if(t==null)return o;1/遍历求左子树的结点个数m=NodeCount21(t.lchild);k=1;1/根结点计数1，相当于访间根结点n=NodeCount21(t.rchild);//遍历求右子树的结点个数return k+m+n;13/49
public static int NodeCount2(BTreeClass bt) //基于中序遍历求结点个数 { return NodeCount21(bt.b); } private static int NodeCount21(BTNode<Character> t) { int m,n,k; if (t==null) //空树结点个数为0 return 0; m=NodeCount21(t.lchild); //遍历求左子树的结点个数 k=1; //根结点计数1，相当于访问根结点 n=NodeCount21(t.rchild); //遍历求右子树的结点个数 return k+m+n; } 13/49
public static int Nodecount3（BTreeclassbt）//基于后序遍历求结点个数(return NodeCount31(bt.b);7private static int NodeCount3i(BTNode<Character> t)int m,n,k;广//空树结点个数为0if(t==null)return o;1/遍历求左子树的结点个数m=NodeCount31(t.lchild);1/遍历求右子树的结点个数n=NodeCount31(t.rchild);k=1;//根结点计数1，相当于访间根结点return k+m+n;14/49
public static int NodeCount3(BTreeClass bt) //基于后序遍历求结点个数 { return NodeCount31(bt.b); } private static int NodeCount31(BTNode<Character> t) { int m,n,k; if (t==null) //空树结点个数为0 return 0; m=NodeCount31(t.lchild); //遍历求左子树的结点个数 n=NodeCount31(t.rchild); //遍历求右子树的结点个数 k=1; //根结点计数1，相当于访问根结点 return k+m+n; } 14/49
也可以从递归算法设计的角度来求解。设f(b)求二叉树b中所有结点个数，它是“大问题”，f(b.lchild)和f(b.rchild)分别求左、右子树的结点个数。NR当b=nullf(b)=0其他情况f(b)=f(b.lchild)+f(b.rchild)+115/49
也可以从递归算法设计的角度来求解。设f(b)求二叉树b中所有结点个 数，它是“大问题”，f(b.lchild)和f(b.rchild)分别求左、右子树的 结点个数。 N L R f(b)=0 当b=null f(b)=f(b.lchild)+f(b.rchild)+1 其他情况 15/49