• 王道数据结构二叉树算法大题代码总结

    第五章

    1. 非空二叉树先序序列和后序序列正好相反，该二叉树的形态为：高度和结点数相同的二叉树

    在这里插入图片描述

    2. 同上，正好相反：只有根节点的二叉树
    3. 后序遍历二叉树的非递归写法
    void PostOrder(BiTree T)
{
    InitStack(S);
    p = T;r = NULL;
    while (p || Is_Empty(S)) {
        if (p) {
            push(S,p);
            p = p->lchild;
        } else {
            GetTop(S,p);
            if (p->rchild&&p->rchild != r) {
                push(S,P->rchild);
                p = p->rchild;
            } else {
                pop(S,p);visit(p->data);
                r = p;p = NULL;
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    附注：

    • 遍历递归写法
    void PreOrder(BiTree T)
{
    if (T != NULL) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BiTree T)
{
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree T)
{
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 非递归写法
    • 中序
    void InOrder2(BiTree T) 
{
    InitStack(S);BiTree p = T;
    while (p || !IsEmpty(S)) {
        if (p) {
            Push(S,p);
            p = p->lchild;
        } else {
            Pop(S,p);visit(p);
            p = p->rchild;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 前序
    void PreOrder2(BiTree T)
{
    InitStack(S);BiTree p = T;
    while (p || !IsEmpty(S)) {
        if (p) {
            visit(p);Push(S,p);
            p = p->lchild;
        } else {
            Pop(S,p);
            p = p->rchild;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 层次遍历算法
    void LevelOrder(BiTree T)
{
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while (!IsEmpty(Q)) {
        DeQueue(Q,p);visit(p);
        if (p->lchild != NULL) {
            EnQueue(Q,p->lchild);
        } 
        if (p->rchild != NULL) {
            EnQueue(Q,p->rchild);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    4. 自下而上、从右向左的层次遍历算法
    void InvertLevel(BiTree bt)
{
    Stack S;Queue Q;
    if (bit != NULL) {
        InitStack(S);
        InitQueue(Q);
        EnQueue(Q,bt);
        while (IsEmpty(Q) == false) {
            DeQueue(Q,p);
            Push(s,p);
            if (p->lchild)  
                EnQueue(Q,p->lchild);
            if (p->rchild)
                EnQueue(Q,p->rchild);
        }
        while (IsEmpty(s) == false) {
            Pop(s,p);
            visit(p->data);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    5. 设计一个非递归算法求二叉树的高度（二叉链表存储）

    按照先序遍历，叶子结点出栈时的栈的长度就是深度

    //二叉链表的结构
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//层次遍历二叉树
int GetBiTreeHeigth(BiTree T){
    if(T==NULL) retrun 0;  //空树，高度为0;
    
    InitQueue Q[MaxSize];  //初始化一个空队列;
    int front =-1,rear=-1;
    int last=0;
    int level =0;
    BiTree P;
    
    //EnQueue(Q,T);  //将当前结点入队；
    Q[++rear] = T;
    
    while(front <rear){
        P = Q[++front]; //出队，DeQueue(Q,Q.front);
        
        //访问当前结点visit(T);
        if(P->lchild){
            Q[++rear] = P->lchild; //EnQueue(Q,T->lchild);
        }
        if(P->rchild){
            Q[++rear] = P->rchild; //EnQueue(Q,T->rchild);
        }
        
        if(front==last){//当前层最后结点；
            level++;
            last=rear;//上一层最后一个节点，出队的时候，队首正好是下一层的最后一个节点
        }
    }
    
    return level;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 递归写法
    int Btdepth2(BiTree T)
{
	if(T == NULL) {
		return 0;
	}
    ldep = Btdepth2(T->lchild);
    rdep = Btdepth2(T->rchild);
    return max(ldep,rdep)+1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    6. 根据先序遍历和中序遍历建立二叉树（二叉链表）
    BiTree PreInCreat(ElemType A[],ElemType B[],int l1,int h1,int l2,int h2)
{
    root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = A[l1];
    for(i = l2;B[i]!=root->data;i ++) ;
    llen = i-l2;
    rlen = h2-i;
    if (llen) root->lchild = PreInCreat(A,B,l1+1,l1+llen,l2,l2+llen-1);
    else root->lchild = NULL;
    if (rlen) root->rchild = PreInCreat(A,B,h1-rlen+1,h1,h2-rlen+1,h2);
    else root->rchild = NULL;
    return root;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    7. 二叉链表存储，判别给定二叉树是否是完全二叉树

    层次遍历，遇到一个只有左儿子或者

    bool IsComplete(BiTree T)
{
    InitQueue(Q);
    if (!T) 
        return 1;
    EnQueue(Q,T);
    while (!IsEmpty(Q)) {
        DeQueue(Q,p);
        if (p) {
	        if (p->lchild==NULL&&p->rchild) return 0;//只有右儿子，没有左儿子。
            EnQueue(Q,p->lchild);
            EnQueue(Q,p->rchild);
        } else {
            while (!IsEmpty(Q)) {
                DeQueue(Q,p);
                if (p) 
                    return 0;
            }
        }
    }
    return 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    8. 计算给定二叉树的所有双分支节点个数

    层次遍历或者递归

    int DsonNodes(BiTree b)
{
    if (b == NULL) 
        return 0;
    else if (b->lchild != NULL&&b->rchild != NULL) {
        return DsonNodes(b->lchild) + DsonNodes(b->rchild) + 1; 
    } else {
        return DsonNodes(b->lchild) + DsonNodes(b->rchild);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    9. 把树中所有结点的左右子树进行交换

    创建一个新树，递归赋值-左子树赋给右儿子，右子树赋给左儿子
    这个想法可能有点问题

    void swap(BiTree b)
{
	if (b) {
		swap(b->lchild);
		swap(b->rchild);
		temp = b->lchild;
		b->lchild = b->rchild;
		b->rchild = temp;
	}
}
//own idea;
BiTree T2;
void swap2(BiTree T,BiTree T2)
{
	if(T) {
		swap(T->lchild,T2->lchild);
		swap(T->rchild,T2->rchild);
		T2->lchild = T->rchild;
		T2->rchild = T->lchild;
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    10. 二叉链表存储，求先序遍历序列中第k个结点的值

    直接操作就行

    int i = 1;
ElemType PreNode(BiTree b,int k)
{
    if (b == NULL) return '#';
    if (i == k) 
        return b->data;
    i ++;
    ch = preNode (b->lchild,k);
    if (ch != '#')  
        return ch;
    ch = PreNode(b->rchild,k);
        return ch;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    11. 二叉链表存储，对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间

    看代码

    void Search(BiTree bt,ElemType x)
{
    BiTree Q[];
    if (bt) {
        if (bt->data == x) {
            DeleteXTree(bt);
            exit(0);
        } 
        InitQueue(Q);
        EnQueue(Q,bt);
        while (!IsEmpty(Q)) {
            DeQueue(Q,p);
            if (p->lchild) {
                if (p->lchild->data == x){
                    DeleteXTree(p->lchild);
                    p->lchild = NULL;
                } else {
                    EnQueue(Q,p->lchild);
                }
            }
            if (p->rchild) {
                if (p->rchild->data == x) {
                    DeleteXTree(p->rchild);p->rchild = NULL;
                } else{
                    EnQueue(Q,p->rchild);
                }
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    二叉树的基本运算 数据结构
    doc 0星 超过10%的资源 162KB
    下载
    12. 在二叉树中查找值为x的结点，打印值为x的结点的所有祖先（值为x的结点不多于一个）

    非递归后序遍历，找到值为x的结点时，把栈中所有元素打印出来。

    void Search(BiTree bt,ElemType x)
{
    stack s[];
    top = 0;
    while (bt != NULL || top > 0) {
        while (bt != NULL&&bt->data != x) {
            s[++top].t = bt;
            s[top].tag = 0;
            bt = bt->lchild;
        }
        if (bt != NULL&&bt-data==x) {
            printf("所查结点的所有祖先结点的值为：\n");
            for (i = 1;i <= top;i ++) 
                printf("%d",s[i].t->data);
            exit(1);
        }
        while (tag != 0&&s[top].tag == 1) {
            top --;
        }
        if (top != 0) {
            s[top].tag = 1;
            bt = s[top].t->rchild;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    13. 最近公共祖先结点

    一直除以2
    倍增求LCA

    答案思路：
    采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。假设p在q的左边，后序遍历先访问到p，先将栈中元素复制到另一辅助栈中。继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中匹配，第一个匹配的就是LCA。

    略。。。不是最优

    • 1
    14. 求非空二叉树b的宽度

    层次遍历，一次整完一层的元素，然后队列最大长度就是所求

    //求二叉树的宽度
int WidthOfBiTree(BiTree root)
{
    if(root == NULL)
        return 0;

    int maxWidth = 0;
    deque<BiTree> d;
    d.push_back(root);

    while(true)
    {
        int len = d.size();
        if(len == 0)
            break;
        while(len > 0)
        {
            BiTree temp = d.front();
            d.pop_front();
            len--;
            if(temp->Lchild)
                d.push_back(temp->Lchild);
            if(temp->Rchild)
                d.push_back(temp->Rchild);
        }
        maxWidth = maxWidth > d.size() ? maxWidth : d.size();

    }
    return maxWidth;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    15. 一颗满二叉树（结点值均不相同）,已知先序序列，求后序序列。
    void PreToPost(ElemType pre[],int l1,int h1,ElemType post[],int l2,int h2) 
{
    int half;
    if (h1 >= l1) {
        post[h2] = pre[l1];
        half = (h1 - l1)/2;
        PreToPost(pre,l1+1,l1+half,post,l2,l2+half-1);
        PreToPost(pre,l1+half+1,h1,post,l2+half,h2-1);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    16. 将二叉树的叶节点按从左向右的顺序连接成一个单链表，表头指针为head，右节点的右指针链域指向下一个叶节点

    层次遍历，队列中存放结点——错误思路，因为不是完全二叉树

    答案 ：中序遍历，设置前驱节点指针pre。第一个叶结点右指针head指向，遍历到叶结点时，就将它前驱的rchild指针指向它，子u后一个叶结点的rchild为空。

    LinkedList head, pre = NULL;
LinkedList InOrder(BiTree bt)
{
    if (bt) {
        InOrder(bt->lchild);
        if (bt->lchild == NULL&&bt->rchild == NULL) {
            if (pre == NULL) {
                head = bt;
                pre  = bt;
            } else {
                pre ->rchild = bt;
                pre = bt;
            }
        }
        InOrder(bt->rchild);
        pre->rchild = NULL;
    }
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    17. 判断是否相似两个二叉树
    数据结构之树与二叉树算法总结
    doc 0星 超过10%的资源 295KB
    下载

    递归

    int similar(BiTree T1,BiTree T2)
{
    int leftS,rightS;
    if (T1 == NULL &&T2 == NULL) {
        return 1;
    } else if (T1 == NULL||T2== NULL) {
        return 0;
    } else {
        leftS = similar(T1->lchild,T2->lchild);
        rightS = similar(T1->rchild,T2->rchild);
        return leftS&&rightS;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    18. 中序线索二叉树中找指定结点在后序的前驱结点的算法

    算法思想：
    在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点为叶子，若其中序左线索指向某祖先节点f，若f有左子女，则其左子女是结点p的后序前驱；若f无左子女，则顺其前驱找双亲的双亲，直到找到双亲有左子女。还有一种情况，若p是中序遍历的第一个结点，则结点p在中序和后序下均无前驱。

    BiThrTree InPostPre(BiThrTree t,BiThrTree p)
{
    BiThrTree q;
    if (p->rtag == 0) q=p->rchild;
    else if (p->ltag == 0) q = p->lchild;
    else if (p->lchild== NULL) q=NULL;
    else {
        while (p->ltag==1&&p->lchild!=NULL)
            p = p->lchild;
        if (p->ltag==0) q = p->lchild;
        else q = NULL;
    }
    return q;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    19. 【2014年真题】计算二叉树的带权路径长度
      1. 基本设计思想
        ①. 基于先序递归遍历的算法思想是
        用一个静态变量记录wpl，把每个结点的深度作为一个递归函数的一个参数传递，步骤如下：
        若该结点是叶结点，则变量wpl加上该结点的深度与权值之积。
        若该结点是非叶结点，则左子树不为空时，对左子树调用递归算法，右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1.
        最后返回计算出的wpl计科
        ②. 基于层次遍历算法思想
        使用队列进行层次遍历，并记录当前的层数
        当遍历到叶节点时，累计wpl
        当遍历到非叶节点，把该结点的子树加入队列，当某节点为该层的最后一个结点时，层数自增1.
        队列空时遍历结束。
      1. 数据类型定义
    typedef struct BiTNode{
    int weight;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


    • 1
    • 2
    • 3
    • 4
    • 5
      1. 代码实现
    
int WPL(BiTree root) {
    return wpl_PreOrder(root,0);
}

int wpl_PreOrder(BiTree root,int deep)
{
    static int wpl = 0;
    if (root->lchild== NULL&&root->rchild== NULL) wpl+=deep*root->weight;
    if (root->lchild!= NULL) wpl_PreOrder(root->lchild,deep+1);
    if (root->rchild!= NULL) wpl_PreOrder(root->rchild,deep+1);
    return wpl;
}


typedef struct
{
	LBTree* p;
	int lno;
}Queue;
int WPL(LBTree* lbt)
{
	Queue Q[maxSize];
	int front,rear;
	front = rear = 0;
	int Lno = 1;
	LBTree* q = lbt;
	Q[rear].p = q;
	Q[rear].lno = Lno;
	rear++;
	while (front != rear)
	{
		q = Q[front].p;
		Lno = Q[front].lno;
		front++;
		if (q->lchild != NULL)
		{
			Q[rear].p = q->lchild;
			Q[rear].lno = Lno + 1;
			rear++;
		}
		if (q->rchild != NULL)
		{
			Q[rear].p = q->rchild;
			Q[rear].lno = Lno + 1;
			rear++;
		}
	}
	int wpl = 0;
	for (int i = 0; i < rear; i++)
	{	
		if (Q[i].p->weigth != -1)
			wpl += (Q[i].p->weigth) * (Q[i].p->lno - 1);
	}
	return wpl;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    20. 【2017年真题】将给定的二叉树转换为等价的中缀表达式（通过括号反映操作符的计算次序）
      1. 基本设计思想

    算法的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。表达式树中分支节点所对应的子表达式的计算次序，由该分支节点所处的位置决定。在适当位置增加必要的括号。显然表达式最外层和根节点不需要添加括号

      1. 算法实现
    void BtreeToE(BTree *root)
{
    BtreeToExp(root,1);
}

void BtreeToExp(BiTree *root,int deep)
{
    if (root == NULL) return ;
    else if (root->next == NULL&&root->right==NULL) {
        printf("%s",root->data);
    } else {
        if (deep > 1) printf("(");
        BtreeToExp(root->left,deep+1);
        printf("%s",root->data);
        BtreeToExp(root->right,deep+1);
        if (deep>1) printf("%s",")");
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
  • 相关阅读:
    SQLServer统计监控SQL执行计划突变的方法
    flask 实践
    String&StringBuilder&StringBuffer
    LeetCode 0140. 单词拆分 II
    mnist数据集
    大数据队列Kafka
    1194. 锦标赛优胜者
    Android 系统 使用blktrace的方法
    jenkins-2.426.1-1.1.noarch.rpm 的公钥没有安装
    go基础语法50问，来看看你的go基础合格了吗？
  • 原文地址：https://blog.csdn.net/qq_46264636/article/details/126044595