C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

C++使用递归和非递归算法实现的二叉树叶子节点个数计算方使用递归和非递归算法实现的二叉树叶子节点个数计算方

法法

主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统

计相关操作技巧,需要的朋友可以参考下

本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考，具体如下：

/*求二叉树叶子节点个数 -- 采用递归和非递归方法

经调试可运行源码及分析如下：

***/

using std::stack;

/*二叉树结点定义*/

typedef struct BTreeNode

{

char elem;

struct BTreeNode *pleft;

struct BTreeNode *pright;

}BTreeNode;

/*

求二叉树叶子节点数

int get_leaf_number(BTreeNode *proot)

{

if(proot == NULL)

return 0;

if(proot->pleft == NULL && proot->pright == NULL)

return 1;

return (get_leaf_number(proot->pleft) + get_leaf_number(proot->pright));

}

/*非递归：本例采用先序遍历计算

判断当前访问的节点是不是叶子节点，然后对叶子节点求和即可。

stack <BTreeNode*> st;

while (proot != NULL || !st.empty())

{

while (proot != NULL)

{

cout << "节点：" << proot->elem << endl;

st.push(proot);

proot = proot->pleft;

}

if (!st.empty())

}

}

return num;

}

/*初始化二叉树根节点*/

BTreeNode* btree_init(BTreeNode* &bt)

{

bt = NULL;

return bt;

}