生成二叉数及二叉树的遍历

不念不忘少年蓝@ 2023-06-13 11:08 11阅读 0赞

## 生成二叉数及二叉树的遍历 ##

中序生成满二叉数

linkedQueue<binaryTreeNode<char> *> q;
    void insertByLevel(char a, int j, int l) { 
        if (!q.empty()&&j<l) { 
            binaryTreeNode<char> *t = q.front();
            q.pop();
            t->element = a;
            if (2 * j + 1 < l) { 
                t->leftChild = new binaryTreeNode<char>;
                q.push(t->leftChild);
            }
            else { 
                t->leftChild = NULL;
            }
            if (2 * j + 2 < l) { 
                t->rightChild = new binaryTreeNode<char>;
                q.push(t->rightChild);
            }
            else { 
                t->rightChild = NULL;
            }
        }
    }
    
    binaryTreeNode<char> *creatByLevel(string str) { 
        int length = (int) str.size();
        while (!q.empty()) { 
            q.pop();
        }
        auto *t = new binaryTreeNode<char>;
        q.push(t);
        for (int j = 0; j < length; ++j) { 
            insertByLevel(str.at(j), j, length);
        }
        return t;
    }

根据前序和中序生成二叉树

binaryTreeNode<char> *creatByPreAndIn(string str1, string str2) { 
        int l = (int) str1.size();
        auto *t = new binaryTreeNode<char>;
        t->element = str1.at(0);
        for (int i = 0; i < l; ++i) { 
            if (str2.at(i) == str1.at(0)) { 
                if (i != 0&&l>1) { 
                    t->leftChild = creatByPreAndIn(str1.substr(1, i), str2.substr(0, i));
                } else { 
                    t->leftChild = NULL;
                }
                if (l > i + 1) { 
                    t->rightChild = creatByPreAndIn(str1.substr(i + 1, l - i - 1), str2.substr(i + 1, l - i - 1));
                } else { 
                    t->rightChild = NULL;
                }
            }
        }
        return t;
    }

二叉树的遍历

//输出
    template<class T>
    void visit(binaryTreeNode<T> *x, const int *i, int l) { 
            if (x!= nullptr) { 
                if (i[0] < l - 1) { 
                    cout << x->element << ",";
                } else if (i[0] == l - 1) { 
                    cout << x->element << endl;
                }
            }
    }
    
    //前序遍历
    template<class T>
    void preOrder(binaryTreeNode<T> *t, int *i, int l) { 
        if (t != NULL) { 
            visit(t, i, l);
            i[0]++;
            preOrder(t->leftChild, i, l);
            preOrder(t->rightChild, i, l);
        } else{ 
            return;
        }
    }
    //中序遍历
    template<class T>
    void inOrder(binaryTreeNode<T> *t, int *i, int l) { 
        if (t != NULL) { 
            inOrder(t->leftChild, i, l);
            visit(t, i, l);
            i[0]++;
            inOrder(t->rightChild, i, l);
        } else{ 
            return;
        }
    }
    //后序遍历
    template<class T>
    void postOrder(binaryTreeNode<T> *t, int *i, int l) { 
        if (t != NULL) { 
            postOrder(t->leftChild, i, l);
            postOrder(t->rightChild, i, l);
            visit(t, i, l);
            i[0]++;
        } else{ 
            return;
        }
    }