二叉树的概念

[bosthhe1]

1，二叉树是每个节点的度小于等于2的树。 2，树的高度h计算公式为h = log以2为底N的对数。（N代表的为树的节点数） 3，在树中，叶子就代表的为此节点没有子节点。 4，二叉树中不能存在环，就如a指向b和c，d就不能指向b或c。 5，二叉树分为满二叉树，完全二叉树 满二叉树是除了最底层的节点（底层子节点为满），其余树的节点都有2个子节点 完全二叉树是除了底层和底层上一层，其余树的节点都有两个子节点 完全二叉树的底层可以不为满，但是底层的子节点必须依次排列。 在二叉树中，若n0代表没有子节点，n2代表有两个子节点满足公式 n0= n2+1

[bosthhe1]

计算树有多少个叶子
typedef char STDataType;
int size = 0;
typedef struct BinaryTree
{
    BinaryTree * right;
    BinaryTree * left;
    STDataType a;
}BinaryTree;

int NumBinaryTree(BinaryTree *A)
{
    if (A->left == NULL&&A->right==NULL)
        return 1;
    else
        return NumBinaryTree(A->left) + NumBinaryTree(A->right);
}
void TestBinaryTree(BinaryTree *A)
{
    if (A == NULL)
    {
        printf("NULL ");
        return;
    }
    TestBinaryTree(A->left);
    TestBinaryTree(A->right);
    printf("%c ", A->a);
}
void TestBinaryTree1()
{
    BinaryTree *A = (BinaryTree *)malloc(sizeof(BinaryTree));
    A->a = 'A';
    A->left = NULL;
    A->right = NULL;
    BinaryTree *B = (BinaryTree *)malloc(sizeof(BinaryTree));
    B->a = 'B';
    B->left = NULL;
    B->right = NULL;
    BinaryTree *C = (BinaryTree *)malloc(sizeof(BinaryTree));
    C->a = 'C';
    C->left = NULL;
    C->right = NULL;
    BinaryTree *D = (BinaryTree *)malloc(sizeof(BinaryTree));
    D->a = 'D';
    D->left = NULL;
    D->right = NULL;
    BinaryTree *E = (BinaryTree *)malloc(sizeof(BinaryTree));
    E->a = 'E';
    E->left = NULL;
    E->right = NULL;
    A->left = B;
    A->right = C;
    B->left = D;
    B->right = E;
    TestBinaryTree(A);
    int c = NumBinaryTree(A);
    printf("\n");
    printf("%d\n", c);
    int b = NumBinaryTree(B);
    printf("%d\n", b);
}

int main()
{
    TestBinaryTree1();
    return 0;
}

[bosthhe1]

构建二叉树，计算二叉树高度
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef char STDataType;
int size = 0;
typedef struct BinaryTree
{
    BinaryTree * right;
    BinaryTree * left;
    STDataType a;
}BinaryTree;

BinaryTree* TestBinaryTree1(char *p, int *i) //构造二叉树，以#键代表NULL
{
    if (p[*i] == '#')
    {
        (*i)++;
        return NULL;
    }
    BinaryTree *Tree = (BinaryTree *)malloc(sizeof(BinaryTree));
    Tree->a = p[*i];
    ++(*i);
    Tree->left = TestBinaryTree1(p, i);
    Tree->right = TestBinaryTree1(p, i);
    return Tree;
}
int BinaryTreeHight(BinaryTree *p)//求树的高度
{
    if (p == NULL)
    {
        return 0;
    }
    return BinaryTreeHight(p->left)>BinaryTreeHight(p->right) ? BinaryTreeHight(p->left) + 1 : BinaryTreeHight(p->right) + 1;
}

int main()
{
    char arr[100] = { 0 };
    scanf("%s", arr);
    int i = 0;
    BinaryTree *tree = TestBinaryTree1(arr, &i);
    int b = BinaryTreeHight(tree);
    return 0;
}

[bosthhe1]

//计算树有多少个节点
typedef char STDataType;
int size = 0;
typedef struct BinaryTree
{
    BinaryTree * right;
    BinaryTree * left;
    STDataType a;
}BinaryTree;

int NumBinaryTree(BinaryTree *A)
{
    if (A==NULL)
        return 0;
    else
        return NumBinaryTree(A->left) + NumBinaryTree(A->right)+1;
}

void TestBinaryTree1()
{
    BinaryTree *A = (BinaryTree *)malloc(sizeof(BinaryTree));
    A->a = 'A';
    A->left = NULL;
    A->right = NULL;
    BinaryTree *B = (BinaryTree *)malloc(sizeof(BinaryTree));
    B->a = 'B';
    B->left = NULL;
    B->right = NULL;
    BinaryTree *C = (BinaryTree *)malloc(sizeof(BinaryTree));
    C->a = 'C';
    C->left = NULL;
    C->right = NULL;
    BinaryTree *D = (BinaryTree *)malloc(sizeof(BinaryTree));
    D->a = 'D';
    D->left = NULL;
    D->right = NULL;
    BinaryTree *E = (BinaryTree *)malloc(sizeof(BinaryTree));
    E->a = 'E';
    E->left = NULL;
    E->right = NULL;
    A->left = B;
    A->right = C;
    B->left = D;
    B->right = E;
    int c = NumBinaryTree(A);
    printf("%d\n", c);

}

int main()
{
    TestBinaryTree1();
    return 0;
}