二叉树 | Zion

[honeyhhhh]

https://zionlove.site/binarytree/#more

基本概念二叉树由结点的有限集合构成，可以是空集，或者由一个根结点及两棵互不相交，分别称做这个根的左子树，右子树的二叉树组成的集合五种基本形态，空二叉树，只有一个根结点的二叉树，只有左子树，只有右子树，完全二叉树 根结点，每一个非空树都有且只有一个被称为根的结点，树根的判断依据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。叶(子)结点：没有任何子结点(子树)，或者树叶，叶子，终端结点，

[honeyhhhh]

根结点到叶结点的路径

void s()
    {
        list<postTag<T> > listStack;
        BinaryTreeNode<T> *p = root;
        postTag<T> t;

        while (p || !listStack.empty())
        {
            while (p!= NULL)
            {
                t.p = p;
                t.tag = Left;
                listStack.push_back(t);
                p = p->leftChild();
            }
            t = listStack.back();
            listStack.pop_back();
            p = t.p;
            if (t.tag == Left)
            {
                if (p->leftChild() == NULL && p->rightChild() == NULL) {
                    cout << p->info << ':';
                    listNode::iterator it;
                    for (it = listStack.begin(); it != listStack.end(); it++) {
                        postTag<T> l = *it;
                        cout << l.p->info;
                    }
                    cout << endl;
                }
                t.tag = Right;
                listStack.push_back(t);
                p = p->rightChild();
            }
            else
            {
                p = NULL;
            }
        }
    }