2.4. 树基础
2.4.1. 什么是树
定义: n(n>=0)个节点构成的有限集合。子树是不想交的,出个根节点,每个节点有且只有一个父节点。
几个概念
节点的度: 节点的子树个数。
树的度: 树的所有节点中最大的度。
节点的层次: 规定根节点在1层,其他任意节点的层数是其父节点+1。
树的深度: 树中所有节点中最大层次是这棵树的深度。
父节点: 有子树的节点是其子树的根节点的父节点。
子节点: 如果a节点是b节点的父节点,则成b是a节点的子节点。
兄弟节点: 具有同一个父亲节点的各节点是兄弟节点。
2.4.2. 什么是二叉树
度为2的树,可以为空。
一个二叉树,第i层的最大节点树为 pow(2,i-1)。
深度为k的二叉树有最大节点树为pow(2,k)-1。
对任何非空二叉树T,若n0表示叶子节点个数,n1表示一个子节点的个数,n2表示2个子节点的个数,则n0=n2+1。
证明如下:
n表示总边树 = 总结点树 -1 = n0 +n1 +n2 -1
总结点 = 0 *n0 + 1 * n1 + 2 *n2
n0 +n1 +n2 -1 = n1 + 2 * n2
n0=n2+1 。
抽象数据结构描述
类型名称: 二叉树
数据对象集: 一个有穷的节点集合
操作集:
Boolean IsEmpty(BinTree bt): 判断树是否为空。
void Traversal (BinTree bt): 遍历树,按某种顺序访问每个节点。
BinTree CreateBinTree(): 创建一个二叉树。
void PreOrderTraversal(BinTree bt): 先序: 根 左子树 右子树
void InOrderTraversal(BinTree bt): 中序: 左子树 根 右子树
void PosOrderTraversal(BinTree bt): 后序: 左子树 右子树 根
void LevelOrderTraversal(BinTree bt): 先序: 从上到下,从左到右。先第一层遍历完毕,在第二层。每次从左到右。
2.4.3. 二叉树顺序存储实现
完全二叉树: 按照从上到下,从左到右存储。
特点:
非根节点的父节点需要为 [i/2]
节点i的左孩子为2i 如果2i<=n(节点个数) 则表示没有左孩子节点。
节点i的右孩子为2i+1 如果2i+1<=n(节点个数) 则表示没有右孩子节点。
对于一般二叉树,也是可以采用这种方式的, 但是空间浪费是比较严重的。
1
2
3int main(){
4
5}
6
7
2.4.4. 二叉树链式存储实现
1// bitree_link_base.h
2#pragma once
3#include <stdio.h>
4#include <stdlib.h>
5
6#define ElementType int
7typedef struct TreeNode *BsTree ;
8typedef BsTree Position ;
9struct TreeNode{
10 ElementType Data ;
11 BsTree Left;
12 BsTree Right;
13};
1// bitree_link_base.c
2#include <stdio.h>
3#include <stdlib.h>
4#include "stack_link_base_for_tree.c"
5#include "queue_link_base_for_tree.c"
6#include "bitree_link_base.h"
7
8// 判断树是否为空
9int TreeIsEmpty(BsTree bt){
10 if( bt == NULL){
11 return 1 ;
12 }
13 return 0;
14}
15
16// 创建树
17BsTree CreateBsTree(){
18 BsTree bt = (BsTree)malloc(sizeof(struct TreeNode));
19 return bt ;
20}
21
22// 前序递归
23void PreOrderTraversalByRecursive(BsTree bt){
24 if (bt){
25 printf("%d ", bt->Data);
26 PreOrderTraversalByRecursive(bt->Left);
27 PreOrderTraversalByRecursive(bt->Right);
28 }
29}
30
31// 中续递归
32void InOrderTraversalByRecursive(BsTree bt){
33 if (bt){
34 InOrderTraversalByRecursive(bt->Left);
35 printf("%d ", bt->Data);
36 InOrderTraversalByRecursive(bt->Right);
37 }
38}
39
40// 后续递归
41void PosOrderTraversalByRecursive(BsTree bt){
42 if (bt){
43 PosOrderTraversalByRecursive(bt->Left);
44 PosOrderTraversalByRecursive(bt->Right);
45 printf("%d ", bt->Data);
46 }
47}
48
49// 前序迭代
50void PreOrderTraversalByIterate(BsTree bt){
51 Stack s = CreateStack();
52 BsTree t = bt;
53 while( t || !StackIsEmpty(s)){
54 while(t){
55 printf("%d ",t->Data);
56 Push(s, t);
57 t= t->Left;
58 }
59 if (!StackIsEmpty(s)){
60 t= (BsTree) Pop(s);
61 t=t->Right;
62 }
63 }
64}
65
66// 中序迭代
67void InOrderTraversalByIterate(BsTree bt){
68 Stack s = CreateStack();
69 BsTree t = bt;
70 while( t || !StackIsEmpty(s)){
71 while(t){
72 Push(s, t);
73 t= t->Left;
74 }
75 if (!StackIsEmpty(s)){
76 t= (BsTree) Pop(s);
77 printf("%d ",t->Data);
78 t=t->Right;
79 }
80 }
81}
82
83// 后序迭代
84void PostOrderTraversalByIterate(BsTree bt){
85 Stack s = CreateStack();
86 BsTree t = bt;
87 BsTree prev= NULL ;
88 while( t || !StackIsEmpty(s)){
89 while(t){
90 Push(s, t);
91 t= t->Left;
92 }
93 t = (BsTree)Pop(s);
94 if (t->Right == NULL || t->Right == prev){
95 printf("%d ",t->Data);
96 prev = t ;
97 t = NULL;
98
99 }else{
100 Push(s,t);
101 t= t->Right;
102 }
103
104 }
105}
106
107
108// 层次遍历
109void LevelOrderTraversal(BsTree bt){
110
111 Queue q = CreateQueue();
112 BsTree t = bt ;
113 if (bt == NULL){
114 return ;
115 }
116 AddQ(q,t);
117 while(!IsEmptyQ(q)){
118
119 t= DeleteQ(q);
120 printf("%d ",t->Data);
121 if (t->Left){
122 AddQ(q,t->Left);
123 }
124 if (t->Right){
125 AddQ(q,t->Right);
126 }
127
128 }
129
130}
131BsTree CreateDemoTree(){
132 /*
133 1
134 2 3
135 5 4 6
136
137
138 * */
139 BsTree bt1 = CreateBsTree();
140 bt1->Data = 1 ;
141 BsTree bt2 = CreateBsTree();
142 bt2->Data = 2 ;
143 BsTree bt3 = CreateBsTree();
144 bt3->Data = 3 ;
145 BsTree bt4 = CreateBsTree();
146 bt4->Data = 4 ;
147 BsTree bt5 = CreateBsTree();
148 bt5->Data = 5 ;
149 BsTree bt6 = CreateBsTree();
150 bt6->Data = 6 ;
151
152 bt1->Left = bt2 ;
153 bt1->Right =bt3 ;
154
155 bt2->Left = bt5 ;
156 bt2->Right=bt4 ;
157
158 bt3->Left = bt6 ;
159 return bt1 ;
160}
161
162int main(){
163
164 BsTree bt =CreateDemoTree();
165 printf("PreOrderTraversal\n");
166 PreOrderTraversalByRecursive(bt);
167 printf("\n");
168
169 printf("InOrderTraversalByRecursive\n");
170 InOrderTraversalByRecursive(bt);
171 printf("\n");
172
173 printf("PosOrderTraversalByRecursive\n");
174 PosOrderTraversalByRecursive(bt);
175 printf("\n");
176
177
178 printf("PreOrderTraversalByIterate\n");
179 PreOrderTraversalByIterate(bt);
180 printf("\n");
181
182 printf("InOrderTraversalByIterate\n");
183 InOrderTraversalByIterate(bt);
184 printf("\n");
185
186 printf("PostOrderTraversalByIterate\n");
187 PostOrderTraversalByIterate(bt);
188 printf("\n");
189
190 printf("LevelOrderTraversal\n");
191 LevelOrderTraversal(bt);
192 printf("\n");
193}