数据结构学习——二叉树

二叉树并且前/中/后序遍历

线索二叉树

二叉树并且前/中/后序遍历

//二叉树
#include<iostream>

using namespace std;

struct TreeNode{
    string data;
    TreeNode* leftchild;
    TreeNode* rightchild;
};

/*
这里我就是尝试把节点的创建和连接写一起了
显然，这种写法在二叉树较大的时候会很麻烦
*/
void createTreeAndConnect(TreeNode*&root,string data,string direction,TreeNode* parent){
    TreeNode* newnode = new TreeNode;
    newnode->data = data;
    newnode->leftchild = NULL;
    newnode->rightchild = NULL;
    if(root==NULL){
        root = newnode;
        return;
    }
    else{
        if(parent!=NULL){
            TreeNode* temp = parent;
            if(direction=="left"){
                temp->leftchild = newnode;
            }
            else if(direction=="right"){
                temp->rightchild = newnode;
            }
        }
        else{
            cout<<"没有父节点"<<endl;
        }
    }    
}

/*
选择另外一种写法，把节点的创建和连接分开

还有一种思路就是createTree和connectTree用另外一种方法封装好
也就是第一种方法，但是定位可以自己发挥想象
*/


TreeNode* createTree(string data){
    TreeNode* newnode = new TreeNode;
    newnode->data = data;
    newnode->leftchild = NULL;
    newnode->rightchild = NULL;
    return newnode;
}

void connectTree(TreeNode* your_node,string direction,TreeNode* parent){
    TreeNode* temp = parent;
    if(parent!=NULL){
        
        if(direction=="left"){
            temp->leftchild = your_node;
        }
        else if(direction=="right"){
            temp->rightchild = your_node;
        }
    }
    else{
        cout<<"没有父节点"<<endl;
    }
}
//Preorder Traversal：前序便利
void preorder_traversal(TreeNode* root){
    if(root==NULL){
        return;
    }
    else{
        cout<<root->data<<endl;
        preorder_traversal(root->leftchild);
        preorder_traversal(root->rightchild);
    }
}

//Inorder Traversal：中序遍历
void inorder_traversal(TreeNode* root){
    if(root==NULL){
        return;
    }
    else{
        inorder_traversal(root->leftchild);
        cout<<root->data<<endl;
        inorder_traversal(root->rightchild);

    }
}

//Postorder Traversal：后序遍历
void postorder_traversal(TreeNode* root){
    if(root==NULL){
        return;
    }
    else{
        postorder_traversal(root->leftchild);
        postorder_traversal(root->rightchild);
        cout<<root->data<<endl;
    }
}

int main(){
//这里的数字为满二叉树对应数字

/*
    TreeNode* root = NULL;
    createTreeAndConnect(root,"1","",NULL);
    createTreeAndConnect(root,"2","left",root);
    createTreeAndConnect(root,"3","right",root);
    createTreeAndConnect(root,"4","left",root->leftchild);
    createTreeAndConnect(root,"5","right",root->leftchild);
*/


    TreeNode* root=createTree("1");
    TreeNode* node1=createTree("2");
    TreeNode* node2=createTree("3");
    TreeNode* node3=createTree("4");
    TreeNode* node4=createTree("5");
    TreeNode* node5=createTree("6");
    TreeNode* node6=createTree("9");
    TreeNode* node7=createTree("12");

    connectTree(node1,"left",root);
    connectTree(node2,"right",root);
    connectTree(node3,"left",node1);
    connectTree(node4,"right",node1);
    connectTree(node5,"left",node2);
    connectTree(node6,"right",node3);
    connectTree(node7,"left",node5);


    cout<<"前序"<<endl;
    preorder_traversal(root);
    cout<<"中序"<<endl;
    inorder_traversal(root);
    cout<<"后序"<<endl;
    postorder_traversal(root);


    return 0;
}

前序：

中序

后序

线索二叉树

//线索二叉树
//threaded:有线状图案装饰的
//left/righttag:为0则指向左右孩子，为1则代表指向前驱或后继
#include<iostream>

using namespace std;

struct TreeNode{
    string data;
    TreeNode* leftchild;
    TreeNode* rightchild;
    bool lefttag;
    bool righttag;
};


TreeNode* createNode(string data){
    TreeNode* newnode = new TreeNode;
    newnode->leftchild = NULL;
    newnode->rightchild = NULL;
    newnode->lefttag = 0;
    newnode->righttag = 0;
    newnode->data = data;
    return newnode; 
}

void connectNode(TreeNode* parent_npde,TreeNode* your_node,string direction){
    if(parent_npde == NULL){
        cout<<"Parent node is NULL"<<endl;
        return;
    }
    else{
        if(direction == "left"){
            parent_npde->leftchild = your_node;            
        }
        else if(direction == "right"){
            parent_npde->rightchild = your_node;
        }

    }
}





void printTree(TreeNode* root){ 
    if(root == NULL){
        return;
    }
    else{
        
        printTree(root->leftchild);
        cout<<root->data<<endl;
        printTree(root->rightchild);
    }
}

/*
pre表示的是当前节点的前驱节点

如果当前节点的左孩子为空，则将当前节点的左孩子指向前驱节点，lefttag置为1

如果pre的节点的右孩子为空，pre的右节点指向当前节点，righttag置为1

结构有点类似于便利的结构，反正就是改位置
*/
void inThread(TreeNode* root, TreeNode*& pre){
    if (root == NULL)
    {
        return;
    }
    else{

        inThread(root->leftchild,pre);

        if(root->leftchild == NULL){
            root->leftchild = pre;
            root->lefttag = 1;
        }

        if(pre != NULL && pre->rightchild == NULL){
            pre->rightchild = root;
            pre->righttag = 1;
        }

        pre = root;//更新前驱节点

        inThread(root->rightchild,pre);
    }
}

void changeThread(TreeNode* root){ 
    TreeNode* pre=NULL;
    inThread(root,pre);
}

void inOrder(TreeNode* root){
    TreeNode* temp = root;
    while(temp!=NULL){
        //找到最左子节点
        while(temp->lefttag == 0){
            temp = temp->leftchild;
        }
        cout<<temp->data<<endl;

        //沿着线索访问
        while(temp!=NULL&&temp->righttag == 1){
            temp = temp->rightchild;
            cout<<temp->data<<endl;
        }
        //移动到右子节点（righttag为0）
        temp = temp->rightchild;
    } 
}

int main(){

    TreeNode* root=createNode("1");
    TreeNode* node1=createNode("2");
    TreeNode* node2=createNode("3");
    TreeNode* node3=createNode("4");
    TreeNode* node4=createNode("5");
    TreeNode* node5=createNode("6");
    TreeNode* node6=createNode("9");
    TreeNode* node7=createNode("12");

    connectNode(root,node1,"left");
    connectNode(root,node2,"right");
    connectNode(node1,node3,"left");
    connectNode(node1,node4,"right");
    connectNode(node2,node5,"left");
    connectNode(node3,node6,"right");
    connectNode(node5,node7,"left");

    cout<<"中序便利"<<endl;

    printTree(root);

    cout<<"中序线索化"<<endl;

    changeThread(root);

    inOrder(root);

    
    return 0;

}

就是把空指针利用起来，让空指针指向前/后节点（根据前中后序的顺序）我这里演示的是中序