二叉树操作集锦（递归遍历，非递归遍历，求深度，结点个数，完全二叉树等）

二叉树操作集锦（递归遍历，非递归遍历，求深度）

一、二叉树操作集锦

1.1 二叉树定义

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BNode,*BTree;
1
2
3
4

1.2 二叉树创建

先序创建二叉树

//先序创建二叉树
void CreateBTree(BTree *T){
    int data;
    scanf("%d",&data);
    if(data == -1){
        *T = NULL;
        return;
    }
    *T = (BTree)malloc(sizeof(BNode));
    (*T)->data = data;
    CreateBTree(&(*T)->lchild);
    CreateBTree(&(*T)->rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

输入格式：1 2 4 -1 -1 5 -1 -1 3 -1 -1

1.3 二叉树遍历

1.3.1 二叉树递归遍历

1.3.1.1 二叉树先序递归遍历

//先序遍历二叉树
void PreOrder(BTree T){
    if(T == NULL){
        return;
    }
    printf("%d ",T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}
1
2
3
4
5
6
7
8
9

1.3.1.2 二叉树中序递归遍历

//中序遍历二叉树
void InOrder(BTree T){
    if(T == NULL){
        return;
    }
    InOrder(T->lchild);
    printf("%d ",T->data);
    InOrder(T->rchild);
}
1
2
3
4
5
6
7
8
9

1.3.1.3 二叉树后序递归遍历

//后序遍历二叉树
void PostOrder(BTree T){
    if(T == NULL){
        return;
    }
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    printf("%d ",T->data);
}
1
2
3
4
5
6
7
8
9

1.3.2 二叉树非递归遍历

1.3.2.1 二叉树先序非递归遍历

//非递归先序遍历二叉树
void PreOrder2(BTree T){
    BTree stack[100];
    int top = -1;
    BTree p = T;
    while(p != NULL || top != -1){
        while(p != NULL){
            printf("%d ",p->data);
            stack[++top] = p;
            p = p->lchild;
        }
        if(top != -1){
            p = stack[top--];
            p = p->rchild;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.3.2.2 二叉树中序非递归遍历

//非递归中序遍历二叉树
void InOrder2(BTree T){
    BTree stack[100];
    int top = -1;
    BTree p = T;
    while(p != NULL || top != -1){
        while(p != NULL){
            stack[++top] = p;
            p = p->lchild;
        }
        if(top != -1){
            p = stack[top--];
            printf("%d ",p->data);
            p = p->rchild;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.3.2.3 二叉树后序非递归遍历

//非递归后序遍历二叉树
void PostOrder2(BTree T){
    BTree stack[100];
    int top = -1;
    BTree p = T;        //p指向当前节点
    BTree r = NULL;     //r指向刚刚访问过的结点
    while(p != NULL || top != -1){
        while(p != NULL){
            stack[++top] = p;           //将当前节点入栈
            p = p->lchild;
        }
        if(top != -1){
            p = stack[top];
            if(p->rchild == NULL || p->rchild == r){
                printf("%d ",p->data);
                top--;
                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
20
21
22
23
24

1.3.3 二叉树层次遍历

//层次遍历二叉树
void LevelOrder(BTree T){
    BTree queue[100];
    int front = 0,rear = 0;
    if(T == NULL){
        return;
    }
    queue[rear++] = T;
    while(front != rear){
        BTree p = queue[front++];
        printf("%d ",p->data);
        if(p->lchild != NULL){
            queue[rear++] = p->lchild;
        }
        if(p->rchild != NULL){
            queue[rear++] = p->rchild;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.4 二叉树求深度（高度）

//求二叉树的深度
int getDepth(BTree T){
    int ldepth,rdepth;
    if(T == NULL){
        return 0;
    }
    ldepth = getDepth(T->lchild);
    rdepth = getDepth(T->rchild);
    return ldepth > rdepth ? ldepth+1 : rdepth+1;
}
1
2
3
4
5
6
7
8
9
10

1.5 二叉树叶子结点个数

int LeafCount(BTree T){
    if(T == NULL){
        return 0;
    }
    if(T->lchild == NULL && T->rchild == NULL){
        return 1;
    }
    return LeafCount(T->lchild) + LeafCount(T->rchild);
}
1
2
3
4
5
6
7
8
9

1.6 二叉树度为1的结点个数

int count1(BTree T){
    if(T == NULL)
        return 0;
    if(T->lchild == NULL && T->rchild != NULL)
        return 1 + count1(T->rchild);
    if(T->lchild != NULL && T->rchild == NULL)
        return 1 + count1(T->lchild);
    return count1(T->lchild) + count1(T->rchild);
}
1
2
3
4
5
6
7
8
9

1.7 二叉树度为2的结点个数

int count = 0;
void Count2(BTree T){
    if(T == NULL)
        return;
    if(T->lchild != NULL && T->rchild != NULL)
        count++;
    Count2(T->lchild);
    Count2(T->rchild);
}
1
2
3
4
5
6
7
8
9

1.8 二叉树是否为完全二叉树

int IsComplete(BTree T){
    if(T == NULL)
        return 1;
    int flag = 0;
    BTree queue[100];
    int front = 0,rear = 0;
    queue[rear++] = T;
    while(front != rear){
        BTree p = queue[front++];
        if(flag == 1 && (p->lchild != NULL || p->rchild != NULL))
            return 0;
        if(p->lchild != NULL && p->rchild != NULL){
            queue[rear++] = p->lchild;
            queue[rear++] = p->rchild;
        }else if(p->lchild != NULL && p->rchild == NULL){
            queue[rear++] = p->lchild;
            flag = 1;
        }else if(p->lchild == NULL && p->rchild != NULL){
            return 0;
        }else{
            flag = 1;
        }
    }
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1.9 二叉树交换左右子树

void Exchange(BTree *T){
    if(*T == NULL)
        return;
    BTree temp = (*T)->lchild;
    (*T)->lchild = (*T)->rchild;
    (*T)->rchild = temp;
    Exchange(&(*T)->lchild);
    Exchange(&(*T)->rchild);
}
1
2
3
4
5
6
7
8
9

1.10 二叉树根结点到叶子结点路径

void PrintPath(BTree T,int path[],int top){
    if(T == NULL)
        return;
    path[++top] = T->data;
    if(T->lchild == NULL && T->rchild == NULL){
        int i = 0;
        for(i = 0;i<=top;i++){
            printf("%d ",path[i]);
        }
        printf("\n");
    }
    PrintPath(T->lchild,path,top);
    PrintPath(T->rchild,path,top);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14