二叉树的各种操作函数

#include "source.h"

//满与空的问题，计算个数时（判断rear和front的大小1.    2.   ）空一个
void InitQueue(Queue u)
{
    u.front = 0;
    u.rear = 0;
}
int sizeQue(Queue u)
{   
    int size;
    if (u.front > u.rear)
        size = max - (u.front - u.rear);
    else
        size = u.rear - u.front;
    return size;

}
void swap(int &a, int &b)
{
    int c = a;
    a = b;
    b = c;
}
void Perm(int arr[], int k, int m)
{
    if (k == m)
    {
        for (int i = 0;i <= m;i++)
            printf("%d ", arr[i]);
        printf("\n");
    }   
    else
    {
        for (int i = k;i<=m;i++)
        {
            swap(arr[k], arr[i]);
            Perm(arr, k+1, m);
            //交换之后恢复原来的位置
            swap(arr[k], arr[i]);
        }
    }
}


void Freenode(BtNode *p)
{
    free(p);
}
/

void PreOrder(BtNode *ptr)
{
    if (ptr != NULL)
    {
        printf("%c ", ptr->data);
        PreOrder(ptr->leftchild);
        PreOrder(ptr->rightchild);
    }
}
void InOrder(BtNode *ptr)
{
    if (ptr != NULL)
    {
        InOrder(ptr->leftchild);
        printf("%c ", ptr->data);
        InOrder(ptr->rightchild);
    }
}
void PastOrder(BtNode *ptr)
{
    if (ptr != NULL)
    {
        PastOrder(ptr->leftchild);
        PastOrder(ptr->rightchild);
        printf("%c ", ptr->data);
    }
}

BtNode * CreateTree1()
{
    BtNode *s = NULL;
    char item;
    scanf_s("%c", &item);
    if (item != '#')
    {
        s = Buynode();
        s->data = item;
        s->leftchild = CreateTree1();
        s->rightchild = CreateTree1();
    }
    return s;
}
BtNode * CreateTree2(char *&str)
{
    BtNode *s = NULL;

    if (*str != '#')
    {
        s = Buynode();
        s->data = *str;
        s->leftchild = CreateTree2(++str);
        s->rightchild = CreateTree2(++str);
    }
    return s;
}
BtNode * CreateTree3(char ** const pstr)
{
    BtNode *s = NULL;
    if (**pstr != '#')
    {
        s = Buynode();
        s->data = **pstr;
        s->leftchild = CreateTree2(++(*pstr));
        s->rightchild = CreateTree2(++(*pstr));
    }
    return s;
}
//通过前序遍历和中序遍历得到原序列
//char *ps = "ABCDEFGH";
//char *is = "CBEDFAGH";

//寻找在中序中的位置
int FindPos(char *is,char ch,int n)
{
    for (int i = 0;i<n+1;i++) {                     //找到返回下标序号
        if (ch == is[i]) {
            return i;
            break;
        }
    }
    return -1;
}

char * substr(char *dst, char src[], int start, int len)
{
    int i;
    int pos = len - start+1;
    dst = new char[pos+1];
    for (i = 0;i<pos;i++)
    {
        dst[i] = src[start + i];    //从第start+i个元素开始向数组内赋值  
    }
    dst[i] = '\0';
    return dst;
}
BtNode * CreatePI(char *ps, char *is)
{
    BtNode *bt = NULL;
    if (strlen(ps) <= 0)
    {
        return bt;
    }
     int n = strlen(ps)-1;      //最后一个元素的下标

    char *lf_child_in = 0;
    char *rg_child_in = 0 ;
    char *lf_child_ps = 0;
    char *rg_child_ps = 0;
    //char *src_pr;

    bt = (BtNode *)malloc(sizeof(BtNode));
    bt->data = ps[0];
    int pos = FindPos(is, ps[0], n);//根在中序序列中的位置  

    lf_child_in = substr(lf_child_in,is, 0,pos-1);//左孩子的中序序列  
    rg_child_in = substr(rg_child_in, is, pos + 1, n);

    int lf_child_len = strlen(lf_child_in); //左孩子长度
    int rg_child_len = strlen(rg_child_in);

    lf_child_ps = substr(lf_child_ps, ps,1 , lf_child_len);     //左孩子的前序序列
    rg_child_ps = substr(rg_child_ps, ps, 1 + lf_child_len, n);
    if (bt!=NULL)
    {
        bt->leftchild = CreatePI(lf_child_ps, lf_child_in);
        bt->rightchild = CreatePI(rg_child_ps, rg_child_in);
    }
    return bt;
}
int FindPos1(char *is,char ch)
{
    int count = 0;
    while (is[count] != ch)
    {
        count++;
    }
    return count;
}
//利用n
int IsIndex(ElemType *is, ElemType x, int n) {
    for (int i = 0;i<n;i++) {                       //找到返回下标序号
        if (x == is[i]) {
            return i;
            break;
        }
    }
    return -1;                  //未找到则返回-1  
}


