菜鸟笔记
提升您的技术认知

求二叉树的结点个数-ag真人游戏

求二叉树的结点个数
如下利用递归来实现
方法一

根据递归函数实现,如果树不为空,根节点为1
1 统计根节点左子树
2 统计根节点右子树
3 将左子树节点个数 右子树节点个数 根节点个数1=即为整颗树的节点个数
4 统计左右子树的节点个数也是按照1~3的步骤进行
5 当树为空时,根节点的个数为0,即为递归函数的出口。
123 //方法一 : 结点个数= 树的左子树结点,加右子树结点 根结点(1)
124 
125 size_t treesize(treenode* root)
126 {
127     if(root==null)
128     {
129         return 0
130     }
131     //统计左子树的节点个数
132     size_t lsize=treesize(root->lchild);
133     //统计右子树的节点个数
134     size_t rsize=treesize(root->rchild);
135     return 1 lsize rsize;                                                                                                                                          
136 }

方法二
将先序遍历打印操作改写为计数器加1操作,当遍历到非空节点时计数器 1

    1 先遍历根节点,计数器 1
    2 然后递归遍历左子树
    3 再递归遍历右子树
    4 子树的遍历也遵循1~3的过程
    5 当子树为空,直接返回,跳出递归函数

递归过程中计数器一直在改变,所以计数器应在递归函数外面,然后通过其地址改变值

139 void _treesize1(treenode* root, size_t* count)
140 {
141     if(root==null)
142     {
143         //空树                                                                                                                                                     
144         return ;
145     }
146     if(count==null)
147     {
148         //非法输入
149         return ;
150     }
151     (*count)  ;
152     _treesize1(root->lchild,count);
153     _treesize2(root->rchild,count);
154     return ;
155 }
156 size_t treesize1(treenode* root)
157 {
158     if(root==null)
159     {
160         //空树
161         return 0;
162     }
163     size_t count=0;
164     _treesize1(root,&count);
165     return count ;
166 }
网站地图