menu Error0 Blog
二叉树的性质和遍历
86 浏览 | 2019-10-27 | 分类:数据结构 | 标签:

二叉树特征

  1. 一个二叉树第i层的最大结点数为 2^i-1,当i>=1时
  2. 深度为K的二叉树最大节结点总数为: (2^k)-1 ,当k>=1时

二叉树遍历方法

  • ​ 先序 (根 --> 左子树-->右子树)
  • ​ 中序 (左子树 --> 根-->右子树)
  • ​ 后序 (左子树 --> 右子树-->根)
  • ​ 层次遍历 (从上到下、从左到右)

序号关系

当根节点 i>1时,子节点序号等于 左(i 2) 右(i 2)+1,而父节点的序号等于(i/2)取整

存储结构代码

typedef struct TreeNode {
    
char val; 
/*左右节点*/
struct TreeNode *left; 
struct TreeNode *right;
};

二叉树遍历代码

先序遍历

void PreOrder(struct TreeNode* root)
{
    if (root == NULL) {
        return;
    }
        printf("%c", root->val);
        PreOrderTree(root->left);
        PreOrderTree(root->right);
}

中序遍历

void Middle(struct TreeNode* root)
{
    if (root == NULL) {
        return;
    }
        Middle(root->left);
        printf("%c", root->val);
        Middle(root->right);
}

后序遍历

void PostOrder(struct TreeNode* root)
{
    if (root == NULL) {
        return;
    }
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%c", root->val);
}

层序遍历

void LevelOrderTraversal(struct TreeNode* root)
{
    if (root == NULL)
        return;
    queue<TreeNode*> Q;
    Q.push(root);
    while (!Q.empty())
    {
        cout<< Q.front()->val;
        if (Q.front()->left)
        {
            Q.push(Q.front()->left);
        }
        if (Q.front()->right)
        {
            Q.push(Q.front()->right);
        }
        Q.pop();
    }
}

遍历结果对比

遍历方式结果
先序遍历ABDECF
中序遍历DBEACF
后序遍历CEBFCA
层序遍历ABCDEF
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

Emoji

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 46

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 48

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 87

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 89