欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的构造、深度优先遍历(栈)和广度优先遍历(队列)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);     // 再把右子树入队
        }
    }
}