二叉树其他运算的实现

#include <stdio.h>
#include <stdlib.h>

// 7.5 二叉树其他运算的实现
typedef char dataType;
typedef struct node
{
    dataType data; // 数据域
    struct node *lChild,*rChild; // 左、右孩子指针域
}treeNode,*binaryTree;

// 1. 按照前序遍历的顺序创建一个二叉树
binaryTree createTree()
{
    binaryTree tree;
    char c;
    if((c = getchar()) == '#')
        tree = NULL;
    else
    {
        tree = (treeNode *) malloc(sizeof(treeNode));
        tree->data = c;
        tree->lChild = createTree();
        tree->rChild = createTree();
    }
    return tree;
}

// 2.二叉树的查找
treeNode *locate(binaryTree tree, dataType x)
{
    treeNode *p;
    if(!tree) return NULL; // 如果是空树
    if(tree->data == x) return tree; // 根结点符合条件
    p = locate(tree->lChild,x); // 寻找左子树
    if(p) return p;
    return locate(tree->rChild,x); // 寻找右子树
}

// 3. 统计二叉树的结点个数
int numOfNode(binaryTree tree)
{
    if(!tree) return 0;
    return numOfNode(tree->lChild) + numOfNode(tree->rChild) +1;
}

// 4. 判断两棵二叉树是否相等
int isEqual(binaryTree t1, binaryTree t2)
{
    int t = 0;
    if(!t1 && !t2) t=1;
    else
    {
        if(t1->data == t2->data)
        {
            if(isEqual(t1->lChild,t2->lChild))
            {
                t = isEqual(t1->rChild,t2->rChild);
            }
        }
    }
    return t;
}

// 5. 递归方式求二叉树的高度或深度
int depth(binaryTree tree)
{
    int lh,rh;
    if(!tree) return 0;
    lh = depth(tree->lChild);
    rh = depth(tree->rChild);
    return lh>rh ? lh+1 :rh+1;
}

int main()
{
    binaryTree tree; // 声明二叉树
    printf("请输入结点，创建一颗二叉树，#表示空结点:\n");
    tree = createTree(); // ABD#E##FG###C##
    treeNode *node;
    char x = 'A';
    node = locate(tree,x);
    if(node)
        printf("结点%c存在\n",node->data);
    int num = numOfNode(tree);
    printf("该二叉树共有%d个结点\n",num);
    int h = depth(tree);
    printf("该二叉树高度或深度是%d",h);
    return 0;
}