二叉树创建与遍历

节点定义：

class BinNode {
public:
    char data;
    BinNode* parent;
    BinNode* lchild;
    BinNode* rchild;
    BinNode(){ lchild = NULL; rchild = NULL; parent = NULL; }
    BinNode(char data2):data(data2) {
        lchild = NULL; rchild = NULL; parent = NULL;
    }
    BinNode(char data2, BinNode* parent2):data(data2) {
        lchild = NULL; rchild = NULL; parent = parent2;
    }
    void insertAsLeft(char data) {
        lchild = new BinNode(data,this);
    }
    void insertAsRight( char data) {
        rchild = new BinNode(data,this);
    }
};

树的定义：

class BinTree {
private:
    BinNode* root;
    string strtree;

public:
    BinTree() {
        root = NULL;
    }
    BinNode* getRoot() { return root; }//获取根节点
    void creatBTreeBycengci(string arr);//层次遍历产生一颗树，参考层次遍历
    void creatBTreeByString(string str) ;//通过一个字符串创建一棵树，调用creatBTree
    BinNode* creatBTree(int& pos);//通过先序遍历产生一棵树，使用递归
    void preorder(BinNode* T) ;//先序遍历以T为根节点的子树，递归
    void inorder(BinNode* T) ;//中序遍历以T为根节点的子树，递归
    void postorder(BinNode* T) ;//后序遍历以T为根节点的字数，递归

    void preorderByStack(BinNode* T);//先序遍历以T为根节点的子树，非递归
    void inorderByStack(BinNode* T);//中序遍历以T为根节点的子树，非递归
    void cengciByQueue(BinNode* T);//层次遍历，利用队列
}

以下是各种方法的实现:

首先是通过一个字符串先序遍历创建一颗树

    void creatBTreeByString(string str) {
        int pos = 0;
        strtree.assign(str);
        root = creatBTree(pos);
    }
    BinNode* creatBTree(int& pos) {
        BinNode* T;
        char ch = strtree[pos++];
        if (ch == '0')  T = NULL;
        else {
            T = new BinNode(ch);
            T->lchild = creatBTree(pos);
            T->rchild = creatBTree(pos);
        }
        return T;
    }

先序遍历、中序遍历、后序遍历的递归版本，此处无传如visit函数，只是访问节点的数据并输出：

void preorder(BinNode* T) {
        if (T == NULL)  return;
        char ch = T->data;
        cout << ch;
        preorder(T->lchild);
        preorder(T->rchild);
    }
    void inorder(BinNode* T) {//中序遍历以T为根节点的子树
        if (T == NULL)  return;
        inorder(T->lchild);
        char ch = T->data;
        cout << ch;
        inorder(T->rchild);
        
    }
    void postorder(BinNode* T) {
        if (T == NULL)  return;
        postorder(T->lchild);
        postorder(T->rchild);
        char ch = T->data;
        cout << ch;
    }

先序遍历的非递归版本（使用栈）：

void preorderByStack(BinNode* T) {
        stack<BinNode*> st;
        while (1) {
            while (T != NULL) {
                cout << T->data ;// visit(T),先访问左孩子
                st.push(T->rchild);//右孩子入栈，NULL也入栈，有进行判断，不会访问NULL
                T = T->lchild;//T 继续指向下一个左孩子
            }
            if (st.empty()) break;//所有右孩子都访问完了，结束。栈底是最上面的右孩子（它最先入栈）
            T = st.top(); st.pop();//pop出栈顶的右孩子，对其进行遍历
            
        }
    }

中序遍历的非递归版本（使用栈）：

    void inorderByStack(BinNode* T) {
        stack<BinNode*> st;
        while (1)
        {
            while (T != NULL) {
                st.push(T); T = T->lchild;//当跑到最左下方时，
                                         //当前节点即是left root right 中的root节点，
                                        //此时left相当于已经访问过，故接下来应该将控制权转给right
            }
            if (!st.empty()) {
                T = st.top(); st.pop();
                cout << T->data;//visit();每个节点访问完后都会试图访问 以右孩子为根节点的树，
                               //完了之后才会访问这个节点对应的父节点（即当前的栈顶）
                T = T->rchild;
            }
            else {
                break;
            }
        }
    }

层次遍历（使用队列）:

    void cengciByQueue(BinNode* T) {
        queue<BinNode*> q;
        q.push(T);//首先会push进根节点
        while (!q.empty()) {
            T = q.front(); q.pop();
            cout << T->data;//visit()
            if (T->lchild)  q.push(T->lchild);
            if (T->rchild)  q.push(T->rchild);
        }
    }
};

给出一个字符串，可参考层次遍历的方法创建一棵树（使用队列）：

    void creatBTreeBycengci(string arr) {//层次遍历产生一颗树，参考层次遍历
        int pos = 0;
        queue<BinNode*> q2;
        char data = arr[pos++];
        root = new BinNode(data);
        
        q2.push(root);
        BinNode* T = root;
        while (pos!=arr.length() ) {
            T = q2.front(); q2.pop();

            data = arr[pos++];
            if (data != '0')        T->lchild = new BinNode(data);
            else                    T->lchild = NULL;
            data = arr[pos++];
            if (data != '0')    T->rchild = new BinNode(data);
            else                    T->rchild = NULL;
            
            if(T->lchild)   q2.push(T->lchild);//存在才推进去
            if(T->rchild)   q2.push(T->rchild);
        }

    }