BtNode * CreatBin(char *ps, char *is, int n)        //n为此次要建树的元素个数
{
    BtNode *temp = NULL;            //如果直接将BtNode *temp=(BtNode *)malloc(sizeof(BtNode));
                                    //在遍历的情况下因为找不到NULL的值而打印出错，没有NULL的话
                                    //是一个随机值，没发打印
    if (n > 0)
    {
        temp = (BtNode *)malloc(sizeof(BtNode));
        temp->data = ps[0];
        int pos = IsIndex(is, ps[0], n);
        temp->leftchild = CreatBin(ps+1, is,  pos);
        temp->rightchild = CreatBin(ps+pos+1, is+pos+1, n-pos-1);
    }
    return temp;
}
BtNode *CreatPI1(char *ps,char *is)
{
    if (ps == NULL || is == NULL)
        return NULL;
    else
        return CreatBin(ps,is,strlen(ps));
}

//通过中序和后续遍历得到前序遍历
//char *ls = "CEFDBHGA";
//char *is = "CBEDFAGH";
BtNode *CrLI(char *ls, char *is ,int n)
{
    BtNode *temp = NULL;
    if (n > 0)
    {
        temp = (BtNode *)malloc(sizeof(BtNode));
        temp->data = ls[n-1];
        int pos = IsIndex(is, ls[n-1], n);
        if (pos == -1)
            exit(0);

        temp->leftchild = CrLI(ls, is, pos);
        temp->rightchild = CrLI(ls + pos, is + pos + 1, n - pos - 1);
    }
    return temp;
}
BtNode * CreateLI(char *ls, char *is)
{
    if (ls == NULL || is == NULL)
        return NULL;
    else
        return CrLI(ls, is, strlen(ls));
}

BtNode * FindValue(BtNode *ptr, ElemType x)
{
    if (ptr == NULL || ptr->data == x)
        return ptr;
    else 
    {
        BtNode *temp;
        temp = FindValue(ptr->leftchild, x);
        if (temp == NULL)
        {
            ptr = FindValue(ptr->rightchild,x);
        }
    }
    return ptr;
}
BtNode * FindParet(BtNode *ptr, BtNode *child)  //外加一个处理函数
{
    if (ptr->leftchild == child || ptr->rightchild == child)
        return ptr;
    BtNode *p = FindParet(ptr->leftchild, child);
    if(p==NULL)
        p = FindParet(ptr->rightchild, child);
    return p;
    //return NULL;
}

//最近双亲结点
/*
    网上有算法：得到前序和后续序列，对先序序列从两结点前从后向前找，对后序序列采取从两结点之后
    从前向后找，找到的第一个公共结点便是双亲结点

    我的思路：
        计算两个结点的高度，最小的高度的父结点便是其最近双亲结点
*/

