二叉树的性质和遍历
麦兜 / 2019-10-27 / 数据结构 / 阅读量 211

二叉树特征

  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
1 + 5 =
快来做第一个评论的人吧~