1. 给出二叉树自下而上，自右到左的层次遍历算法，算法思想：在一般的层次遍历的同时出队，并将结点放入栈中，最后从栈顶开始出栈即是逆序的层次遍历

    void ReverseLevel(BiTree T) {
        stack<BiTree> s;
        queue<BiTree> q;
        BiTree p;
        if (T) {
            q.push(T);      //将根结点入队
            while (!q.empty()) {    //当队列不为空时
                p = q.front();      //结点出队
                q.pop();            //从删除该结点
                s.push(p);          //把结点放入栈
                if (p->lchild != nullptr)
                    q.push(p);
                if (p->rchild != nullptr)
                    q.push(p);
            }
            while (!s.empty()) {
                p = s.top();
                s.pop();
                visit(p);
            }
        }
    }

  2. 假设二叉树采用二叉链表存储结构，设计非递归算法求二叉树的高度，算法思想：采用层次遍历，用level记录层数，设置变量last指向当前层最右结点，当遍历到last时，层数加1

    int BiTdepth1(BiTree T) {
        if (!T)
            return 0;   //树空返回0
        int front = -1, rear = -1;
        //用于指向当前层的最后一个节点，level记录层数
        int last = 0, level = 0;
        BiTree Q[MaxSize];  //建立二叉树结点指针类型的队列
        Q[++rear] = T;  //将根结点入队
        BiTree p;
        while (front < rear) {  //队不空
            p = Q[++front];     //取出正在访问的结点
            if (p->lchild)
                Q[++rear] = p->lchild;
            if (p->rchild)
                Q[++rear] = p->rchild;
            if (front == last) {    //到一层的最后一个结点时
                level++;        //层数加一
                last = rear;    //把last下一层的最后一个结点
            }
        }
        return level;
    }

    //递归法解决此题
    int BiTdepth2(BiTree T) {
        if (!T)
            return 0;
        int ldep = BiTdepth2(T->lchild);
        int rdep = BiTdepth2(T->rchild);
        if (ldep > rdep)
            return ldep + 1;
        else
            return rdep + 1;
    }

  3. 设一棵二叉树中各结点的值互不相同，其先序遍历和后序遍历序列分别存放于A和B数组，编写算法建立二叉链表

    BiTree AB_Create(ElemType A[], ElemType B[], int l1, int h1, int l2, int h2) {
        //l1, h1, l2, h2分别为先序和中序的第一个和最后一个结点
        //假设初始调用时：l1=l2=1, h1=h2=n
        BiTree root = (BiTree) malloc(sizeof(BiTree));      //建立根结点
        root->data = A[l1];    //根结点
        int i;
        for (i = l2; B[i] != root->data; i++);          //在中序序列中找到根结点的划分
        int Llen = i - l2;      //左子树长度
        int Rlen = h2 - i;      //右子树长度
        if (Llen)       //递归建立左子树
            root->lchild = AB_Create(A, B, l1 + 1, l1 + Llen, l2, l2 + Llen - 1);
        else
            root->lchild = nullptr;
        if (Rlen)       //递归建立右子树
            root->rchild = AB_Create(A, B, h1 - Rlen + 1, h1, h2 - Rlen + 1, h2);
        else
            root->rchild = nullptr;
        return root;
    }

  4. 二叉树链式存储，判断是否是完全二叉树，算法思想：层次遍历，若出现空节点后还有非空节点，则不是完全二叉树

    bool IsComplete(BiTree T) {
        queue<BiTree> q;
        if (!T)
            return 1;       //空树为满二叉树
        BiTree p;
        q.push(T);
        while (!q.empty()) {
            p = q.front();
            q.pop();
            if (p) {
                q.push(p->lchild);
                q.push(p->rchild);
            } else {
                //这一步跳过空节点，若之后还出现非空节点，则不是
                while (!q.empty()) {
                    p = q.front();
                    q.pop();
                    if (p)
                        return 0;
                }
            }
        }
        return 1;
    }

  5. 计算一棵链式二叉树所有双分支结点个数

    int DsonsNode(BiTree T) {
        if (T == nullptr)
            return 0;
        else if (T->lchild != nullptr && T->rchild != nullptr)
            //若找到了含有两个孩子结点的结点，则+1，并继续往下找
            return DsonsNode(T->lchild) + DsonsNode(T->rchild) + 1;
        else
            //否则继续往下找，但是此时不计个数
            return DsonsNode(T->lchild) + DsonsNode(T->rchild);
    }

  6. 把树B中所有结点的左右子树交换的函数，算法思想：首先交换B结点的左孩子的左右子树，然后交换B结点的右孩子的左右子树，最后交换B结点的左右孩子

    void BiTswap(BiTree B) {
        if (B) {
            //递归交换左右子树
            BiTswap(B->lchild);
            BiTswap(B->rchild);
            //交换左右子树
            BiTree T = B->lchild;
            B->lchild = B->rchild;
            B->rchild = T;
        }
    }