int Depth_to_node(BtNode *ptr,ElemType e)
{
    if (ptr == NULL)
        return 0;
    else if (ptr->data == e)
        return 0;
    else
    {
            return Depth_to_node(ptr->leftchild, e) + 1;
            return Depth_to_node(ptr->rightchild, e) + 1;
    }
    return 0;
}
//from 网上
BtNode * FindNearParent(BtNode *ptr, BtNode *child1, BtNode*child2)
{
        if (ptr == NULL) //说明是空树，不用查找了，也就找不到对应节点，则返回NULL  
            return  NULL;

        if (ptr == child1 || ptr == child2)//说明在当前子树的根节点上找到两个节点之一  
            return ptr;

        BtNode   *pLeft = FindNearParent(ptr->leftchild, child1, child2);  //左子树中的查找两个节点并返回查找结果  
        BtNode   *pRight = FindNearParent(ptr->rightchild, child1, child2);//右子树中查找两个节点并返回查找结果  

        if (pLeft == NULL)//如果在左子树中没有找到，则断定两个节点都在右子树中，可以返回右子树中查询结果；否则，需要结合左右子树查询结果共同断定  
            return pRight;
        if (pRight == NULL)//如果在右子树中没有找到，则断定两个节点都在左子树中，可以返回左子树中查询结果；否则，需要结合左右子树查询结果共同断定  
            return pLeft;

        return ptr;//如果在左右子树中都找两个节点之一，则pRoot就是最低公共祖先节点，返回即可。  
}
int SizeLeaf(BtNode *ptr)
{
    if (ptr == NULL)
        return NULL;
    if (ptr && ptr->leftchild == NULL &&ptr->rightchild == NULL)
        return 1;
    else 
    {
        return SizeLeaf(ptr->leftchild)+SizeLeaf(ptr->rightchild);
    }
}
int Size(BtNode *ptr)
{
    //中序遍历或者后序等也都可以
    if (ptr == NULL)
        return NULL;
    else
    {
        return Size(ptr->leftchild) + Size(ptr->rightchild)+1;
    }

}
int Depth(BtNode *ptr)
{
    int size = Size(ptr);
    int depth = 0;
    while (1)
    {
        if ((size = (size / 2)) != 0)
        {
            depth++;
        }
        else break;
    }
    return depth+1;
}
int Depth1(BtNode *ptr)
{
    if (ptr == NULL)
        return 0;
    else
    return Depth1(ptr->leftchild) > Depth1(ptr->rightchild)? Depth1(ptr->leftchild)+1:Depth1(ptr->rightchild)+1;
}

void LevelOrder(BtNode *ptr)
{
    queue<BtNode*> que;
    que.push(ptr);
    while (!que.empty())
    {
        BtNode * temp = que.front();
        if(temp->leftchild != NULL)
            que.push(temp->leftchild);
        if(temp->rightchild != NULL)
            que.push(temp->rightchild);
        que.pop();
        printf("%c ", temp->data);
    }
}

int Level_K_prin(BtNode *ptr,int k,int count_tt)  //count_tt代表从那一层开始，0或1
{
//  static int count_tt = 1;
    if (count_tt == k)
    {
        printf("%c ", ptr->data);
        return k;
    }
     if (ptr->leftchild != NULL)
    {
        //count_tt += 1;
        Level_K_prin(ptr->leftchild, k,count_tt+1 );
    }
    if(ptr->rightchild != NULL)
    {
        //count_tt += 1;
        Level_K_prin(ptr->rightchild, k,count_tt+1);
    }
}
//判断两颗二叉树是否相等
bool Equal(BtNode *pa, BtNode *pb)
{
    if ( pa == NULL && pb!=NULL || pa != NULL && pb == NULL || pa->data != pb->data)
        return false;
    if (pa->leftchild != NULL && pb->leftchild != NULL)
    {
        bool temp = Equal(pa->leftchild, pb->leftchild);
        if (temp)
            ;
        else
            return temp;
    }
    if (pa->rightchild != NULL && pb->rightchild != NULL)
    {
        bool temp = Equal(pa->rightchild, pb->rightchild);
        if (temp)
            ;
        else
            return temp;
    }
    if (pa->rightchild == NULL && pb->rightchild == NULL || pa->leftchild == NULL && pb->leftchild == NULL)
        return true;
    if (pa->rightchild == NULL && pb->rightchild != NULL || pa->rightchild != NULL && pb->rightchild == NULL ||
        pa->leftchild != NULL && pb->leftchild == NULL || pa->leftchild == NULL && pb->leftchild != NULL)
        return false;
    //return false;
}

