title: 树结构复习笔记
tags:

• 树
• 算法
• 数据结构
  abbrlink: 1fbca4b4
  date: 2021-11-17 20:52:32

1. 重建二叉树

输入一棵二叉树前序遍历和中序遍历的结果，重建该二叉树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> pos;
    vector<int> preorder, inorder;
    TreeNode* build(int a,int b,int x,int y){
        if(a>b) return NULL;
        auto root=new TreeNode(preorder[a]);
        int k=pos[root->val];
        root->left=build(a+1, a+1+k-1-x ,x, k-1);
        root->right=build(a+1+k-1-x+1, b, k+1, y);
        return root;
    }
    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder=_preorder, inorder=_inorder;
        int n=inorder.size();
        for(int i=0;i<inorder.size();i++)   pos[inorder[i]]=i;
        return build(0, n-1, 0, n-1);
    }
};

7078(线索二叉树，中序遍历)

#include <iostream>
#include<cstdio>
using namespace std;
typedef struct BThrNode{
    char data;
    struct BThrNode *lchild, *rchild;
    int ltag, rtag;
}BThrNode, *BThrTree;
BThrTree T,p;
void createBTree(BThrTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BThrNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}
BThrTree pre=NULL;
void InThread(BThrTree p)
{
    if(p!=NULL)
    {
        InThread(p->lchild);
        if(p->lchild==NULL){p->ltag=1; p->lchild=pre;}
        else p->ltag=0;
        if(p->rchild==NULL){p->rtag=1; pre->rchild=p;}
        else pre->rtag=0;
        pre=p;
        InThread(p->rchild);
    }
}
void TraveBTree(BThrTree &T)
{
    if(T)
    {
        TraveBTree(T->lchild);
        cout<<T->data;
        TraveBTree(T->rchild);
    }
}
int main()
{
    createBTree(T);
    InThread(p);
    TraveBTree(T);
    return 0;
}

7079（中序遍历）

#include <iostream>
#include<cstdio>
using namespace std;
typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
    //int ltag, rtag;
}BTNode, *BTree;
BTree T;
void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}
//void InThread(BThrTree p)
//{
//    if(p!=NULL)
//    {
//        InThread(p->lchild);
//        if(p->lchild==NULL){p->ltag=1; p->lchild=pre;}
//        else p->ltag=0;
//        if(p->rchild==NULL){p->rtag=1; pre->rchild=p;}
//        else pre->rtag=0;
//        pre=p;
//        InThread(p->rchild);
//    }
//}
void TraveBTree(BTree &T)
{
    if(T)
    {
        TraveBTree(T->lchild);
        cout<<T->data;
        TraveBTree(T->rchild);
    }
}
int main()
{
    createBTree(T);
    TraveBTree(T);
    return 0;
}

7077（层次遍历）

#include <iostream>
#include<cstdio>
#include <queue>
using namespace std;
const int MAX_SIZE=1010;
typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
    //int ltag, rtag;
}BTNode, *BTree;
typedef struct {
    BTNode data[MAX_SIZE];
    int front,rear;
}SQ;
BTree T;
void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}
//void InThread(BThrTree p)
//{
//    if(p!=NULL)
//    {
//        InThread(p->lchild);
//        if(p->lchild==NULL){p->ltag=1; p->lchild=pre;}
//        else p->ltag=0;
//        if(p->rchild==NULL){p->rtag=1; pre->rchild=p;}
//        else pre->rtag=0;
//        pre=p;
//        InThread(p->rchild);
//    }
//}
void TraveBTree(BTree &T)
{
    BTree p;
    queue<BTree> Q;
    if(T)
    {
        Q.push(T);
        while (!Q.empty())
        {
            p=Q.front();
            cout<<p->data;
            Q.pop();
            if(p->lchild)   Q.push(p->lchild);
            if(p->rchild)   Q.push(p->rchild);
        }
    }
}
int main()
{
    createBTree(T);
    TraveBTree(T);
    return 0;
}

7080（父亲孩子表示法）

#include<iostream>
#include<cstdio>
using namespace std;
typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
}BTNode, *BTree;
BTree T;
void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}
int Trave(BTree T)
{
    //int num=0;
    if(!T)  return 0;
    else
    {
        if(T->lchild==NULL && T->rchild==NULL)  return 1;
        else return Trave(T->lchild)+ Trave(T->rchild);
    }
    return 0;
}
int Depth(BTree &T)
{
    int m,n;
    if(T==NULL) return  0;
    else
    {
        m= Depth(T->lchild);
        n= Depth(T->rchild);
        if(m>n) return m+1;
        else    return n+1;
    }
}
int CountLeaf(BTree &T)
{
    int ans=0;
    if(T==NULL) return 0;
    if(T->lchild==NULL) return CountLeaf(T->rchild)+1;
    else
        return CountLeaf(T->lchild)+ CountLeaf(T->rchild);
}
int main()
{
    createBTree(T);
    //int ans= Depth(T);
    cout<<CountLeaf(T)<<endl;
    return 0;
}