数据结构二叉树的实现

二叉树是一种非常常见的数据结构，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。下面是二叉树的实现方法：

1.定义二叉树节点的结构体类型

typedef struct BinaryTreeNode{
    BTDataType _data;//数据域
    struct BinaryTreeNode* _left;//存储左孩子
    struct BinaryTreeNode* _right;//存储右孩子
}BTNode;

2.创建二叉树

BTNode* CreateBinaryTree(BTDataType* a, int* pi){
    if(a[*pi] == '#'){//如果当前节点是空节点
        (*pi)++;//指针后移
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));//创建新节点
    root->_data = a[*pi];//存储数据
    (*pi)++;//指针后移
    root->_left = CreateBinaryTree(a, pi);//递归创建左子树
    root->_right = CreateBinaryTree(a, pi);//递归创建右子树
    return root;
}

3.销毁二叉树

void DestroyBinaryTree(BTNode** root){
    if(*root == NULL){//如果当前节点是空节点
        return;
    }
    DestroyBinaryTree(&((*root)->_left));//递归销毁左子树
    DestroyBinaryTree(&((*root)->_right));//递归销毁右子树
    free(*root);//释放当前节点
    *root = NULL;
}

4.求二叉树的深度

int BinaryTreeDepth(BTNode* root){
    if(NULL==root){//如果当前节点是空节点
        return 0;
    }
    int Dep_1=BinaryTreeDepth(root->_left);//递归求左子树深度
    int Dep_2=BinaryTreeDepth(root->_right);//递归求右子树深度
    if(Dep_1>Dep_2){
        return Dep_1+1;
    }
    return Dep_2+1;
}