二叉树 - Githubissues

二叉树互推

前序、中序、后序遍历（三种遍历方法，从语义上，是相对于根而言的）前序：先根节点，再左节点，再右节点中序：先左，再根，最后右后序：先左，再右，最后根

已知前序、中序遍历，求后序遍历前序遍历： GDAFEMHZ 中序遍历： ADEFGHMZ 根据前序遍历得知G是根节点，所以ADEF为左，HMZ为右在前序遍历中ADEF中D先出现所以D是根，根据中序遍历D的左树为A右树为EFG A无左右树，返回到D在开始判EFG，和之上的过程相同。所以流程为 1 确定根,确定左子树，确定右子树。 2 在左子树中递归。 3 在右子树中递归。

已知中序和后序遍历，求前序遍历也是一样的中序遍历: ADEFGHMZ 后序遍历: AEFDHZMG 后序中最后一个为目前树的根节点，根据这个根，可以在中序中找到这个根的左和右子树对应的中序，若中序左子树长为l，那么后序中前l个为左子树的后序，剩下的（去除最后的根）为右子树的后序流程为 1 确定根,确定左子树，确定右子树。 2 在左子树中递归。 3 在右子树中递归。

#include <iostream>
#include <stdio.h>
using namespace std;

class TreeNode{
public:
    TreeNode* left;
    TreeNode* right;
    char val;
};

TreeNode* CreateTreeFromPrIn(char* pr, char* in, int len){
    TreeNode* node = new TreeNode;
    if(len==0){
        return nullptr;
    }
    node->val = *pr; //前向的第一个为该子树根节点

    int rootIndex = 0;
    for(;rootIndex<len;rootIndex++){
        if(in[rootIndex]==*pr){
            break;
        }
    }
    node->left = CreateTreeFromPrIn(pr+1, in, rootIndex); //左子树递归
    node->right = CreateTreeFromPrIn(pr+rootIndex+1, in+rootIndex+1, len-rootIndex-1);//右子树递归

    return node;
}

TreeNode* CreateTreeFromInAf(char* in, char* af, int len){
    TreeNode* node = new TreeNode;
    if(len==0){
        return nullptr;
    }
    node->val = *(af+len-1);//后向的最后一个为该子树根节点
    int rootindex = 0;
    for (;rootindex<len;rootindex++) {
        if(in[rootindex]==node->val){
            break;
        }
    }
    node->left = CreateTreeFromInAf(in, af, rootindex);//左子树为中序的前rootindex个，也是后序的前rootindex个（因为后序是先打印完af[last]的左子树）
    node->right = CreateTreeFromInAf(in+rootindex+1, af+rootindex, len-1-rootindex);
    return node;
}

void TravelByPr(TreeNode* header){
    if(header!=nullptr){
        cout<<header->val;
        TravelByPr(header->left);
        TravelByPr(header->right);
    }
    return;
}

void TravelByIn(TreeNode* header){
    if(header!=nullptr){
        TravelByIn(header->left);
        cout<<header->val;
        TravelByIn(header->right);
    }
    return;
}

void TravelByAf(TreeNode* header){
    if(header!=nullptr){
        TravelByAf(header->left);
        TravelByAf(header->right);
        cout<<header->val;
    }
    return;
}

int main()
{
    char* pr = "GDAFEMHZ";
    char* in = "ADEFGHMZ";
    char* af = "AEFDHZMG";
    TreeNode* header;
    header = CreateTreeFromPrIn(pr, in, 8);
    TravelByAf(header);
    header = CreateTreeFromInAf(in, af, 8);
    cout<<""<<endl;
    TravelByPr(header);
    return 0;
}

二叉树非递归遍历

前序对于任一结点P： 1)访问结点P，并将结点P入栈; 2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P; 3)直到P为NULL并且栈为空，则遍历结束。

void preOrder2(BinTree *root)     //非递归前序遍历 
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<"";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

中序

void inOrder2(BinTree *root)      //非递归中序遍历
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<"";
            s.pop();
            p=p->rchild;
        }
    }    
}

后序对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

void postOrder2(BinTree *root)    //非递归后序遍历
{
    stack<BTNode*> s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)              //沿左子树一直往下搜索，直至出现没有左子树的结点 
        {
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty())
        {
            temp=s.top();
            s.pop();
            if(temp->isFirst==true)     //表示是第一次出现在栈顶 
             {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;    
            }
            else//第二次出现在栈顶 
             {
                cout<<temp->btnode->data<<"";
                p=NULL;
            }
        }
    }    
}

二叉树的逐层遍历，左视图与右视图

都是利用队列实现，遍历到某个点后将该点的左右孩子入队。

//  main.cpp
//  Norm_Alg
//
//  Created by FanYizhe on 2019/3/26.
//  Copyright © 2019年 FanYizhe. All rights reserved.
//

#include <iostream>
#include <queue>

using namespace std;

class TreeNode{
public:
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int val){
        this->val = val;
        this->left = NULL;
        this->right = NULL;

    }
};

/*逐行遍历二叉树*/
void travel_level(TreeNode* head){
    queue<TreeNode*> q;
    q.push(head);
    while (!q.empty()) {
        head = q.front();
        q.pop();
        cout<<head->val<<endl;
        if(head->left!=NULL){
            q.push(head->left);
        }
        if(head->right!=NULL){
            q.push(head->right);
        }
    }
}

/*左视图*/
void left_map(TreeNode* head, int level, queue<TreeNode*>& q){
    if (head==NULL) {
        return;
    }
    if(q.size()==level){
        q.push(head);
        cout<<head->val<<endl;
    }
    left_map(head->left, level+1, q);
    left_map(head->right, level+1, q);
}

/*右视图*/
void right_map(TreeNode* head, int level, queue<TreeNode*>& q){
    if (head==NULL) {
        return;
    }
    if(q.size()==level){
        q.push(head);
        cout<<head->val<<endl;
    }
    right_map(head->right, level+1, q);
    right_map(head->left, level+1, q);
}

int main(int argc, const char * argv[]) {
    TreeNode* node = new TreeNode(1);
    node->left = new TreeNode(2);
    node->right = new TreeNode(3);
    TreeNode* root = node;
    node = root->left;
    node->left = new TreeNode(4);
    node->right = new TreeNode(5);
    node = root->right;
    node->left = new TreeNode(6);
    node->right = new TreeNode(7);
    cout<<"Travel Totel Tree in Rows"<<endl;
    travel_level(root);
    cout<<"Left Perspective of Tree"<<endl;
    queue<TreeNode*> q;
    left_map(root, 0, q);
    queue<TreeNode*> emp;
    swap(emp, q);
    cout<<"Right Perspective of Tree"<<endl;
    right_map(root, 0, q);

    // insert code here...
    std::cout << "Hello, World!\n";
    return 0;
}

FanDoubleLucky / notebook

二叉树 #1

二叉树互推

二叉树非递归遍历

二叉树的逐层遍历，左视图与右视图