数据结构二叉树

二叉树: 每个节点最多具有两个子节点

二叉搜索树（二叉排序树，B树）: 左节点小于父节点，右节点大于父节点

完整的二叉树: 深度为k，并且有

二叉树数据结构二叉排序树数据结构二叉排序树，即每一层的节点数是该层中的最大节点数

完整的二叉树: 除最后一层外，其他所有层均已满，最后一层的叶节点集中在左侧

链接列表实际上是一棵特殊的树

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

序言: root-left-right

后期处理: 左右根

中间顺序: 从左到右

对于二进制排序的树，恰好对中间顺序遍历进行了排序

递归遍历:

//先序+递归  
void ergodic(TreeNode* root)
{
    if (root == NULL)
        return;
    else
    {
        printf(%d/n, root->val);
        ergodic(root->left);
        ergodic(root->right);
    }
}
//后序+递归  
void ergodic(TreeNode* root)
{
    if (root == NULL)
        return;
    else
    {
        ergodic(root->left);
        ergodic(root->right);
        printf(%d/n, root->val);
    }
}
//中序+递归  
void ergodic(TreeNode* root)
{
    if (root == NULL)
        return;
    else
    {
        ergodic(root->left);
        printf(%d/n, root->val);
        ergodic(root->right);
    }
}

非递归遍历:

//先序+非递归  
void ergodic(TreeNode* root)
{
    stack<TreeNode*> st;
    
    while(root != NULL || !st.empty())
    {
        while (root != NULL)
        {
            printf(%d/n, root->val);
            st.push(root);
            root = root->left;
        }
        
        if (!st.empty())
        {
            root = st.top()->right;
            st.pop();
        }
    }
}

TreeNode* find(TreeNode* root, int data)
{
    while(root != NULL)
    {
        if (data == root->val)
            return root;
        else if (data<root->val)
            root = root->left;
        else
            root = root->right;
    }
    return NULL;
}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-181237-1.html