二叉树_链式存储

链式存储：

二叉链：数据域（data）、左子结点域（lchild）、右子节点域（rchild）
定义：

typedef struct linkBTreeNode
{
    ElemType data;
    struct linkBTreeNode *lchild;
    struct linkBTreeNode *rchild;
}LBTreeNode;

求指定节点的左子节点地址：

LBTreeNode *LeftChild(LBTreeNode *p)
{
    if(p == NULL) return NULL;
    return p->lchild;
}

求指定节点的右子节点地址：

LBTreeNode *RightChild(LBTreeNode *p)
{
    if(p == NULL) return NULL;
    return p->rchild;
}

二叉树的遍历：
定义：按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次；
用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心；

遍历规则：
1、先序遍历(DLR)：头 -> 左 -> 右
2、中序遍历(LDR)：左 -> 头 -> 右
3、后序遍历(LRD)：左 -> 右 -> 头
先中后都是对于根结点而言。

例子

二叉树遍历的递归实现：

访问方法：

void visit(LBTreeNode *t)
{
    printf("%c ", t->data);
}

先序遍历：

void PreOrder(LBTreeNode *t)//先访问根节点，再访问左右子树 
{
    if(t == NULL) return;
    visit(t);
    PreOrder(t->lchild);
    PreOrder(t->rchild);
}

中序遍历：

void MidOrder(LBTreeNode *t)//先左子树，再根节点，后右子树 
{
    if(t == NULL) return;
    MidOrder(t->lchild);
    visit(t);
    MidOrder(t->rchild);
}

后序遍历：

void LastOrder(LBTreeNode *t)//先左右子树，后根节点 
{
    if(t == NULL) return;
    LastOrder(t->lchild);
    LastOrder(t->rchild);
    visit(t);
}

插一嘴：递归实现的思路清晰，易于理解，但是执行效率很低。非递归实现效率高些。

---

二叉树遍历的非递归实现：
先序遍历：

void nPreOrder(LBTreeNode *t)
{
    SequenceStack s;
    LBTreeNode *p = t;
    StackInitialize(&s);
    while(StackIsNotEmpty(s) || p)
    {
        if(p)
        {
            visit(p);
            StackPush(&s, p);
            p = LeftChild(p);
        }
        else
        {           
            StackPop(&s, p);
            p = RightChild(p);          
        }
    }
}

中序遍历：

void nMidOrder(LBTreeNode *t)
{
    SequenceStack s;
    LBTreeNode *p = t;
    StackInitialize(&s);
    while(StackIsNotEmpty(s) || p)
    {
        if(p)
        {           
            StackPush(&s, p);
            p = LeftChild(p);
        }
        else
        {           
            StackPop(&s, p);
            visit(p);
            p = RightChild(p);          
        }
    }
}

后序遍历：好难-.-||略

利用“扩展先序遍历序列” 创建二叉树二叉链表：
1、若输入的字符是 '#'，则建立空树；
2、否则建立根结点，接着递归建立左子树，然后递归建立右子树。

//按先序序列建立二叉树的二叉链表
LBTreeNode *CreateBTree1(void)
{
    LBTreeNode *node;
    char ch;
    scanf("%c", &ch);
    if(ch == "#") node = NULL;
    else
    {
        node = (LBTreeNode *)malloc(sizeof(LBTreeNode));
        if(node == NULL)
        {
            printf("内存不足\n");
            return node;
        }
        node->data = ch;
        node->lchild = CreateBTree1();
        node->rchild = CreateBTree1();
    }
    return node;    
}
//创建完整的二叉树
LBTreeNode *CreateBTree2(void)
{
    LBTreeNode *pbtree;
    pbtree = (LBTreeNode *)malloc(sizeof(LBTreeNode));
    if(pbtree != NULL)
        pbtree = CreateBTree1();
    return pbtree;