二叉树的构造、深度优先遍历(栈)和广度优先遍历(队列)C++实现
程序员文章站
2022-05-21 19:28:53
...
struct Tree{
char data;
struct Tree *lchild;
struct Tree *rchild;
};
int index_global = 0;
Tree * treeNodeConstructor(Tree *root, char data[]);
void depthFirstSearch(Tree *root);
void breadthFirstSearch(struct Tree *root);
int main() {
char data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#'};
Tree *tree = NULL;
tree = treeNodeConstructor(tree, data);
cout << "深度遍历的结果:" <<endl;
depthFirstSearch(tree);
cout <<endl;
cout << "广度遍历的结果:" <<endl;
breadthFirstSearch(tree);
cout <<endl;
delete tree;
return 0;
}
Tree * treeNodeConstructor(Tree *root, char data[]){
char e = data[index_global ++];
if (e == '#') {
root = NULL;
}else{
root = new Tree;
root->data = e;
root->lchild = treeNodeConstructor(root->lchild, data);
root->rchild = treeNodeConstructor(root->rchild, data);
}
return root;
}
// 利用栈实现二叉树的深度优先遍历:
// 栈不空时,root指向栈顶元素,栈顶元素出栈;
// 若root 的右子树不空,则先压栈,若root左子树不空,则再压栈;
// 循环,栈顶元素出栈顺序即为深度优先遍历顺序
void depthFirstSearch(Tree *root){
stack<Tree *> nodeStack;
nodeStack.push(root);
while (!nodeStack.empty()) {
root = nodeStack.top();
cout << root->data;
nodeStack.pop();
if (root->rchild) { // 先把右子树压栈
nodeStack.push(root->rchild);
}
if (root->lchild) { // 再把左子树压栈
nodeStack.push(root->lchild);
}
}
}
// 利用队列实现二叉树的广度优先遍历:
// 栈不空时,root指向队首元素,队首元素出队;
// 若root 的左子树不空,则先入队,若root右子树不空,则再入队;
// 循环,队首元素出队顺序即为广度优先遍历顺序
void breadthFirstSearch(Tree *root){
queue<Tree *> nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
root = nodeQueue.front();
cout << root->data;
nodeQueue.pop();
if (root->lchild) {
nodeQueue.push(root->lchild); // 先把左子树入队
}
if (root->rchild) {
nodeQueue.push(root->rchild); // 再把右子树入队
}
}
}
上一篇: 二叉树的深度优先遍历以及广度优先遍历实现
推荐阅读
-
Java实现二叉树的深度优先遍历和广度优先遍历算法示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
PHP实现二叉树的深度优先与广度优先遍历方法
-
[PHP] 算法-邻接矩阵图的广度和深度优先遍历的PHP实现
-
PHP实现二叉树的深度优先与广度优先遍历方法_PHP
-
PHP实现二叉树的深度优先与广度优先遍历方法
-
数据结构与算法1:二叉树(binary_tree)的前、中、后序(深度优先)和广度优先遍历及python代码实现
-
【数据结构】【树及算法】二叉树的实现,树的应用:表达式解析,树的遍历,优先队列和二叉堆
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
图数据结构,以及使用递归方式实现图的深度优先和广度优先遍历