Fork me on GitHub

二叉树

发表于 | 分类于
字数统计: 959 | 阅读时长 ≈ 4

二叉树的遍历：

  • 前序遍历：根左右

  • 中序遍历：左根右

  • 后序遍历：左右根

  • 层次遍历：一层一层的遍历，类似广度优先

二叉树的存储结构

  • 二叉树以二叉链表结构存储，也就是1个数据域，两个指针域（分别指向左右孩子）
1
2
3
4
5
6
7
//二叉树的二叉链表结构定义
typedef char ElemType;
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree
  • 二叉树的建立，先按照前序遍历的方式建立二叉树，当然也可以按照中序遍历或者后序遍历的方式建立二叉树
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
26
27
28
//以前序遍历的方式建立二叉树
void CreateBiTree(BiTree *T)
{
    ElemType ch;
    cin>>ch;
    if(ch=='#')
    {
        *T=NULL;
    }
    else
    {

        *T=(BiTNode)malloc(sizeof(BiTNode));
        if(!*T)
        {
            exit(OVERFLOW);//分配内存失败退出

        }
        else
        {
            (*T)->data=ch;//生成结点
            CreateBiTree(&(*T)->lchild);//构造左子树
            CreateBiTree(&(*T)->rchild);//构造右子树

        }
    }

}

递归前序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//递归方式前序遍历二叉树

void PreOrderTraverse(BiTree T,int level)
{
    if(T==NULL)
    {
        return;
    }
    else
    {
        Display(T->data);
        Floor(T->data,level);//输出了层数
        PreOrderTraverse(T->lchild,level+1);
        PreOrderTraverse(T->rchild,level+1);
    }
}

递归中序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//递归中序遍历
void InOrderTraverse(BiTree T,int level)
{    if(T==NULL)
    {
        return;
    }
    else
    {
        InOrderTraverse(T->lchild,level+1);
        Display(T->data);
        Floor(T->data,level);
        InOrderTraverse(T->rchild,level+1);
    }
}

递归后序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//递归后序遍历
void PostOrderTraverse(BiTree T,int level)
{    if(T==NULL)
    {
        return;
    }
    else
    {
        PostOrderTraverse(T->lchild,level+1);
        PostOrderTraverse(T->rchild,level+1);
        Display(T->data);
        Floor(T->data,level);
    }
}

中序遍历非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InOrder(BiTree T)
{
	InitStack(S);
	BiTree p=T;//p是遍历指针
	while(p||!isEmpty(S))
	{
		if(p)//根指针进站，遍历左子树
		{
			Push(S,p);
			p=p->lchild;
		}
		else{
			Pop(S,p);
			visit(p);
			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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<stdlib.h>
using namespace std;  
typedef char ElemType;//二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右子结点）
typedef struct BiTNode {
    ElemType data;
    struct BiTNode lchild,rchild;
}BiTNode,*BiTree;

//以前序遍历的方式建立二叉树
void CreateBiTree(BiTree *T) {
    ElemType ch;
    cin>>ch;
    if(ch=='#')
    {
        *T=NULL;
    }
    else
    {
`       T=(BiTNode)malloc(sizeof(BiTNode));
        if(!T)
        {
            exit(OVERFLOW);//分配内存失败退出
        }
        else
        {
             (T)->data=ch;//生成结点
             CreateBiTree(&(T)->lchild);//构造左子树
             CreateBiTree(&(*T)->rchild);//构造右子树
        }
    }
}
        
//将二叉树前序遍历输出
void Display(ElemType ch) {
    cout<<ch<<" ";
}

//在输出的基础上，输出层数
void Floor(ElemType ch,int level) {
    cout<<ch<<"在第"<<level<<"层"<<end;
}

//递归方式前序遍历二叉树
void PreOrderTraverse(BiTree T,int level) {
    if(T==NULL)
    {
        return;
    }
    else
    {
        Display(T->data);
        Floor(T->data,level);//输出了层数
        PreOrderTraverse(T->lchild,level+1);
        PreOrderTraverse(T->rchild,level+1);
    }
}

//递归中序遍历
void InOrderTraverse(BiTree T,int level) {
    if(T==NULL)
    {
        return;
    }
    else
    {
        InOrderTraverse(T->lchild,level+1);
        Display(T->data);
        Floor(T->data,level);
        InOrderTraverse(T->rchild,level+1);
    }
}

//递归后序遍历
void PostOrderTraverse(BiTree T,int level) {
    if(T==NULL)
    {
        return;
    }
    else
    {
        PostOrderTraverse(T->lchild,level+1);
        PostOrderTraverse(T->rchild,level+1);
        Display(T->data);
        Floor(T->data,level);
    }
}

int main() {    
    int level=1;//表示层数
    BiTree T=NULL;
    cout<<"请以前序遍历的方式输入二叉树：";//类似输入AB#D##C##
    CreateBiTree(&T);//建立二叉树，没有树，无法遍历
    cout<<"递归前序遍历输出："<<endl;
    PostOrderTraverse(T,level);
    cout<<end;
    cout<<"递归中序遍历输出为："<<end;
    InOrderTraverse(T,level);
    cout<<endl;
    cout<<"递归后序遍历输出为："<<endl;
    PostOrderTraverse(T,level);
    cout<<endl;
    return 0;
}