链表和二叉树

单向链表

typedef struct list_node *list_pointer;
typedef struct list_node{
        int data;
        list_pointer link;
}

链表反转

list_pointer invert(list_pointer lead){
    list_pointer mid, tail;
    mid = NULL;
    while(lead){
        tail = mid;
        mid = lead;
        lead = lead->link;
        mid->link = tail;
    }
    return mid;
}      

二叉树定义

typedef struct node *tree_pointer;
typedef struct list_node{
    int data;
    tree_pointer left, right;
}

1、递归中序遍历

void inorder(tree_pointer ptr){
    if(ptr){
        inorder(ptr->left);
        printf("%d", ptr->data);
        inorder(ptr->right);
    }
}

2、迭代中序遍历

void iter_inorder(tree_pointer ptr){
    int top = -1;
    tree_pointer stack[MAX_STACK_SIZE];
    for(;;){
        for(; ptr; ptr = ptr->left){
            add(&top, ptr);
        }
        ptr = delete(&top);
        if(!ptr)
            break;
        printf("%d", ptr->data);
        ptr = ptr->right;
    }
}

3、二叉树层序遍历

void level_order(tree_pointer ptr){
    int front = rear = 0;
    tree_pointer queue[MAX_QUEUE_SIZE];
    if(!ptr)
        return;
    addQueue(front, &rear, ptr);
    for(;;){
        ptr = deleteQueue(&front, rear);
        if(ptr){
            if(ptr->left)
                addQueue(front, &rear, ptr->left);
            if(ptr->right)
                addQueue(front, &rear, ptr->right);            
        }
        else
            break; 
    }
}

4、判断一棵树是否为平衡树
思路一：按照前序遍历的路线判断。
1.判断以根结点的树是否为二叉平衡树。求出左右子树的高度，判断它们的高度差是否超过了1。
2.递归判断根的左子树是否为平衡二叉树
3.递归判断根的右子树是否为平衡二叉树
注意：空树也是平衡二叉树

//二叉树的高度(比较左右子树那个高，高的加1既为二叉树的高度)
int BinaryTreeHigh(tree_pointer ptr)
{
    if (root == NULL)
    {
        return 0;
    }
    int ret1 = BinaryTreeHigh(ptr->_left);
    int ret2 = BinaryTreeHigh(ptr->_right);
    //二叉树的高度为左子树和右子树中高的那个高度加1
    return ret1 > ret2 ? ret1 + 1 : ret2 + 1;
}
//判断树是否为平衡二叉树(1:是 0:不是)
int IsBlancedTree_R(tree_pointer ptr)
{
    //空树是平衡二叉树
    //平衡二叉树是指以当前结点为根的左右子树高度不得超过1
    if (ptr == NULL)
        return 1;
    //右子树深度
    int right = BinaryTreeHigh(ptr->_left);
    //左子树深度
    int left = BinaryTreeHigh(ptr->_right);
    int gap = right - left;
    //深度超过1不是
    if (gap > 1 || gap < -1)
        return 0;
    //递归判断子树
    return IsBlancedTree_R(ptr->_left) && IsBlancedTree_R(ptr->_right);
}

思路二：按照后序遍历的路线判断
1.首先，判断它的左子树是否为平衡二叉树
2.然后在判断它的右子树是否为平衡二叉树
3.判断它们是否为平衡二叉树的同时，记录它们的左右子树的深度
4.最后在判断以这个结点为根的树是否为平衡二叉树

/判断树是否为平衡二叉树(1:是 0:不是)
//优化版本(不用遍历重复的结点)
int IsBlancedTree_op(tree_pointer ptr, int *pdepth)
{
    if (ptr == NULL)
    {
        *pdepth = 0;
        return 1;
    }
    //按照后序遍历去判断,先判断左右子树，然后记录以当前结点为根树的深度
    int left, right;
    if (IsBlancedTree_op(ptr->_left, &left) && IsBlancedTree_op(ptr->_right, &right))
    {
        int gap = right - left;
        if (gap <= 1 && gap >= -1)
        {
            *pdepth = left>right ? left + 1 : right + 1;
            return 1;
        }
    }
    return 0;
}

5、二叉树最小公共父节点

tree_pointer  lowestCommonAncestor(tree_pointer ptr, tree_pointer p, tree_pointer q){
    if(!ptr || ptr == p|| ptr == q)
        return ptr;
    TreeNode left = lowestCommonAncestor(ptr->left, p, q);
    TreeNode right = lowestCommonAncestor(ptr->right, p, q);
    if(left&&right)
        return root;
    if(!left)
        return right;
    if(!right)
        return left;
}

6、判断二叉树是否对称

bool balance_tree(tree_pointer ptr){
    flag=0;
    while(p!=NULL)
    {
        if(p->left == NULL && p->right)
        {
            return(0);
        }
        if(p->rchild==NULL){
            flag = 1;
        }
        if(flag == 1 && p->left != NULL || p->right != NULL){
            return 0;
        }
    }
    return 1;
}

7、将二叉树转为排序双向链表
要点：

1.直接改变树的结构

2.排序二叉树在中序遍历的时候是有序的

3.双向链表，需要前后两个指针（可以将Tree的节点作为链表节点）

代码实现：中序的递归实现

void ToList(Tree* pTree ,Tree** pHead,Tree** pEnd )
{
    if(pTree == NULL ) return;
    ToList(pTree->pleft,pHead,pEnd);
    if(*pHead == NULL)
    {
        *pHead = pTree;
        *pEnd = pTree;
    }
    else
    {
        (*pEnd)->pright = pTree;
        pTree->pleft = *pEnd;
    }
    (*pEnd) = pTree;
    ToList(pTree->pright,pHead,pEnd);
}