二叉树遍历

Posted on In

二叉树遍历

1
2
3
4
5
6
struct Node{
    int data;
    Node* lchild;
    Node* rchild;
};
typedef Node* BiTree;

先序遍历

1
2
3
4
5
6
7
8
void preorder(BiTree T){
    if(T == NULL){
        return;
    }
    visit(T);
    preorder(T->lchild);
    preorder(T->rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void preorder(BiTree T){
    if(T == NULL){
        return;
    }
    std::stack<BiTree> st;
    st.push(T);
    BiTree p;
    while(!st.empty()){
        p = st.top();
        st.pop();
        visit(p);
        if(p->rchild != NULL){
            st.push(p->rchild);
        }
        if(p->lchild != NULL){
            st.push(p->rchild);
        }//先进右再进左
    }
}

中序遍历

1
2
3
4
5
6
7
8
void inorder(BiTree T){
    if(T == NULL){
        return;
    }
    inorder(T->lchild);
    visit(T);
    inorder(T->rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void inorder(BiTree T){
    if(T == NULL){
        return;
    }
    std::tack<BiTree> st;
    BiTree p = T;
    while(p != NULL || !st.empty()){
        while(p != NULL){
            st.push(p);
            p = p->lchild;
        }//一直向左
        p = st.top();
        st.pop();
        visit(p);
        p = p->rchild;
    }
    
}

后序遍历

1
2
3
4
5
6
7
8
void postorder(){
    if(T == NULL){
        return;
    }
    postorder(p->lchild);
    postorder(p->rchild);
    visit(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void postorder(){
	if(T == NULL){
        return;
    }
    std::stack<BiTree> st;
    BiTree p = T, r = NULL;
    while(p != NULL || !st.empty()){
        while(p != NULL){
            st.push(p);
            p = p->lchild;
        }
        p = st.top();
        if(p->rchild == NULL || r == p->rchild){
            st.pop();
            visit(p);
            r = p;
            p = NULL;
        }
        else{
            p = p->rchild;
        }
    }
}

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void levelorder(BiTree T){
    if(T == NULL){
        return;
    }
    queue<BiTree> q;
    q.push(T);
    BiTree p;
    while(!q.empty()){
        p = q.front();
        q.pop();
        visit(p);
        if(p->lchild != NULL){
            q.push(p->lchild);
        }
        if(p->rchild != NULL){
            q.push(q->rchild);
        }
    }
}

根据先序和中序构建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void construct(Node* root, int* pre, int* mid, int l1, int r1, int l2, int r2){
	if(l1 > r1)return;
	root->data = pre[l1];
	int pos = 0;
	for(int i=l2;i<=r2;i++){
		if(pre[l1] == mid[i]){
			pos = i;
			break;
		}
	}// 找到根结点在中序序列中的位置
	if(pos>l2){// 构造左子树
		root->left = new Node();
		construct(root->left, pre, mid, l1 + 1, l1 + pos - l2, l2, pos - 1 );
	}
	if(pos<r2){// 构造右子树
		root->right = new Node();
		construct(root->right, pre, mid, l1 - l2 + pos + 1, r1, pos + 1, r2);
	}
}