树形结构的其他运算

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

// 7.8 习题7
typedef char dataType;
typedef struct treeNode
{
    dataType data; // 数据域
    struct treeNode *lChild,*rChild; // 左、右孩子指针域
}node,*binaryTree;

// 顺序栈
#define MAX_SIZE 100
typedef struct stack
{
    node *data[MAX_SIZE]; // 栈中存放的是二叉树结点指针
    int top; // 栈顶指针
}seqStack;

// 1.初始化栈
void init(seqStack *stack)
{
    stack->top = 0;
}

// 2. 判断栈是否为空
int empty(seqStack stack)
{
    return stack.top == 0;
}

// 3. 元素入栈
void push(seqStack *stack, node* n)
{
    if(stack->top == MAX_SIZE-1)
    {
        printf("栈已满，无法入栈！\n");
        exit(1);
    }
    stack->data[stack->top++] = n;
}

// 4. 读取栈顶元素
node *get(seqStack stack)
{
    return stack.data[stack.top-1];
}

// 5. 元素出栈
node* pop(seqStack *stack)
{
    if(empty(*stack))
    {
        printf("栈已空，无法出栈！\n");
        exit(1);
    }
    return stack->data[--stack->top];
}

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

// 7.1.13.1 递归方法求二叉树的叶子结点个数
int numLeaf(binaryTree tree)
{
    if(!tree) return 0; // 空树
    if(!tree->lChild && !tree->rChild) // 左右孩子都不存在
        return 1;
    return numLeaf(tree->lChild) + numLeaf(tree->rChild);
}

// 7.1.13.2 非递归方法求二叉树的叶子结点个数
int numLeaf1(binaryTree tree)
{
    int num = 0;
    seqStack stack;
    stack.top = 0; // 初始化栈
    while (tree || !empty(stack)) // 树或栈非空
    {
        if(tree)
        {
            if(!tree->lChild && !tree->rChild)
                num++;
            push(&stack,tree); // 进栈
            tree = tree->lChild; // 一路向左
        } else
        {
            tree = pop(&stack); // 出栈向右子树
            tree = tree->rChild;
        }
    }
    return num;
}

// 7.1.14 求给定二叉树中序遍历序列的最后一个结点
node * inOrderLast(binaryTree tree)
{
    while (tree && tree->rChild)
        tree = tree->rChild;
    return tree;
}

// 7.1.15 返回二叉树任意两结点p、q的共同祖先
node *seekAncestor(binaryTree t, node *p, node *q)
{
    seqStack s, s1; // 声明顺序栈
    init(&s), init(&s1); // 初始化栈
    node *r = NULL; // 记录最近访问的结点
    while (t || !empty(s)) // 树或栈非空
    {
        if (t) // 一路向左直到左孩子为空
        {
            push(&s,t); // 沿着根的左孩子依次入栈
            t = t->lChild;
        } else
        {
            t = get(s); // 读取栈顶元素
            if(t->rChild && t->rChild != r) // 右孩子存在且未访问
                t = t->rChild; // 转向右孩子
            else
            {
                pop(&s); // 出栈
                if(t == p || t == q)
                {
                    if(empty(s1)) // 栈s复制给栈s1
                        for (int i = s.top-1; i >= 0; i--)
                            push(&s1,s.data[i]);
                    else break; // p、q的祖先都已找到，退出循环
                }
                r = t; // 记录最近访问的结点(关键步骤)
                t = NULL; // 结点访问后重置为空(关键步骤)
            }
        }
    }
    while (!empty(s)) // 寻找共同祖先
    {
        t = pop(&s);
        for (int j = s1.top-1; j >= 0; j--)
            if(t == s1.data[j])
                return t;
    }
    return NULL;
}

int main()
{
    binaryTree tree;
    printf("请输入结点，创建一颗二叉树，#表示空结点:\n");
    tree = createTree(); // ABD#E##FG###C##
    printf("该二叉树叶子结点有%d个\n",numLeaf(tree));
    printf("该二叉树叶子结点有%d个\n", numLeaf1(tree));
    node *n = inOrderLast(tree);
    if(n) printf("该二叉树中序遍历序列的最后一个结点是%c",n->data);
    else printf("该二叉树为空！");
    return 0;
}