二叉树递归遍历实现

/*
二叉树的遍历
深度优先遍历，偏向于纵深
前序遍历：根节点、左子树、右子树
中序遍历：左子树、根节点、右子树
后续遍历：左子树、右子树、根节点

广度优先遍历
层序遍历：按照二叉树从根节点每层进行遍历
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int VALUE_TYPE;

struct bstree_node_st
{
    VALUE_TYPE data;
    struct bstree_node_st *left;
    struct bstree_node_st *right;
};

struct bstree_st
{
    struct bstree_node_st *node;
};


struct bstree_node_st* bstree_create_node(VALUE_TYPE key)
{
    struct bstree_node_st *node = (struct bstree_node_st*)malloc(sizeof(struct bstree_node_st));
    memset(node, 0, sizeof(struct bstree_node_st));
    node->data = key;
    node->left = NULL;
    node->right = NULL;

    return node;
}


int bstree_insert_node(struct bstree_st* T, VALUE_TYPE key)
{
    if (T == NULL) return -1;
    if (T->node == NULL)
    {
        T->node = bstree_create_node(key);
        return 0;
    }
    struct bstree_node_st *node = T->node;
    struct bstree_node_st *tmp = T->node;

    //遍历树并找到插入位置的叶子节点
    while (node != NULL)
    {
        // 保存节点(比较后，要么左、要么右孩子为空)
        tmp = node;  
        if (key < node->data)
        {
            node = node->left;
        }
        else if (key > node->data)
        {
            node = node->right;
        }
        else // 相等情况，则报错
        {
            return -1;
        }
    }

    // 值与节点进行大小比较，将创建的新节点赋值给左或右孩子
    if (key < tmp->data)
    {
        tmp->left = bstree_create_node(key);
    }
    else
    {
        tmp->right = bstree_create_node(key);
    }

    return 0;
}

//前序遍历
int bstree_before_traverse(struct bstree_node_st* T)
{
    if (T  == NULL)
    {
        return -1;
    }
    printf("%d ", T->data);
    bstree_before_traverse(T->left);
    bstree_before_traverse(T->right);
	return 0;
}

//中序遍历
int bstree_mid_traverse(struct bstree_node_st* T)
{
    if (T  == NULL)
    {
        return -1;
    }
    
    bstree_mid_traverse(T->left);
    printf("%d ", T->data);
    bstree_mid_traverse(T->right);
	return 0;
}


//后序遍历
int bstree_after_traverse(struct bstree_node_st* T)
{
    if (T  == NULL)
    {
        return -1;
    }
    bstree_after_traverse(T->left);
    bstree_after_traverse(T->right);
    printf("%d ", T->data);
	return 0;
}


//叶子节点数目求取
int bstree_get_leaves_num(struct bstree_node_st* T, int *num)
{
    if (T  == NULL)
    {
        return -1;
    }
    if (T->left == NULL && T->right == NULL)
    {
        (*num)++;
    }
    bstree_get_leaves_num(T->left, num);
    bstree_get_leaves_num(T->right, num);

}
int main()
{
    struct bstree_st T;
    T.node = NULL;
    bstree_insert_node(&T, 10);
    bstree_insert_node(&T, 20);
    bstree_insert_node(&T, 5);
    printf("before_traverse:");
    bstree_before_traverse(T.node);
    printf("\n");

    printf("mid_traverse:");
    bstree_mid_traverse(T.node);
    printf("\n");
    
    printf("after_traverse:");
    bstree_after_traverse(T.node);
    printf("\n");
    
    int num = 0;
    bstree_get_leaves_num(T.node, &num);
    
    printf("leaves num is %d\n", num);
    return 0;
}

#include <iostream>
#include <memory>
#include <vector>
#include <deque>

#define VALUE_TYPE int
struct TreeNode
{

    VALUE_TYPE data;
    std::shared_ptr<TreeNode> left_node_ptr;
    std::shared_ptr<TreeNode> right_node_ptr;
    TreeNode(VALUE_TYPE data) : data(data), left_node_ptr(nullptr), right_node_ptr(nullptr)
    {
    }
};

class BinTree
{
public:
    BinTree()
    {
        root_node_ptr_ = nullptr;
    }
    std::shared_ptr<TreeNode> CreateNode(VALUE_TYPE data)
    {
        std::shared_ptr<TreeNode> node_ptr = std::make_shared<TreeNode>(data);
        return node_ptr;
    }
    int InsertNode(VALUE_TYPE data)
    {
        if (root_node_ptr_ == nullptr)
        {
            root_node_ptr_ = CreateNode(data);
            return 0;
        }
        std::shared_ptr<TreeNode> tmp_node_ptr = root_node_ptr_;
        std::shared_ptr<TreeNode> leaf_node_ptr = nullptr;
        while (tmp_node_ptr)
        {
            leaf_node_ptr = tmp_node_ptr;
            if (data < tmp_node_ptr->data)
            {
                tmp_node_ptr = tmp_node_ptr->left_node_ptr;
            }
            else if (data > tmp_node_ptr->data)
            {
                tmp_node_ptr = tmp_node_ptr->right_node_ptr;
            }
            else
            {
                return -1;
            }
        }
        if (data < leaf_node_ptr->data)
        {
            leaf_node_ptr->left_node_ptr = CreateNode(data);
        }
        else
        {
            leaf_node_ptr->right_node_ptr = CreateNode(data);
        }
        return 0;
    }
    int BeforeTraverseTree(std::shared_ptr<TreeNode> node_ptr)
    {
        if (node_ptr == nullptr)
        {
            return -1;
        }
        //tree_node_ptr_container.push_back(node_ptr);
        std::cout << node_ptr->data << " ";
        BeforeTraverseTree(node_ptr->left_node_ptr);
        BeforeTraverseTree(node_ptr->right_node_ptr);
    }
    int MidTraverseTree(std::shared_ptr<TreeNode> node_ptr)
    {
        if (node_ptr == nullptr)
        {
            return -1;
        }
        //tree_node_ptr_container.push_back(node_ptr);
        MidTraverseTree(node_ptr->left_node_ptr);
        std::cout << node_ptr->data << " ";
        MidTraverseTree(node_ptr->right_node_ptr);
    }
    int AfterTraverseTree(std::shared_ptr<TreeNode> node_ptr)
    {
        if (node_ptr == nullptr)
        {
            return -1;
        }
        //tree_node_ptr_container.push_back(node_ptr);
        AfterTraverseTree(node_ptr->left_node_ptr);
        AfterTraverseTree(node_ptr->right_node_ptr);
        std::cout << node_ptr->data << " ";
    }
    int GetTreeLeafNodeNum(std::shared_ptr<TreeNode> node_ptr, int *num)
    {
        if (node_ptr == nullptr)
            return 0;
        if (node_ptr->left_node_ptr == nullptr && node_ptr->right_node_ptr == nullptr)
        {
            (*num)++;
            return 0;
        }
        GetTreeLeafNodeNum(node_ptr->left_node_ptr, num);
        GetTreeLeafNodeNum(node_ptr->right_node_ptr, num);
    }
    // 广度优先搜索使用deque进行实现，根节点插入，取出队头，并将左右孩子尾部插入到队列
    int BFSTree()
    {
        if (root_node_ptr_ == nullptr)
            return -1;

        std::deque<std::shared_ptr<TreeNode>> de;
        de.push_back(root_node_ptr_);
        while (!de.empty())
        {
            // 获取队头
            auto tmp_node_ptr = de.front();
            std::cout << tmp_node_ptr->data << " ";
            // 取出队头
            de.pop_front();
            if (tmp_node_ptr->left_node_ptr != nullptr)
            {
                de.push_back(tmp_node_ptr->left_node_ptr);
            }
            if (tmp_node_ptr->right_node_ptr != nullptr)
            {
                de.push_back(tmp_node_ptr->right_node_ptr);
            }
        }
    }
    std::shared_ptr<TreeNode> GetRootNode()
    {
        return root_node_ptr_;
    }

private:
    std::shared_ptr<TreeNode> root_node_ptr_;
    std::vector<std::shared_ptr<TreeNode>> tree_node_ptr_container;
};
int main()
{
    std::shared_ptr<BinTree> tree = std::make_shared<BinTree>();
    tree->InsertNode(10);
    tree->InsertNode(2);
    tree->InsertNode(30);
    tree->InsertNode(15);

    auto root_node = tree->GetRootNode();
    std::cout << "before traverse:";
    tree->BeforeTraverseTree(root_node);
    std::cout << std::endl;

    std::cout << "middle traverse:";
    tree->MidTraverseTree(root_node);
    std::cout << std::endl;

    std::cout << "after traverse:";
    tree->AfterTraverseTree(root_node);
    std::cout << std::endl;

    int leaf_node_num = 0;

    tree->GetTreeLeafNodeNum(root_node, &leaf_node_num);
    std::cout << "leaf node num:" << leaf_node_num << std::endl;
    std::cout << std::endl;
    std::cout << "BFS:" << std::endl;
    tree->BFSTree();
    return 0;
}