数学建模社区-数学中国
标题:
【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
[打印本页]
作者:
杨利霞
时间:
2022-9-15 11:55
标题:
【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
' i6 V5 X( S! g. o/ m T
7 u A# j2 g, @ w6 u/ U4 q: H; [
[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
4 C. u7 v' y3 p6 l- R# X% q
[color=rgba(0, 0, 0, 0.749019607843137)]前言
) H/ ]) W" M. G7 ]
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
Y p* }% K4 Z' l) L8 N
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
4 z$ d4 {# c/ V( v0 x) G6 G
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
- @- @( G @9 _5 E
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
" ?- E+ N h4 d4 t9 ]3 U# t
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
" }1 x7 ?( S# w* [) S5 Q
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
3 f& N! v! y$ [. U
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
9 b% `" K4 f; ^
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
- E9 x' \* n4 A: H$ _5 V$ i$ l; A
[color=rgba(0, 0, 0, 0.749019607843137)]前言
! f( x& @0 @, l
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
$ d' I1 i9 m! O. U, S
[color=rgba(0, 0, 0, 0.749019607843137)]
/ ~1 ^) x0 Z, L$ N% g0 w3 w1 |
4 |- K: O E+ ?+ Q* `$ e d H) S
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
* E. \% j( h$ i8 |& j# c" K
[color=rgba(0, 0, 0, 0.749019607843137)]
. \$ J' ~/ G. y4 |$ q
9 B% b; U9 j9 j t- M9 w
[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：
+ w2 t# s' Z1 c& T1 \
[color=rgba(0, 0, 0, 0.749019607843137)]
0 c5 ~. Q2 k. Z7 I, B) U
) k- f l& l; e
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树
1 i; Y4 Q1 B5 t* d7 T+ j0 D
[color=rgba(0, 0, 0, 0.749019607843137)]
0 y6 v1 D4 _% \; z& {$ M8 E4 ]
* c& E- d# l/ H6 x/ a1 e
[color=rgba(0, 0, 0, 0.749019607843137)]
! ~6 p& o4 A. `
0 ?# i% b1 ]7 X. o% S" S
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树
! r$ W" M9 ?/ S0 N
[color=rgba(0, 0, 0, 0.749019607843137)]
5 H) H1 k$ a/ i% Q a \
# i& t( C! I$ z0 T
[color=rgba(0, 0, 0, 0.749019607843137)]
$ J# ^9 a4 r9 T. N0 q8 e+ S
! U) c$ y, ^+ _* w: F' e* `, ?$ g
[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根
3 r& t, K [- ?8 ?8 K
[color=rgba(0, 0, 0, 0.749019607843137)]
5 U- C* q9 L! z4 r9 p
. V/ \9 Z! K! _0 F3 Q
[color=rgba(0, 0, 0, 0.749019607843137)]
) |. q% }9 E& Z- c
+ v. C: D* j T1 ^; }" T
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
; `9 X7 g+ V+ n3 ~
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
?" o) T& Z' O! M s
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
: u) s- O4 Y7 l+ |5 ?; a4 ~ I
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
2 \1 _) t. ~ |8 _* L
[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
9 ~/ e3 X7 m* e0 i& J: h- Y
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；
0 ~- g+ }) s! i/ {
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
4 T0 F# W; R; @ L6 k) I3 x+ z
[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
: o1 K, u, J- V- D
[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
4 N, e* C+ J M
[color=rgba(0, 0, 0, 0.749019607843137)]
1 r& M, }7 J& U e
& ~# ^+ k) a# P2 v
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
0 ?6 @" i: X- \" L8 }
[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1
) v% E0 t* g j! G q( G8 s
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
) j) ?; z j8 D) Y' ]
[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
. L3 ?" J* Y2 ^2 T
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
# R1 P; i& \& P1 Z, J x
[color=rgba(0, 0, 0, 0.749019607843137)]
! ?/ T& f2 N, F
$ n& p: p8 @' w/ }% ?
[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;
& s4 `+ i/ t: u: E a+ b* |: V3 W
[color=rgba(0, 0, 0, 0.749019607843137)]
& [/ `; I: C- W* q
- v4 v, e2 r& a; C) R. @# [+ Z
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
* f3 V7 S5 [- g$ f
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
" r& K7 I6 I5 U# N
[color=rgba(0, 0, 0, 0.749019607843137)]{
% ~3 f5 d0 b- L& R7 w# m
[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;
1 N/ O+ q1 Y* V
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;
T# x: D$ ~( Y& z
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
" w/ `. R. l. I" C5 }' G7 d
[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;
9 P2 V) W! K* V K
[color=rgba(0, 0, 0, 0.749019607843137)]
( t7 c* j- n, K4 G+ s% y2 Z
) F7 }' {# x9 @$ l" i8 O$ i. v4 T6 A
[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
: o( c% Y% a. ?5 a
[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
f$ y: M$ Y* W, i
[color=rgba(0, 0, 0, 0.749019607843137)]{
$ ?0 c& P* t; r" i1 O- [9 [
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
- f0 Z4 M9 Q; X3 R8 }% a" o
[color=rgba(0, 0, 0, 0.749019607843137)] {
) _ {% c1 C% w. Z Y
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
- z1 `8 U( I/ [( |6 _
[color=rgba(0, 0, 0, 0.749019607843137)] return;
6 S4 z f) Q# W; e/ U$ d8 Y: X
[color=rgba(0, 0, 0, 0.749019607843137)] }
+ s3 F* t+ J) w! Q& V/ g2 h
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
/ F7 J, V( D' Z$ A4 W. X
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);
# w( A! d6 _* Y6 b* z8 l" Q- S
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);
! Z: t/ n. f7 J2 i9 Z
[color=rgba(0, 0, 0, 0.749019607843137)]}
# R0 a3 q. T) n' ^) }
[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
6 R9 v3 b& I/ |5 }, _
[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
# U$ F6 V1 d2 j0 p+ S: q; H$ g
[color=rgba(0, 0, 0, 0.749019607843137)]{
t: h0 A1 [7 `( U" z8 l. c7 n5 _ y
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
) J# \8 v5 L R8 y w+ h
[color=rgba(0, 0, 0, 0.749019607843137)] {
4 {' j) }' B( E2 F5 V- h& z' e7 w
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
6 M. P' Y0 @! m! v+ u8 z
[color=rgba(0, 0, 0, 0.749019607843137)] return;
& j) o2 w; ~' k
[color=rgba(0, 0, 0, 0.749019607843137)] }
$ p# C8 x! h0 F( k5 W( ] Y/ ]' f6 ]
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);
9 R" G0 g) c# k; \5 X" ]
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
; W+ ^3 B7 a- k8 U" X6 Z) f
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);
+ }2 l. F! t+ h/ b% x p* G+ [
[color=rgba(0, 0, 0, 0.749019607843137)]}
. S3 y( {# w! I: M% z: X
[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
; ] {! g* ]( f. u/ g
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)
. y0 p K' i8 I. d! u
[color=rgba(0, 0, 0, 0.749019607843137)]{
, c* m: K; h1 t' K K6 ^
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
( \" A8 \2 }4 E8 u/ W: H3 J
[color=rgba(0, 0, 0, 0.749019607843137)] {
% \ J2 {8 R# k3 K/ P8 Y/ I! g
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
0 K ^; S; o) `5 p
[color=rgba(0, 0, 0, 0.749019607843137)] return;
. G* z5 {0 b1 X0 M1 M+ P8 E
[color=rgba(0, 0, 0, 0.749019607843137)] }
: m, `& M; s/ x- y$ a8 l7 B. k
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);
; Q; s+ p) Z+ e
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
% w# e2 V6 ?/ C1 S5 P% F; F
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
4 p, t% P7 m' s; z; p/ A
[color=rgba(0, 0, 0, 0.749019607843137)]}
" D) M# F1 m9 u: ^, W
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构
- i3 Y# `. B4 F% c
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()
/ Q+ g$ }+ y1 R/ G3 |- l
[color=rgba(0, 0, 0, 0.749019607843137)]{
w: }: }; t7 `+ q" d z. m
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间
" m( U3 [7 M4 F c& Y
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
$ P5 `) ]; C N) ^2 J
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
1 s+ }' M3 J) Z& }& ]6 [ i& N
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
% i/ N+ D( p, \2 l6 i* M
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);
0 h0 o" f4 S7 ?, O. n
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
% t- s) q7 R, l2 L( D- [
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);
5 Y, {% L" y: W
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
' c5 c i6 y8 i9 \5 E% m4 q
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);
9 F9 Q+ J' G( o" s* {* \9 |/ t
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
* _7 y$ V& T$ Q% z2 X
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);
% ?/ Q- A1 { \' W" h4 R
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
/ ]) v0 z. Y8 `3 O! \$ N9 s. d! L
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);
L' }7 N& p( W# m
[color=rgba(0, 0, 0, 0.749019607843137)]
! J' r* {. `2 t5 _
5 @; b% ?" N* ~+ g
[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;
8 k g" r6 V7 h# l: |$ S/ M( @
[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;
! l# v! p5 L/ j4 W8 J1 j" E
[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;
, ~8 i! P0 l) X1 q! ~
[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;
* f3 O7 @1 k: i0 ^
[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;
) s# S( x! v: B" a
[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
1 N: r6 J7 i* p" ?( ~
[color=rgba(0, 0, 0, 0.749019607843137)]
6 y6 J( z; |1 }: J* d, z* n* T
5 @, H) A1 W- A1 T, p- I
[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;
; `/ I5 F2 E% N' b: a3 z0 j- e, C
[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;
! S$ r; f9 e! J! H
[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;
! h8 q* }8 K$ F
[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
0 f6 _. D' |$ ^0 N
[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;
* ]* W& r. h4 s9 C+ x
[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;
, c( F& G8 P. q: |# H( a! q
[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;
( C3 G' r( }* {: Q* w/ w8 B7 [* l
[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;
L. @, K5 s9 o% `) O2 w' L: p! O
[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;
E/ }* ?1 F, ]: O3 T& @( C0 J! j
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;
1 G+ P4 d/ e% B! `8 l
[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;
; [/ ?& ]$ S! N$ V
[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;
. S/ u4 M6 M5 Z/ h
[color=rgba(0, 0, 0, 0.749019607843137)]
? t; P& X8 r* y( h
, v: ^) m% c) |( d4 _
[color=rgba(0, 0, 0, 0.749019607843137)] return n1;
5 `; I2 p" `* f
[color=rgba(0, 0, 0, 0.749019607843137)]}
5 {% A2 B" h. s+ c1 T8 J8 Q: h
[color=rgba(0, 0, 0, 0.749019607843137)]
7 n' h4 L$ m+ s+ K9 v, m3 E" J. N
" q5 X, D I: h, \. M
[color=rgba(0, 0, 0, 0.749019607843137)]int main()
! W' J! i- w& ]
[color=rgba(0, 0, 0, 0.749019607843137)]{
# ?2 `, W+ V$ [2 j1 w
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构
! `# E7 Z( r* s' ]! J$ R5 Z
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();
* }! I* t, Q0 X$ h& W# P
[color=rgba(0, 0, 0, 0.749019607843137)]
$ s8 h' v& i7 ^) ?
8 X) z4 M+ x3 V6 [- I7 I
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历
. S9 w8 V/ B$ C# }5 Z
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");
: r1 E% f( c6 j, }
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);
: c: J5 g O8 W0 ~ ^0 A) b2 v
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
! d# l0 E! n( h) o- W- P: o0 A
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历
6 s, G ^. W6 H8 S; S- q5 A# S
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");
1 }# r- z8 F4 o" r& O
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);
, _* j7 _2 ?- @+ s) l" B
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
2 [6 R, ~" f5 i4 p3 Z
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历
0 p' ]9 _) J# j( \3 S
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");
1 d$ j3 O. B/ ^3 k2 p
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
7 e( e0 X7 k0 [ E
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
8 l- o5 m" B" D" e. H: B9 z
[color=rgba(0, 0, 0, 0.749019607843137)]
3 Z' P$ a v% f. O7 L6 t& J' l
4 n6 ~1 m0 Q0 L0 Y
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
% k1 @% q+ ]# A' z9 C% Z! t: W3 O
[color=rgba(0, 0, 0, 0.749019607843137)]}
/ L- g$ z7 \, ?. R
[color=rgba(0, 0, 0, 0.749019607843137)]1
3 E+ A' {8 C1 A! ]+ z# g
[color=rgba(0, 0, 0, 0.749019607843137)]2
' b7 K- O; v4 f. E: I) X# A
[color=rgba(0, 0, 0, 0.749019607843137)]3
9 {$ P% L$ j u* }5 K4 N# X' B
[color=rgba(0, 0, 0, 0.749019607843137)]4
6 x, \" Q C, y- r
[color=rgba(0, 0, 0, 0.749019607843137)]5
B* T K$ ?# l7 ~# E* ]$ L
[color=rgba(0, 0, 0, 0.749019607843137)]6
* C6 r. g+ l$ R' h7 K0 {( w) s
[color=rgba(0, 0, 0, 0.749019607843137)]7
8 s5 y7 \6 E& r2 \, e
[color=rgba(0, 0, 0, 0.749019607843137)]8
" o2 g& j( T) a1 {& \& W3 f
[color=rgba(0, 0, 0, 0.749019607843137)]9
5 Y6 b9 n% u- b
[color=rgba(0, 0, 0, 0.749019607843137)]10
- h5 N+ X) z- U/ V/ k6 V- v* q5 f
[color=rgba(0, 0, 0, 0.749019607843137)]11
! E% E, W7 b2 S0 Q
[color=rgba(0, 0, 0, 0.749019607843137)]12
8 Y. }3 }: H: l8 ~+ ?* q3 g
[color=rgba(0, 0, 0, 0.749019607843137)]13
4 w; p# b7 D# O+ c
[color=rgba(0, 0, 0, 0.749019607843137)]14
* r9 x9 U' g: u7 a7 P- N
[color=rgba(0, 0, 0, 0.749019607843137)]15
# B6 @5 { P! H( q" L
[color=rgba(0, 0, 0, 0.749019607843137)]16
6 `( I) A3 I' [1 O. l3 y
[color=rgba(0, 0, 0, 0.749019607843137)]17
- H$ R' p5 A, h' _& w
[color=rgba(0, 0, 0, 0.749019607843137)]18
- K2 t% z( g, c* f
[color=rgba(0, 0, 0, 0.749019607843137)]19
7 J4 |. Z t9 p) X0 i
[color=rgba(0, 0, 0, 0.749019607843137)]20
! ^: D' U2 @/ O! b0 d8 u
[color=rgba(0, 0, 0, 0.749019607843137)]21
Q! E$ O7 [ `$ A2 E3 j
[color=rgba(0, 0, 0, 0.749019607843137)]22
: h7 ?" Q. z/ }( Q
[color=rgba(0, 0, 0, 0.749019607843137)]23
/ v: S$ K: E+ g6 o$ d* |
[color=rgba(0, 0, 0, 0.749019607843137)]24
! A$ b: t: [$ r/ f0 _0 ~5 [, a8 b
[color=rgba(0, 0, 0, 0.749019607843137)]25
, n: B: K$ R# f. G
[color=rgba(0, 0, 0, 0.749019607843137)]26
8 j& j4 b; Y" k
[color=rgba(0, 0, 0, 0.749019607843137)]27
) X* Y7 k: m+ m
[color=rgba(0, 0, 0, 0.749019607843137)]28
3 F: O7 y. p3 a) [
[color=rgba(0, 0, 0, 0.749019607843137)]29
: n5 c, g4 B1 t$ h4 e2 {& G
[color=rgba(0, 0, 0, 0.749019607843137)]30
A# D/ X* T2 E3 o1 C/ E- J
[color=rgba(0, 0, 0, 0.749019607843137)]31
& P- y$ s$ e+ v J
[color=rgba(0, 0, 0, 0.749019607843137)]32
) I' @1 F5 N' ~. q( | n: e
[color=rgba(0, 0, 0, 0.749019607843137)]33
3 I- K( O& ~! J& A0 [+ J: }
[color=rgba(0, 0, 0, 0.749019607843137)]34
2 L7 f: B0 d/ h# N$ P' o, I
[color=rgba(0, 0, 0, 0.749019607843137)]35
+ d3 ^, }8 s z9 B0 W0 U
[color=rgba(0, 0, 0, 0.749019607843137)]36
% B8 ~; F5 { }& L
[color=rgba(0, 0, 0, 0.749019607843137)]37
2 w9 r4 H Y" Z% d; X& a H. T; s
[color=rgba(0, 0, 0, 0.749019607843137)]38
; p, u8 @; d4 r% O2 d
[color=rgba(0, 0, 0, 0.749019607843137)]39
; \/ i( n' [" a
[color=rgba(0, 0, 0, 0.749019607843137)]40
$ X, H' f% Y7 A. |* t$ \
[color=rgba(0, 0, 0, 0.749019607843137)]41
- o5 Z( O7 N0 h! ]; ?
[color=rgba(0, 0, 0, 0.749019607843137)]42
3 s8 J3 {( P2 A
[color=rgba(0, 0, 0, 0.749019607843137)]43
& E J6 ]0 y" ^ O! N& Y" ?) e
[color=rgba(0, 0, 0, 0.749019607843137)]44
3 U! Q8 A4 D3 z }( @
[color=rgba(0, 0, 0, 0.749019607843137)]45
; }( _3 D9 J8 x8 \; L6 u' w+ `0 G/ M
[color=rgba(0, 0, 0, 0.749019607843137)]46
& B* p. t% m3 ~* ?, N
[color=rgba(0, 0, 0, 0.749019607843137)]47
- O, K* o% h& F$ R5 H
[color=rgba(0, 0, 0, 0.749019607843137)]48
% ` f6 l {; x
[color=rgba(0, 0, 0, 0.749019607843137)]49
# O. n$ m4 l: S+ H2 T9 ?
[color=rgba(0, 0, 0, 0.749019607843137)]50
9 H$ Q3 s; f, n7 T/ J& d( s
[color=rgba(0, 0, 0, 0.749019607843137)]51
0 H7 e8 C; |& H# k1 z: n3 l
[color=rgba(0, 0, 0, 0.749019607843137)]52
) ]6 o% f1 D2 S3 c9 R' z
[color=rgba(0, 0, 0, 0.749019607843137)]53
, B- j f$ C% ? u
[color=rgba(0, 0, 0, 0.749019607843137)]54
, }$ q& ]$ G3 L4 x( i' E
[color=rgba(0, 0, 0, 0.749019607843137)]55
2 j M6 O p' a* B1 @: R
[color=rgba(0, 0, 0, 0.749019607843137)]56
! J$ U8 Z7 W9 ^1 `
[color=rgba(0, 0, 0, 0.749019607843137)]57
$ E( g, z% Z8 ?( x
[color=rgba(0, 0, 0, 0.749019607843137)]58
: g- U5 ]) d2 J5 K- \
[color=rgba(0, 0, 0, 0.749019607843137)]59
! R8 @; |) b) R/ e
[color=rgba(0, 0, 0, 0.749019607843137)]60
! m/ k& v" A0 b! b+ E
[color=rgba(0, 0, 0, 0.749019607843137)]61
S, V0 [; y; n: }) N
[color=rgba(0, 0, 0, 0.749019607843137)]62
/ U+ U, Z: N. l, c6 x
[color=rgba(0, 0, 0, 0.749019607843137)]63
9 U& b: G! q% `7 |
[color=rgba(0, 0, 0, 0.749019607843137)]64
: Y \3 y( o! S( _0 w3 W
[color=rgba(0, 0, 0, 0.749019607843137)]65
! F2 z# l. x5 X# I5 z/ f
[color=rgba(0, 0, 0, 0.749019607843137)]66
: o7 H8 I1 h( G; L @
[color=rgba(0, 0, 0, 0.749019607843137)]67
4 P6 w$ M0 x6 G# B* u, a( e. ?
[color=rgba(0, 0, 0, 0.749019607843137)]68
8 V b" X( n" z( D7 p6 E! Y5 l
[color=rgba(0, 0, 0, 0.749019607843137)]69
+ W: ~% }4 m1 c: `
[color=rgba(0, 0, 0, 0.749019607843137)]70
) }- l$ n$ g, V. {7 L- C
[color=rgba(0, 0, 0, 0.749019607843137)]71
8 g$ g& h3 U% W, T3 ]3 g, x7 q' e
[color=rgba(0, 0, 0, 0.749019607843137)]72
) _) H1 l0 O4 x0 |0 M$ X* d1 s
[color=rgba(0, 0, 0, 0.749019607843137)]73
2 s% |( f+ l( ^, ~) F2 N
[color=rgba(0, 0, 0, 0.749019607843137)]74
& n8 N9 z3 S9 w# ~" j
[color=rgba(0, 0, 0, 0.749019607843137)]75
) @, Y, F4 W; Y6 q' ^5 R0 z
[color=rgba(0, 0, 0, 0.749019607843137)]76
& o% ]% P! d1 J" @; H7 q2 X* D. e
[color=rgba(0, 0, 0, 0.749019607843137)]77
4 Q4 p& e3 f6 W* n- y7 B% Q
[color=rgba(0, 0, 0, 0.749019607843137)]78
1 V7 p( d9 O4 X6 `
[color=rgba(0, 0, 0, 0.749019607843137)]79
- P! I# O; }' b4 l1 o o7 u
[color=rgba(0, 0, 0, 0.749019607843137)]80
1 w) N0 B+ V- u) h3 O. |& {
[color=rgba(0, 0, 0, 0.749019607843137)]81
7 W/ |* L9 z8 J# k: P7 T% P
[color=rgba(0, 0, 0, 0.749019607843137)]82
% q, `4 }( m& H1 B" {- F
[color=rgba(0, 0, 0, 0.749019607843137)]83
" q6 b4 D* u! j
[color=rgba(0, 0, 0, 0.749019607843137)]84
$ @, c1 J, I3 O* o9 |$ D
[color=rgba(0, 0, 0, 0.749019607843137)]85
0 S0 g! o6 q# F" ]+ d6 y
[color=rgba(0, 0, 0, 0.749019607843137)]86
( G1 _( k) @4 U3 x) v& O& j4 R
[color=rgba(0, 0, 0, 0.749019607843137)]87
" |1 T6 A( J7 k3 n
[color=rgba(0, 0, 0, 0.749019607843137)]88
0 w2 ?8 q( B$ E. Q
[color=rgba(0, 0, 0, 0.749019607843137)]89
5 t0 K9 z) d" Z1 B
[color=rgba(0, 0, 0, 0.749019607843137)]90
& y3 B. Y, N" F' p6 u
[color=rgba(0, 0, 0, 0.749019607843137)]91
5 }3 P( U9 V5 j0 p
[color=rgba(0, 0, 0, 0.749019607843137)]92
- j) o* X1 c8 ?! z% P B% ^$ y
[color=rgba(0, 0, 0, 0.749019607843137)]93
$ a" t( n2 z/ m1 ^
[color=rgba(0, 0, 0, 0.749019607843137)]94
; Z2 i+ A1 [ v2 ~: l' {
[color=rgba(0, 0, 0, 0.749019607843137)]95
5 w. A- Y8 u: |' w8 g; H
[color=rgba(0, 0, 0, 0.749019607843137)]96
9 ?( e. t' D( ` q1 s
[color=rgba(0, 0, 0, 0.749019607843137)]97
! `+ w" A6 l" y l( v
[color=rgba(0, 0, 0, 0.749019607843137)]98
- c& ? o8 I. h" ?, E3 }2 k& v
[color=rgba(0, 0, 0, 0.749019607843137)]99
5 \5 r( L1 C2 f8 X" S
[color=rgba(0, 0, 0, 0.749019607843137)]100
7 V# E' X! E. {# _: P
[color=rgba(0, 0, 0, 0.749019607843137)]101
( l$ I [! \/ k4 F5 W
[color=rgba(0, 0, 0, 0.749019607843137)]102
- r* z6 a$ ~1 J
[color=rgba(0, 0, 0, 0.749019607843137)]103
/ c' Z7 c, _5 u- n. i3 b
[color=rgba(0, 0, 0, 0.749019607843137)]104
! M! ]5 Q X% v
[color=rgba(0, 0, 0, 0.749019607843137)]105
" ]- @7 L2 `/ M2 N9 o8 Q: M
[color=rgba(0, 0, 0, 0.749019607843137)]106
. ^6 ] W. ^/ Q3 ^- N# b
[color=rgba(0, 0, 0, 0.749019607843137)]107
, y) |8 L* T# p$ U: L; S8 b
[color=rgba(0, 0, 0, 0.749019607843137)]108
0 {+ p3 x* ^: n0 }) C" \2 ~" x, j
[color=rgba(0, 0, 0, 0.749019607843137)]109
. G5 n1 A5 g3 y
[color=rgba(0, 0, 0, 0.749019607843137)]110
, y% \% Y4 S/ q+ A
[color=rgba(0, 0, 0, 0.749019607843137)]111
- D0 y" o$ s2 y& e" r2 H. R3 M7 p
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
9 h7 J0 J' R( C; v
[color=rgba(0, 0, 0, 0.749019607843137)]
. Q2 ?4 A0 s4 f0 V
( u4 }7 \" o: m6 V; l: D* B
[color=rgba(0, 0, 0, 0.749019607843137)]
1 t$ [0 {$ p3 Z) w* W
+ i- C" j8 v( M7 H. g: p3 j
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
/ u0 M5 b. b' Y9 |% `* m" ?
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
- v4 f1 X' j% b M
[color=rgba(0, 0, 0, 0.749019607843137)]
) c: d. W: ^2 `% Z: y3 i& P
1 b) B! g' z- D+ a( R8 k
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
, A7 L! r9 X. m6 G, z# h
[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
* L! d) I8 M2 w# F" {) U
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
' u- C2 W6 ]( k
[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
0 N5 A6 g( X/ z; v8 N
[color=rgba(0, 0, 0, 0.749019607843137)]//{
! |) H" i' ^% W) M" H1 B- g0 Z
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
+ d; y, E# S0 b: p
[color=rgba(0, 0, 0, 0.749019607843137)]// {
/ ^+ z8 H+ d& D9 u( u# C+ @
[color=rgba(0, 0, 0, 0.749019607843137)]// return;
; Q, e) i3 a2 U6 A* R# s3 V
[color=rgba(0, 0, 0, 0.749019607843137)]// }
0 k8 n+ ~1 L6 t, D$ J
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;
" i, k: L% W/ b6 m c
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);
) T) n/ d' M% c; I4 C5 B5 z
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);
% x$ s6 n3 ~% R) {$ f8 _, E+ s1 V
[color=rgba(0, 0, 0, 0.749019607843137)]//
+ C3 I: I1 a, {8 L0 k7 N7 F. _ ?7 ~
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量
$ u3 L: Z+ A# y! _& n/ w8 I
[color=rgba(0, 0, 0, 0.749019607843137)]//}
, f& o9 \4 c, W7 {
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之
5 Y/ {2 o0 [0 y1 P! |9 w7 r) w
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)
$ h6 m, H" N7 J1 G
[color=rgba(0, 0, 0, 0.749019607843137)]{
+ V/ d9 V4 F- d9 i( v) X
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
$ N. [0 ^9 `% ?2 }' J+ Z2 \
[color=rgba(0, 0, 0, 0.749019607843137)]}
+ V. B: P- g5 ?" K Y0 `7 \
[color=rgba(0, 0, 0, 0.749019607843137)]1
- G7 I4 u z0 U6 j+ t- M
[color=rgba(0, 0, 0, 0.749019607843137)]2
. E- K& _7 f) C. C" r, v/ y' d
[color=rgba(0, 0, 0, 0.749019607843137)]3
; n/ C8 S7 j8 \3 l/ x9 y. o
[color=rgba(0, 0, 0, 0.749019607843137)]4
! F0 S$ \9 G+ Y
[color=rgba(0, 0, 0, 0.749019607843137)]5
/ o* E7 t) Z4 x1 p7 S
[color=rgba(0, 0, 0, 0.749019607843137)]6
! p8 ] K. l3 o2 k/ S1 ~
[color=rgba(0, 0, 0, 0.749019607843137)]7
( ]1 t* ~ C1 F9 u5 E1 T
[color=rgba(0, 0, 0, 0.749019607843137)]8
% @( l! V% y9 [4 o& m
[color=rgba(0, 0, 0, 0.749019607843137)]9
* r" B0 z8 ~; t9 n/ a
[color=rgba(0, 0, 0, 0.749019607843137)]10
0 x0 r+ C2 d3 x4 q. k k
[color=rgba(0, 0, 0, 0.749019607843137)]11
$ { ^& }, e% v/ u4 r% _$ e
[color=rgba(0, 0, 0, 0.749019607843137)]12
9 l& ~1 X( [7 D4 i# R I$ }
[color=rgba(0, 0, 0, 0.749019607843137)]13
& J" _- ^* ^$ v
[color=rgba(0, 0, 0, 0.749019607843137)]14
& w" |& O( K( d% {% R
[color=rgba(0, 0, 0, 0.749019607843137)]15
/ _: z y7 G9 |: o8 l- S
[color=rgba(0, 0, 0, 0.749019607843137)]16
" o& S' J1 d( b k# U2 }7 g
[color=rgba(0, 0, 0, 0.749019607843137)]17
' _7 J6 S! D$ u' z9 v
[color=rgba(0, 0, 0, 0.749019607843137)]18
: O3 `/ Y b4 Y
[color=rgba(0, 0, 0, 0.749019607843137)]19
c' A9 f5 q/ s+ E. m
[color=rgba(0, 0, 0, 0.749019607843137)]20
. ^8 q7 ~$ \9 K. A8 M6 m5 n
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
6 ^; P" v% K( K% t+ L
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数
0 E( d! s. y! J W- f6 }- v
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
- w$ p1 z. r/ g! p! {( j9 u$ Q% W# U( |
[color=rgba(0, 0, 0, 0.749019607843137)]{
7 F. u: J# c4 `$ k4 g5 t9 V8 j
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点
. o+ R' \' u7 r/ z u: ^4 d$ _3 p
[color=rgba(0, 0, 0, 0.749019607843137)] {
; @$ c: W6 P3 C& P6 ?/ [
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
9 a1 @! N0 ]' A1 X
[color=rgba(0, 0, 0, 0.749019607843137)] }
" R& b( x; w# V* _$ q
[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空
+ n% p& `) S& I1 `" U
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)
0 L# X! V) `' [' v6 S, e
[color=rgba(0, 0, 0, 0.749019607843137)] {
7 Q- Q5 D6 q! }2 Z: N7 D* T
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
, g. I+ P$ e8 u# T# F
[color=rgba(0, 0, 0, 0.749019607843137)] }
{$ @# |6 q. E' ~+ @
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
. v* x) @* F% a; A
[color=rgba(0, 0, 0, 0.749019607843137)]}
- {3 t! j. S4 _
[color=rgba(0, 0, 0, 0.749019607843137)]1
A' i! S" C$ i( M) V% s7 E
[color=rgba(0, 0, 0, 0.749019607843137)]2
, h# `! Z O# A& W, w6 L3 w7 f& Z
[color=rgba(0, 0, 0, 0.749019607843137)]3
2 F! v( @" ?4 w1 k, o
[color=rgba(0, 0, 0, 0.749019607843137)]4
0 r2 {- \& n9 {, F' m0 `# d
[color=rgba(0, 0, 0, 0.749019607843137)]5
& M+ D1 p- |- t) C! X
[color=rgba(0, 0, 0, 0.749019607843137)]6
- E7 t, k0 O1 a' W8 r9 H
[color=rgba(0, 0, 0, 0.749019607843137)]7
+ X( F) C, O% I; {) S! _) b* \
[color=rgba(0, 0, 0, 0.749019607843137)]8
5 w X2 f7 t- x2 B
[color=rgba(0, 0, 0, 0.749019607843137)]9
0 p- o* T- N& ]0 y: T8 V: J% i
[color=rgba(0, 0, 0, 0.749019607843137)]10
- p( X7 i* y9 x5 x
[color=rgba(0, 0, 0, 0.749019607843137)]11
4 P/ K6 ]+ ` ]1 x: y% k4 }
[color=rgba(0, 0, 0, 0.749019607843137)]12
( l3 ~3 x* {+ B/ {6 k
[color=rgba(0, 0, 0, 0.749019607843137)]13
9 _1 q. P( k: V& x1 _/ a2 I
[color=rgba(0, 0, 0, 0.749019607843137)]14
/ p+ N9 R9 e6 A
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
8 S$ l2 o6 N! ^1 k5 P e; `4 o6 x
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
) o# e3 i* E* d& W' B% |6 n) t
[color=rgba(0, 0, 0, 0.749019607843137)]{
, N7 V5 ]+ s, w; J ?3 ]2 {, s
[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0
9 X. N' v2 M2 o0 Q1 k% I0 Y0 o
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
# l9 T+ p8 v2 C2 Z) ]- B8 o
[color=rgba(0, 0, 0, 0.749019607843137)] {
( y) _( m) A# m3 y
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
0 h; L' D6 _- W+ `2 d8 ?
[color=rgba(0, 0, 0, 0.749019607843137)] }
# t1 U# L! W5 v; b E( t
[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树
, T0 h1 b+ Y; g& W; ]4 o8 K) {
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度
8 N% [' {, E* Z; F' ~
[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度
0 [$ ~ p: d8 j, r' t' L/ b
[color=rgba(0, 0, 0, 0.749019607843137)]
2 s X g0 g) P9 @
: B6 [6 ?1 N9 _1 f. K3 R1 i5 O/ h
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;
: J8 G& `& j6 T. f* H4 w- d5 y
[color=rgba(0, 0, 0, 0.749019607843137)]}
9 `0 o4 A; g! L* l4 @7 h
[color=rgba(0, 0, 0, 0.749019607843137)]1
7 n; n8 c9 y9 l1 `0 C0 Z
[color=rgba(0, 0, 0, 0.749019607843137)]2
" R! v$ r" w5 A2 J; X
[color=rgba(0, 0, 0, 0.749019607843137)]3
. g8 j2 k1 f4 u. v- ?
[color=rgba(0, 0, 0, 0.749019607843137)]4
* Q: e; ^' G. K a8 L
[color=rgba(0, 0, 0, 0.749019607843137)]5
; R; p, X! `& x! p3 ~
[color=rgba(0, 0, 0, 0.749019607843137)]6
6 d' N. X8 }8 S! ]1 K! g# c
[color=rgba(0, 0, 0, 0.749019607843137)]7
! X/ J" w/ A# p3 F
[color=rgba(0, 0, 0, 0.749019607843137)]8
) l5 m, _0 r/ r: s
[color=rgba(0, 0, 0, 0.749019607843137)]9
# E+ p# x, ^# X& X7 W
[color=rgba(0, 0, 0, 0.749019607843137)]10
" v ^$ G5 m' }* x/ [
[color=rgba(0, 0, 0, 0.749019607843137)]11
" z0 l5 u; i/ j
[color=rgba(0, 0, 0, 0.749019607843137)]12
) z) h: N- g1 g" {9 k% Z
[color=rgba(0, 0, 0, 0.749019607843137)]13
, H" D9 n2 ~7 `' @+ Q3 Z
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
) o1 o% B$ I$ V/ q# @
[color=rgba(0, 0, 0, 0.749019607843137)]
& Y3 ^& b( f7 V
+ F* `4 W6 ]4 n6 L) I
[color=rgba(0, 0, 0, 0.749019607843137)]
8 ]! u% i+ Z# |* A
' ^' @$ O; m3 W2 a; O' W5 R
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
3 H3 V/ c9 L6 Q: @7 y& {, r3 r% e
[color=rgba(0, 0, 0, 0.749019607843137)]
7 H5 r+ ~. y) X$ A
$ x3 J6 Z' X4 i' T6 Q
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
& N* V( p: G8 X# n3 H5 Z0 U
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
: A% s1 H" H4 V8 O
[color=rgba(0, 0, 0, 0.749019607843137)]{
+ A5 H+ h0 ?' H, M' ?
[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);
) d* l i/ s* R+ h+ d& D
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
/ y& w; C }) m9 O6 u& R0 K7 W& u" G
[color=rgba(0, 0, 0, 0.749019607843137)] {
% p& N9 c" ?, v- V, J- f: }
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
8 u, ?5 |- B2 b% G9 w# q# ~
[color=rgba(0, 0, 0, 0.749019607843137)] }
& B( W% S7 @( o( a* S9 S9 l4 h
[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
+ c' ?& c3 W) `
[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1)
& z7 y4 n. l- @* ?7 v
[color=rgba(0, 0, 0, 0.749019607843137)] {
5 I" A& R& ?' Q6 a( G, h
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
7 S7 C1 T( q7 V# C$ B2 d
[color=rgba(0, 0, 0, 0.749019607843137)] }
( @2 n4 {' t, ]
[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层
0 P; Z: A D/ P5 n1 h' _
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
' m% b1 B& g1 o/ e2 n: Z
[color=rgba(0, 0, 0, 0.749019607843137)]}
+ R0 \# i6 o1 R; z! B
[color=rgba(0, 0, 0, 0.749019607843137)]1
) ~* N- |" k/ o& R+ H
[color=rgba(0, 0, 0, 0.749019607843137)]2
% F/ v' j# l! A6 x/ a9 w E
[color=rgba(0, 0, 0, 0.749019607843137)]3
" y% Y; ^( u- |: N n
[color=rgba(0, 0, 0, 0.749019607843137)]4
2 H: w. E: N7 z/ K* g
[color=rgba(0, 0, 0, 0.749019607843137)]5
7 p4 r5 \+ G3 a' o/ D0 N
[color=rgba(0, 0, 0, 0.749019607843137)]6
: y; C: x) ]; _2 \6 X, j& s
[color=rgba(0, 0, 0, 0.749019607843137)]7
/ [$ \ d: |0 T# |0 j
[color=rgba(0, 0, 0, 0.749019607843137)]8
9 p: } J+ g' S! |, ]- F
[color=rgba(0, 0, 0, 0.749019607843137)]9
( V! j/ p1 X; g7 C( D7 i! e
[color=rgba(0, 0, 0, 0.749019607843137)]10
1 Q( b3 K5 f: [
[color=rgba(0, 0, 0, 0.749019607843137)]11
0 h* E9 R% c5 O- F
[color=rgba(0, 0, 0, 0.749019607843137)]12
/ [8 C3 F* i* \5 C2 }9 a5 P, b* }6 T
[color=rgba(0, 0, 0, 0.749019607843137)]13
* U1 L9 F; u5 P2 g
[color=rgba(0, 0, 0, 0.749019607843137)]14
! ], P/ V/ O0 {7 i0 V. f# G
[color=rgba(0, 0, 0, 0.749019607843137)]15
2 R& _( q( [! N. m Z; M& @6 |
[color=rgba(0, 0, 0, 0.749019607843137)]16
2 F7 I; f- ~0 S$ f, @
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
0 E8 _9 L* B! J/ m; }8 n0 Q
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
V, K' w/ o$ S8 g% M7 } W
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
_: {0 j3 A9 d/ E6 m
[color=rgba(0, 0, 0, 0.749019607843137)]{
* b6 g9 M" I+ n" S9 W0 B
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
4 x' B( H9 \4 V* |% P/ B
[color=rgba(0, 0, 0, 0.749019607843137)] {
3 n( L5 U& Y2 h# B" U. g
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
2 a: L2 ^& O" C5 q& v
[color=rgba(0, 0, 0, 0.749019607843137)] }
6 [, G+ C& v# H) k& J* w
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)
1 k0 j w; l1 l
[color=rgba(0, 0, 0, 0.749019607843137)] {
! u) u j8 n* t+ y- K" {
[color=rgba(0, 0, 0, 0.749019607843137)] return root;
) R. H+ r- q* f
[color=rgba(0, 0, 0, 0.749019607843137)] }
( h9 Q: R5 t2 u% C. B( m
[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
% C6 y9 M, a$ C' x; U# |) t3 G! ^# ?
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);
1 D# X0 _9 Q" [1 |
[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)
& X0 N" ]0 f1 }6 z. u
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;
. V8 T2 t+ x$ D. |9 a4 z+ E
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树
) N% c# @% r* i3 a
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);
; \0 W" B! e6 a) q# M( |7 }
[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)
) ?# C r/ ?6 ] `$ |& I9 Z; L1 T
[color=rgba(0, 0, 0, 0.749019607843137)] return rret;
/ }4 Y# _- x; l1 l6 b9 Z6 C K
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
; {+ V8 a* J: {. p. o( D
[color=rgba(0, 0, 0, 0.749019607843137)]}
0 p' K& A$ W' L' b9 X5 L
[color=rgba(0, 0, 0, 0.749019607843137)]————————————————
9 ~/ x* I8 P/ I* l$ G& B
[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. L% L9 V3 m5 a* [0 |
[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
+ A# `1 d' |6 P! _
9 z' t2 c9 L5 ?# |8 a- H' Y. ~
& D5 A# E/ t# D
[color=rgba(0, 0, 0, 0.75)]
7 U: R1 r0 ]3 M: t) v# O, ~! Z
: n o1 d* `. p4 X2 c. q
& x& e. U0 c$ P c
; b$ s$ c/ t! Y% {% b
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5