二叉树的使用

• 二叉树结构

typedef struct BTNode{
    int data;
    struct BTNode *lChild;\\左子树
    struct BTNode *rChild;\\右子树
}BiTNode;

• 先序创建二叉树

int CreateBiTree(BiTNode **T)
{
    int ch;
    scanf("%d",&ch);
    if (ch == -1)
    {
        *T = NULL;
        return 0;
    }
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        if (T == NULL)
        {
            printf("failed\n");
            return 0;
        }
        else
        {
            (*T)->data = ch;
            printf("输入%d的左子节点：",ch);
            CreateBiTree(&((*T)->lChild));
            printf("输入%d的右子节点：",ch);
            CreateBiTree((&(*T)->rChild));
        }
    }
    
    return 1;
}

---

DFS

• 先序遍历二叉树

void PreOrderBiTree(BiTNode *T)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        printf("%d ",T->data);
        PreOrderBiTree(T->lChild);
        PreOrderBiTree(T->rChild);
    }
}

• 中序遍历二叉树

void MiddleOrderBiTree(BiTNode *T)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        MiddleOrderBiTree(T->lChild);
        printf("%d ",T->data);
        MiddleOrderBiTree(T->rChild);
    }
}

• 后序遍历二叉树

void PostOrderBiTree(BiTNode *T)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        PostOrderBiTree(T->lChild);
        PostOrderBiTree(T->rChild);
        printf("%d ",T->data);
    }
}

---

BFS

• 层次遍历---遍历二叉树指定层

/*
思路：遍历二叉树的第k层，相当于遍历二叉树根节点的左右子树的第k-1层。这样一直遍历下去，直到k=0时，输出节点即可。
*/
int PrintNodeAtLevel(BiTNode *root, int level)
{
    if(!root || level < 0)
        return 0;
    else if(level == 0)
    {
        printf("%d ",root->data);
        return 1;
    }
    else
        return PrintNodeAtLevel(root->lChild, level - 1) + PrintNodeAtLevel(root->rChild, level - 1);
}

• 层次遍历二叉树（需要二叉树深度）

//层次遍历----根据求得的层次，遍历每一层
void TranverseTree1(BiTNode *root)
{
    for(int i = 0; i < TreeDeep(root); ++i)
    {
        PrintNodeAtLevel(root, i);
        printf("\n");
    }
}

• 层次遍历二叉树（不需要深度）

//层次遍历----无需求得层次，根据遍历每层的返回信息确定遍历
void TranverseTree2(BiTNode *root)
{
    for(int i = 0; ; ++i)
    {
        if(!PrintNodeAtLevel(root, i))
            break;
        printf("\n");
    }
}

• 具体用的BFS的思路

思路：二叉树的层次遍历思路，借助队列来实现。相当于广度优先搜索，使用队列（深度优先搜索的话，使用栈）。

1. 若根节点为空，直接返回；
2. 若根节点非空，则将根节点入队，然后，判断队列是否为空;若不为空，则将队首节点出队，访问，并判断其左右子节点是否为空，若不为空，则压入队列。
3. 因最终输出是从最后一层到第一层的输出，所以，直接调用reverse()函数，将整个容器翻转就可以了。

---

• 二叉树深度

int TreeDeep(BiTNode *T)
{
    int deep = 0;
    if (T != NULL)
    {
        int leftdeep = TreeDeep(T->lChild);
        int rightdeep = TreeDeep(T->rChild);
        deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;
    }
    
    return deep;
}

• 叶子节点个数

int LeafCount(BiTNode *T)
{
    static int count;
    if (T != NULL)
    {
        if (T->lChild == NULL && T->rChild == NULL)
        {
            count++;
        }
        
        LeafCount(T->lChild);
        LeafCount(T->rChild);
    }
    
    return count;
}

• 二叉树的翻转

//二叉树翻转
/*
算法原理:

在数据结构中，对于树这种结构，我们经常采用的策略是使用递归的方式，在这里，我们也使用递归来解决这个问题。

递归算法步骤：

    1、对二叉树的左子树进行翻转

    2、对二叉树的右子树进行翻转

    3、将左右子树的根节点进行交换（不用考虑原二叉树的根节点，因为原二叉树的根节点在翻转前后没有改变）
*/

BiTNode* InvertBinaryTree(BiTNode *tree) {
    if (NULL == tree) {
        return NULL;
    }

    tree->lChild = InvertBinaryTree(tree->lChild);
    tree->rChild = InvertBinaryTree(tree->rChild);
    
    BiTNode *tempTree = tree->lChild;
    tree->lChild = tree->rChild;
    tree->rChild = tempTree;
    return tree;
}

• 根据先序遍历序列和中序遍历序列，重建二叉树

//根据先序遍历序列和中序遍历序列重建二叉树
BiTree Construct(int *ptree,int *itree,int length)
{
    if(ptree==NULL || itree==NULL || length<=0)
        return NULL;
    return ConstructCode(ptree,ptree+length-1,itree,itree+length-1);
}

/****************************************************************
 *args:
 *   ptree_start:先序遍历开始位置指针
 *   ptree_end:先序遍历结束位置指针
 *   itree_start:中序遍历开始位置指针
 *   itree_end:中序遍历结束位置指针
 ****************************************************************/
BiTree ConstructCode(int *ptree_start,int *ptree_end,int *itree_start,int *itree_end)
{
    BiTree root_node;
    root_node=(BiTree)malloc(sizeof(BiTNode));
    root_node->data=ptree_start[0];                          /*根节点*/
    root_node->lChild=NULL;
    root_node->rChild=NULL;
    
    if(ptree_start==ptree_end)                              /*该节点是子树最后一个节点*/
    {
        if(itree_start==itree_end && *ptree_start==*ptree_end)
        {
            return root_node;
        }else
        {
            printf("ConstructCode is error!\n");
            exit(1);
        }
    }
    int *tmp_itree=itree_start;
    int left_length=0;
    while((*itree_start!=root_node->data) && (itree_start<itree_end))/*在中序遍历中寻找跟节点的指针*/
    {
        itree_start++;
    }
    left_length=itree_start-tmp_itree;                      /*根节点在中序遍历中的位置，用于求在先序遍历中右子树的开始位置*/
    if(left_length>0)                                        /*左子树递归*/
    {
        root_node->lChild=ConstructCode(ptree_start+1,ptree_start+left_length,tmp_itree,itree_start-1);
    }
    if(left_length<(ptree_end-ptree_start))                  /*右子树递归，pend-pstart>left_length说明遍历序列比左子树长，右子树有节点*/
    {
        root_node->rChild=ConstructCode(ptree_start+left_length+1,ptree_end,itree_start+1,itree_end);
    }
    return root_node;
}

• 获取二叉树中序遍历的下一个节点

非标准答案，改中序遍历，添加标记打印。

二叉树结构

//中序遍历 找出节点的下一个节点
void MiddleOrderBiTreeFindNextData(BiTNode *T,int s,int flag)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        MiddleOrderBiTreeFindNextData(T->lChild,s,flag);
        if (flag == 1) {
            printf("%d ",T->data);
            return;
        }
        if (T->data == s) {
            flag = 1;
        }
        MiddleOrderBiTreeFindNextData(T->rChild,s,flag);
    }
}

---

and so on...