void NicePerOrder(BtNode *ptr)
{
    stack<BtNode*> stac;
    stac.push(ptr);
    BtNode *Node;
    while (!stac.empty())
    {
        Node = stac.top();
        printf("%c ", Node->data);
        stac.pop();
        if (Node->rightchild != NULL)
            stac.push(Node->rightchild);
        if (Node->leftchild != NULL)
        {
            stac.push(Node->leftchild);
        }
    }
}
void NiceInOrder(BtNode *ptr)
{
    stack<BtNode*> stac;
    while (ptr ||!stac.empty())
    {
        while (ptr)
        {
            stac.push(ptr);
            ptr = ptr->leftchild;
        }
        ptr = stac.top();
        stac.pop();
        printf("%c ", ptr->data);
        ptr = ptr->rightchild;
    }
}
void NicePastOrder(BtNode *ptr)
{
    stack<BtNode*> s;
    BtNode *cur;                      //当前结点 
    BtNode *pre = NULL;                 //前一次访问的结点     
    s.push(ptr);
    while (!s.empty())
    {
        cur = s.top();
        if ((cur->leftchild == NULL&&cur->rightchild == NULL) ||
               (pre != NULL && (pre == cur->leftchild || pre == cur->rightchild)))
        {
            cout << cur->data << " ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
            s.pop();
            pre = cur;
        }
          else
        {
            if (cur->rightchild != NULL)
                s.push(cur->rightchild);
            if (cur->leftchild != NULL)
                s.push(cur->leftchild);
          }
      }
}
//是不是完全二叉树,设置一个全局的leftFlag
bool Is_Comp_BinaryTree(BtNode *root)
{
    queue<BtNode*> q;
    BtNode *ptr;
    // 进行广度优先遍历（层次遍历），并把NULL节点也放入队列  
    q.push(root);
    while ((ptr = q.front()) != NULL)
    {
        q.pop();
        q.push(ptr->leftchild);
        q.push(ptr->rightchild);
    }

    // 判断是否还有未被访问到的节点  
    while (!q.empty())
    {
        ptr = q.front();
        q.pop();

        // 有未访问到的的非NULL节点，则树存在空洞，为非完全二叉树  
        if (NULL != ptr)
        {
            return false;
        }
    }
    return true;
}

bool Is_Full_BinaryTree(BtNode *ptr);
bool Is_Balance_BinaryTree(BtNode *ptr);



//线索化二叉树 
//ThreadBineary temp;
void  InOrderThread(ThreadBineary ptr,ThreadBineary &temp)
{
    if (ptr != NULL)
    {
        InOrderThread(ptr->lfchild,temp);
        if (ptr->lfchild == NULL)
        {
            ptr->ltag = link;
            ptr->lfchild = temp;
            temp = ptr;
        }
        if (temp->richild ==NULL)
        {
            temp->richild = ptr;
            //ptr = temp->richild;
            temp->rtag = thread;
            temp = ptr;
        }
        InOrderThread(ptr->richild,temp);
    }
}

void THrInOrder(ThreadBineary ptr)
{
    //ThreadBineary p =ptr;
    //while (p != NULL)
    //{
    //  while (p->lfchild != NULL)
    //  {
    //      p = p->lfchild;
    //  }
    //  printf("%c", p->data);
    //  
    //  if(p->richild !=NULL)
    //      p = p->richild;
    //}
}
//求两个叶子节点的最大路径
int MaxPathBineary(BtNode *ptr)
{
    return 0;
}
void main()
{
    char *str = "ABC##DE##F##G#H##";
    char *ps = "ABCDEFGH";
    char *is = "CBEDFAGH";
    char *ls = "CEFDBHGA";

    char *ps1 = "ABCDEFGH";
    char *is1 = "CBEDFAGH";

    BinaryTree root = NULL;
    BinaryTree root1 = NULL;
    //root = CreateTree1();

    //root = CreatPI1(ps, is);
    root = CreateLI(ls, is);
    //root = CreateTree1();
    //root = CreateTree2(str);
    //root = CreateTree3(&str);
    root1 = CreatePI(ps1, is1);

    printf("递归的前序遍历是：\n");
    PreOrder(root);
    printf("\n");
    printf("递归的中序遍历：\n");
    InOrder(root);
    printf("\n");
    printf("递归的后序遍历：\n");
    PastOrder(root);
    printf("\n");

    
    //root = CreatePI(ps, is);

    BtNode *tt = FindValue(root,'G');
    if (tt != NULL)
        printf("找到的值是：%c \n", tt->data);
    else
        printf("没找到！");
    int count = Size(root);
    printf("count的值是：%d\n", count);
    count = SizeLeaf(root);
    printf("count2的值是：%d\n", count);
    count = Depth1(root);
    printf("depth is ：%d\n", count);
    count = Depth_to_node(root,'H');
    printf("到%c的值是：%d\n", 'E',count);
    printf("---------------------------------------------------------");
    Level_K_prin(root, 3,1);
    ///
    bool result = Equal(root, root1);
    printf("两个二叉树相等吗？ %d\n", result);
    printf("root1 的层次遍历顺序：\n");
    LevelOrder(root);
    //printf("\n");
    printf("非递归前序遍历的顺序：\n");
    NicePerOrder(root1);
    //printf("\n");
    printf("非递归中序遍历的顺序：\n");
    NiceInOrder(root);
    printf("非递归的后续遍历顺序是：\n");
    NicePastOrder(root);
    printf("\n");

    printf("是不是完全二叉树：\n");
    result = Is_Comp_BinaryTree(root);
    printf("%d", result);
}