【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
0 ?5 q6 D' O0 D+ y" K+ u/ r: a1 P
[color=rgba(0, 0, 0, 0.749019607843137)]文章目录5 o9 R9 ^% T* K0 a+ M
[color=rgba(0, 0, 0, 0.749019607843137)]前言
( J, _/ u; {9 `1 [- o. ]) v- p[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
( Y+ U' N W: [7 w[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
2 V! w) e0 U% u[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
9 | m& y9 |' Z* K[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
6 x: K( Y% Z$ A[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数, D2 W5 ?% z1 O9 P
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
& C. A6 ^* X4 |[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
3 X, l( D# m( ?( d[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找, _- T1 l6 }2 N6 w1 W8 a1 Y
[color=rgba(0, 0, 0, 0.749019607843137)]前言) e- r. T# A1 G" m* @) `, P
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。: q* t# Y" S: x$ j' ]
[color=rgba(0, 0, 0, 0.749019607843137)]
K' c, v+ K1 x
0 n# r7 B* n; y3 ~; ^% e[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式5 I4 s, r$ x) d& ~* O7 N* g
[color=rgba(0, 0, 0, 0.749019607843137)]! P2 j9 P( D J n
8 ~; E. q: P" T% ?3 {/ y[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：) L% |8 O7 h% f+ x+ q, P
[color=rgba(0, 0, 0, 0.749019607843137)]2 m X+ D3 h5 E+ }
; ]7 B+ M9 c7 }) s+ H( ^/ e
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树
- j$ `$ P0 ^9 M[color=rgba(0, 0, 0, 0.749019607843137)]( R/ f( @+ ?0 t( C
- A4 C! t# o- x6 [( S" c
[color=rgba(0, 0, 0, 0.749019607843137)]
! @$ Z7 p8 G: ]+ s3 a4 Q% E/ p' N) m: g6 r, T
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树
" p' N7 W! ~6 }0 F0 i[color=rgba(0, 0, 0, 0.749019607843137)]
; D5 e9 O1 ~9 W( m7 C$ M% k) f6 K3 B* s: a, b
[color=rgba(0, 0, 0, 0.749019607843137)]
/ q; n( g3 l! g9 |6 j
8 P& f$ F, X2 N3 ?[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根1 u' v; r4 ^9 ]; z# U
[color=rgba(0, 0, 0, 0.749019607843137)]
$ f1 Z4 Z" P9 G& l) b6 T6 |+ b) m8 \; ?$ T
[color=rgba(0, 0, 0, 0.749019607843137)]
- f0 R3 J% J- l$ \3 G- O3 r& [* _ Q' N$ W
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）$ _* Z& a0 D/ ]( Y& a
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
6 F5 p( T0 O, C4 [( }- f[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
8 A5 x" z2 w7 V$ V! l[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
9 E. Y { u$ K" e& D2 d* C. }" |# b[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
5 z0 z# Y/ S K[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；4 z7 l- E- _2 N5 h3 L3 w5 Z
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；. q: [' W& ]* ~" }, m( }' z
[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
! S6 z5 g. O5 ?$ i( p( T1 p[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。. \5 P4 }( c- f' i
[color=rgba(0, 0, 0, 0.749019607843137)]! N* A$ {; P V0 ?
7 A! I( e0 T2 j: K
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历2 C. s% S. M5 e
[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1
1 p1 b: k( w' ]4 m[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
9 s# _6 X- i3 A- u6 {[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
! @' {: v6 h5 y5 k$ Z* x$ I u[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
" ^- f8 U. O$ N& F! i[color=rgba(0, 0, 0, 0.749019607843137)]& u+ C' Q u+ o, ?1 P' \
- s6 l. R6 |, {& x" j/ M[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;
2 o- S0 t. H/ i: x( j# F5 x. |[color=rgba(0, 0, 0, 0.749019607843137)]
9 M5 s/ I! F1 T/ o; F8 k! T! k
9 p4 K0 j0 y4 {: v7 T! e* n[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体$ P/ z0 a8 e. y, A3 ^/ t3 m; E
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
8 M2 ~5 z7 K$ }: C& H. q[color=rgba(0, 0, 0, 0.749019607843137)]{
7 c# ^% H/ J, z[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;
) n _5 ^. i2 o1 Q0 s* y[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;. X7 U/ }8 U! O4 Q
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
$ q4 H/ }% X/ z6 m4 h6 j[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;
, Y% z1 Y1 T: S3 [1 d[color=rgba(0, 0, 0, 0.749019607843137)]
, n) y# G+ f* \
; E0 Y) w$ _5 Q9 s9 ~+ y+ P/ @! P; E[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历) x4 Y& ?, t* L! U
[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)% U9 ~4 t$ Z, f) R
[color=rgba(0, 0, 0, 0.749019607843137)]{
- s" l8 J! S! R( W3 n( [) H6 n, q[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
( d+ X2 ~5 x$ W; C: J[color=rgba(0, 0, 0, 0.749019607843137)] {
4 R' b: T) N @& e/ |" a[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");1 u Y$ [) |, |' K; \5 t
[color=rgba(0, 0, 0, 0.749019607843137)] return;
: L) x% y& n0 _; g4 n$ [[color=rgba(0, 0, 0, 0.749019607843137)] }0 r" m' d0 X! I5 ]% }6 h- {) S
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
) `9 @8 A; ]% d[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);- M( Q2 l8 u0 j
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);, h. P ^* r& u- C1 z
[color=rgba(0, 0, 0, 0.749019607843137)]}* R0 \* W8 e, R/ Q$ e2 N, u! p* D
[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
; r: Q# m1 `" p: c4 t[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
2 g2 m+ z7 m# l[color=rgba(0, 0, 0, 0.749019607843137)]{" l* X# S+ k* G' R7 B
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
4 s& u. \# G, ^+ J+ d[color=rgba(0, 0, 0, 0.749019607843137)] {
- y$ O5 }' |0 H: m5 w/ w[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");. Q" e/ O5 x% u8 F
[color=rgba(0, 0, 0, 0.749019607843137)] return;
( ?# ^7 d! n: ~, N: I7 k4 U- D- G[color=rgba(0, 0, 0, 0.749019607843137)] }
9 Z1 B( `. b( p* L6 p[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);
1 @) b i' D3 r. m0 t: Q[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);2 ?- ?7 C1 ]/ Z, U/ e8 Y; A
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);
K' L8 p# L* Y; l* }" m[color=rgba(0, 0, 0, 0.749019607843137)]}
w& I8 s* y* y# ]% T3 I[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历2 I" u* S8 _ H% C- n4 z7 z, b5 v
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)( m8 _" e/ m! ~" z) }
[color=rgba(0, 0, 0, 0.749019607843137)]{2 s- ~: V+ ]* w8 B3 I
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)4 L) a& ]* o/ y$ f% M' B1 s! Q; |6 u5 [
[color=rgba(0, 0, 0, 0.749019607843137)] {
|9 q# C+ O/ e/ j! w[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");" Y4 v) A" i' K3 k' V% s
[color=rgba(0, 0, 0, 0.749019607843137)] return;- w) ~' I/ H. I0 Q& s2 }" q
[color=rgba(0, 0, 0, 0.749019607843137)] }* o6 D+ b; l! @
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);0 A5 p5 Y7 i' ^: M
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
) ?0 F/ s: V9 @$ X1 ~ d8 z. \5 Z[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);' n( \+ D3 {3 M2 P% ?
[color=rgba(0, 0, 0, 0.749019607843137)]}+ g, n' `# W ~ h
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构
, j) l N- p0 ]$ K. `1 F[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()
[) w w( _. k/ z[color=rgba(0, 0, 0, 0.749019607843137)]{
f+ x' v) S, s; ~$ n[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间
. y7 v' N3 Y- T9 b[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode)); b& S! E% T7 o- ^, i
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
* U/ }4 Q5 @/ S4 Q* E[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
8 w8 T G2 I9 Z1 l2 x/ \' S[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);
3 j# O& n, \9 {- @9 A[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));3 \$ M9 C( \0 k, q ~ M# W
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);
5 r9 W! d- I7 ~# v! R x[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
$ P. n, r0 t: {: e0 \[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);
- {" b; [, ?8 K5 t3 ][color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
9 C8 V' {" @' T x5 f6 O[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);* ?- Z; G* i! [$ x- Y
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));8 o% N n" l6 G; X: l& ?) u
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);
; C8 R4 P# `+ F& q4 c[color=rgba(0, 0, 0, 0.749019607843137)]* F' c5 z$ L0 h! v# o6 X
* k7 q6 C, s8 T% ~3 w/ ~
[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;
) X7 b7 N7 Y$ g[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;
4 j, _: l7 S9 b7 O6 o[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;
/ F" O; N; M; t[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;1 S$ s3 w1 E( |3 }3 k/ F* ]& l: H
[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;
2 L( b. \: D- o7 ~[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
' A. G. u: O; o: V[color=rgba(0, 0, 0, 0.749019607843137)]
0 Z, ^6 z2 P' F7 G" Z- c" U' J; V9 B1 N# Z6 M) u* }
[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;
# a4 M5 c+ \1 h# e' m4 g[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;
( f m5 k5 i9 ?9 w; J" n" G[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;
. i- F* M! F) R# [5 S+ o[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
3 Q6 t5 J/ ?: r V/ t6 q[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;
o3 k, A" V" i[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;
" ?, L7 P" z7 t5 [& b[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;0 e& c9 F6 X% ?) V, O" V6 {! f
[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;( c m) c/ u" m, E+ P J, j9 e! R6 ]
[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;8 v6 P0 D# t' Q% |" h9 O
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;
% {% K% G% ]! c1 b5 z[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;" ?2 k$ }$ p6 h$ W
[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;- s) q9 @$ M8 S5 |, m& B- L) }" [8 I
[color=rgba(0, 0, 0, 0.749019607843137)]
& Q/ O* i6 \0 i" s. u. w
' R' s, c8 Q* G" z& @/ E* s[color=rgba(0, 0, 0, 0.749019607843137)] return n1;* [7 m0 Q7 _1 Q& v$ `: Q: K/ P. L
[color=rgba(0, 0, 0, 0.749019607843137)]}8 _" z! H% G Z; @$ _7 k7 C
[color=rgba(0, 0, 0, 0.749019607843137)]
% g. h# p7 y) @% D4 m0 S/ B2 C! ]' Z( x6 c
[color=rgba(0, 0, 0, 0.749019607843137)]int main()
- L3 h+ h# B. ?; r/ l" C+ c& x H[color=rgba(0, 0, 0, 0.749019607843137)]{ [( {7 v6 {) x1 g$ }- @
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构" E! Q3 t W+ Z/ ^6 r% M0 w9 I7 G) [
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();" I# G$ F* Y3 @' [& k4 K2 T( _8 S) a/ \
[color=rgba(0, 0, 0, 0.749019607843137)]2 `# U& D/ u8 i2 A: _
c7 W1 M. O9 R6 i8 l% ?: q
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历$ U4 A6 F# r5 s6 Z+ L
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");! T$ D8 J, ~$ Z- a! s9 r, Y
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);$ s* V6 m" [, z. q1 V: O3 o
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");& P. u( X# c; k
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历4 ^3 t7 _! k, A2 s
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");5 L" G& F! {) W/ U: {' x
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);
) G8 E4 H/ ~# {1 X' i( Z( v[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");6 ]1 w0 Q& i4 s" I# L9 K% t
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历8 X$ t( y& H, X# b* z& f
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:"); |; b8 |7 V& K0 p& J
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);) d. o: T* n8 \0 ?0 q7 n" I/ m
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");( ?3 E( F) Y' X. l j5 {" |
[color=rgba(0, 0, 0, 0.749019607843137)]
5 D5 W g7 @- J
* y3 \. H- F$ J6 R+ C[color=rgba(0, 0, 0, 0.749019607843137)] return 0;, Q" h" c; V( @3 t4 C+ B
[color=rgba(0, 0, 0, 0.749019607843137)]}
' n8 }- D2 D1 j( J+ N6 N[color=rgba(0, 0, 0, 0.749019607843137)]1; g7 j. H# g5 x
[color=rgba(0, 0, 0, 0.749019607843137)]2: a* F- d) o% Z, k; m1 r6 n u" g1 C
[color=rgba(0, 0, 0, 0.749019607843137)]3! d6 ^ U: \% v" w0 N5 i
[color=rgba(0, 0, 0, 0.749019607843137)]4$ L% S. _6 Y% X# n* {, G
[color=rgba(0, 0, 0, 0.749019607843137)]5' [, A! r8 e% X6 ?
[color=rgba(0, 0, 0, 0.749019607843137)]6
8 V% G/ }" ~) {" d" s# K. }; p[color=rgba(0, 0, 0, 0.749019607843137)]7# j: ^7 {; O* Q9 T5 {9 V- h
[color=rgba(0, 0, 0, 0.749019607843137)]8# L% p3 m8 R. G
[color=rgba(0, 0, 0, 0.749019607843137)]9
6 w" x' \" l) Z4 x/ [& X! f[color=rgba(0, 0, 0, 0.749019607843137)]105 j+ N1 ?" ^9 g5 F: F0 C, u
[color=rgba(0, 0, 0, 0.749019607843137)]117 c! x8 _: h; \4 h3 F
[color=rgba(0, 0, 0, 0.749019607843137)]12: i0 ~4 R# {; p
[color=rgba(0, 0, 0, 0.749019607843137)]13
% N3 [" y8 R+ {2 I[color=rgba(0, 0, 0, 0.749019607843137)]14
) V/ W- E# I, A( o& ^[color=rgba(0, 0, 0, 0.749019607843137)]151 H2 T8 W8 m0 o" E0 t
[color=rgba(0, 0, 0, 0.749019607843137)]16
7 `- [# \/ H# Q& n" Z[color=rgba(0, 0, 0, 0.749019607843137)]17' D; A) ]; I% u/ m! @/ Z4 ~
[color=rgba(0, 0, 0, 0.749019607843137)]18( B) K4 b$ ?/ a a! Y" C1 a5 V
[color=rgba(0, 0, 0, 0.749019607843137)]19* y g+ t% y1 ]* r" A: M4 x9 [
[color=rgba(0, 0, 0, 0.749019607843137)]20
5 l6 b5 ^8 r p, A2 A[color=rgba(0, 0, 0, 0.749019607843137)]21
0 d6 X! Z$ t* \5 h3 e9 j- Q8 E[color=rgba(0, 0, 0, 0.749019607843137)]22
4 u" y' X/ \& u: K+ E: ^0 ][color=rgba(0, 0, 0, 0.749019607843137)]237 P$ N0 O# c/ q' `6 m1 ^3 F
[color=rgba(0, 0, 0, 0.749019607843137)]24$ D$ { U$ ^) i8 b
[color=rgba(0, 0, 0, 0.749019607843137)]25
( k. a) \( D- m0 `[color=rgba(0, 0, 0, 0.749019607843137)]26
" [3 g; X: X$ m/ O: w, H; u$ G. h[color=rgba(0, 0, 0, 0.749019607843137)]27
; f3 q* ~/ B) \8 x3 a/ o! w[color=rgba(0, 0, 0, 0.749019607843137)]28( O; q: M; y, Q5 P: N, n
[color=rgba(0, 0, 0, 0.749019607843137)]291 |/ l; T. q+ ~' V
[color=rgba(0, 0, 0, 0.749019607843137)]30
( g( G% c8 e; q) e+ v[color=rgba(0, 0, 0, 0.749019607843137)]31* P) t6 d4 r6 I2 ~9 k, [
[color=rgba(0, 0, 0, 0.749019607843137)]323 w8 O6 e2 E) A1 Z) J$ M2 `. w: p) g
[color=rgba(0, 0, 0, 0.749019607843137)]33+ J V: G- E* D1 X7 U
[color=rgba(0, 0, 0, 0.749019607843137)]34
8 E! u! [2 ?% Q* E[color=rgba(0, 0, 0, 0.749019607843137)]352 y0 m0 J" ?1 d# ]' v2 A
[color=rgba(0, 0, 0, 0.749019607843137)]36+ K4 D& ^! W0 `+ h
[color=rgba(0, 0, 0, 0.749019607843137)]37
" l) Q- \' S- t9 M8 c[color=rgba(0, 0, 0, 0.749019607843137)]38
, N3 t4 w* Z$ ?[color=rgba(0, 0, 0, 0.749019607843137)]39# w' a/ x/ \1 W0 n o- v# h/ w
[color=rgba(0, 0, 0, 0.749019607843137)]400 y+ ]' e* B& ?0 o
[color=rgba(0, 0, 0, 0.749019607843137)]41
1 t- S; W' Z; [$ L5 U% v) o[color=rgba(0, 0, 0, 0.749019607843137)]42
9 \- }: p5 {) T* l* R# N[color=rgba(0, 0, 0, 0.749019607843137)]43
# X4 Y: R8 {; A, f! Q[color=rgba(0, 0, 0, 0.749019607843137)]44, r7 N) l' Y/ V
[color=rgba(0, 0, 0, 0.749019607843137)]457 D3 i* L. l" q1 S
[color=rgba(0, 0, 0, 0.749019607843137)]46
, g9 A2 E, H9 _, w+ h8 F3 l[color=rgba(0, 0, 0, 0.749019607843137)]47
6 o( }8 Z- C- v0 r! ^" A[color=rgba(0, 0, 0, 0.749019607843137)]48* t6 ^! o# x' m6 H2 O9 ^3 L# j
[color=rgba(0, 0, 0, 0.749019607843137)]49
+ S: {4 s+ D$ ~. y% d[color=rgba(0, 0, 0, 0.749019607843137)]50
) @% G- L! Y% w& w1 v) E[color=rgba(0, 0, 0, 0.749019607843137)]51+ {; Z) V4 T# {; g& J* Z
[color=rgba(0, 0, 0, 0.749019607843137)]52/ t9 X# l f2 f5 `1 S! P
[color=rgba(0, 0, 0, 0.749019607843137)]53
_3 E( ^0 }7 q5 t$ b- K[color=rgba(0, 0, 0, 0.749019607843137)]540 w( ?# @- L- M) p5 b
[color=rgba(0, 0, 0, 0.749019607843137)]55
5 H3 d6 b+ Z& d2 d[color=rgba(0, 0, 0, 0.749019607843137)]56
. ?! k0 U0 Y$ w[color=rgba(0, 0, 0, 0.749019607843137)]57' ]$ S* ~/ U- f
[color=rgba(0, 0, 0, 0.749019607843137)]58, X0 @5 |( A7 ^ M3 G5 G
[color=rgba(0, 0, 0, 0.749019607843137)]590 J& P; s- |- ?- ?0 z9 p6 N: S
[color=rgba(0, 0, 0, 0.749019607843137)]60
2 d% c+ y; U, P' A0 p7 `[color=rgba(0, 0, 0, 0.749019607843137)]61
: s! ]6 v3 c3 ~9 ?5 T1 J; P2 |& Y[color=rgba(0, 0, 0, 0.749019607843137)]62" ] M, y+ U) ]
[color=rgba(0, 0, 0, 0.749019607843137)]63
% V& R; u8 o# x[color=rgba(0, 0, 0, 0.749019607843137)]64
N/ ^) E) P$ k[color=rgba(0, 0, 0, 0.749019607843137)]65 L2 g7 H1 Q- A/ U5 ^$ n
[color=rgba(0, 0, 0, 0.749019607843137)]66
4 X a) c4 ]3 {- j4 ][color=rgba(0, 0, 0, 0.749019607843137)]67" @* E' i# U0 _) r* C/ C0 D
[color=rgba(0, 0, 0, 0.749019607843137)]68
# R4 \3 S1 E9 }* k& r t2 V0 `8 I[color=rgba(0, 0, 0, 0.749019607843137)]69 n& @+ W* w9 W: R9 p) b
[color=rgba(0, 0, 0, 0.749019607843137)]700 j& A& X+ `9 a9 k3 R& ^
[color=rgba(0, 0, 0, 0.749019607843137)]71; Q2 W8 B& M- Y( b' L3 \, A4 @
[color=rgba(0, 0, 0, 0.749019607843137)]72
" m0 n+ Z9 Y8 z6 `3 ^3 f# S[color=rgba(0, 0, 0, 0.749019607843137)]73- A9 Q, z0 E z4 T u& Z+ A ]
[color=rgba(0, 0, 0, 0.749019607843137)]74
* c; W. F! S7 ]3 p- K5 `" d[color=rgba(0, 0, 0, 0.749019607843137)]75
2 g* e- {# @6 f5 p) C[color=rgba(0, 0, 0, 0.749019607843137)]76/ ~+ _6 m* S2 Q; v0 N) `( s+ L
[color=rgba(0, 0, 0, 0.749019607843137)]77
( E: n; L+ d1 P[color=rgba(0, 0, 0, 0.749019607843137)]78# L2 ~: u3 K3 k1 h' S6 I7 o
[color=rgba(0, 0, 0, 0.749019607843137)]79
% L8 d1 @" u5 q% r- E/ S[color=rgba(0, 0, 0, 0.749019607843137)]80
' o$ S6 G$ h1 i[color=rgba(0, 0, 0, 0.749019607843137)]81
5 p; z0 ^, E, b7 S- ~( M[color=rgba(0, 0, 0, 0.749019607843137)]82
- K7 J5 z# U" E) n[color=rgba(0, 0, 0, 0.749019607843137)]83. a L0 L4 k% U# i3 b
[color=rgba(0, 0, 0, 0.749019607843137)]84
1 `1 a% U# e# o8 K6 I[color=rgba(0, 0, 0, 0.749019607843137)]853 a9 s$ t. O7 I# x# s2 ~
[color=rgba(0, 0, 0, 0.749019607843137)]86+ M' T$ \. |' e, g* f+ n
[color=rgba(0, 0, 0, 0.749019607843137)]87 H1 ^7 }9 Q. a9 V
[color=rgba(0, 0, 0, 0.749019607843137)]88
( y% G; L6 ~! }3 \. D8 @" R[color=rgba(0, 0, 0, 0.749019607843137)]897 e+ I+ [1 c: o$ j9 w9 ?* D
[color=rgba(0, 0, 0, 0.749019607843137)]909 U9 ^* G% x7 B2 N/ p8 q1 S" U
[color=rgba(0, 0, 0, 0.749019607843137)]91
6 n8 e/ ?& ^) ^ ?" |$ p[color=rgba(0, 0, 0, 0.749019607843137)]92
: l& ^; K9 f& { b7 i, [[color=rgba(0, 0, 0, 0.749019607843137)]93
2 }" g0 |) g- f* M2 r' ][color=rgba(0, 0, 0, 0.749019607843137)]941 ]0 M& g6 ~( q5 h8 L5 p3 L/ U n
[color=rgba(0, 0, 0, 0.749019607843137)]95
. b& ?( _. Z- k) J( v5 p( j[color=rgba(0, 0, 0, 0.749019607843137)]96
! |+ O) O5 {# {, G[color=rgba(0, 0, 0, 0.749019607843137)]975 U/ k7 C% r3 q
[color=rgba(0, 0, 0, 0.749019607843137)]98# e2 a; o( ^, z! J+ ? }$ _" o1 H+ q! Y$ ]
[color=rgba(0, 0, 0, 0.749019607843137)]99
* V. ]: W4 n: E- B# }& q0 \[color=rgba(0, 0, 0, 0.749019607843137)]100' N: B; H& m6 N n
[color=rgba(0, 0, 0, 0.749019607843137)]101) Q# Q, d, |, l" m
[color=rgba(0, 0, 0, 0.749019607843137)]102
! _8 @6 ], ~- G+ N( t7 z[color=rgba(0, 0, 0, 0.749019607843137)]1038 l: H* `- V8 `
[color=rgba(0, 0, 0, 0.749019607843137)]104
# b) r: _& Z$ ^* ^" u' ~7 `) V9 z# u[color=rgba(0, 0, 0, 0.749019607843137)]105) U5 J' X$ d N& [& e
[color=rgba(0, 0, 0, 0.749019607843137)]106# U9 q/ b2 {# T; V) w
[color=rgba(0, 0, 0, 0.749019607843137)]107' b( j7 l' ]# |( a' t9 n& }
[color=rgba(0, 0, 0, 0.749019607843137)]108- z; Z+ N4 L ~- v' B' ^
[color=rgba(0, 0, 0, 0.749019607843137)]109
9 \& q4 J. y- T e9 N' r[color=rgba(0, 0, 0, 0.749019607843137)]110
0 V4 r! v! z/ N. H, B3 s[color=rgba(0, 0, 0, 0.749019607843137)]1117 m- V: X) V2 c! ~& X( r. L
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
+ O1 Q2 V* d" q' ?" z[color=rgba(0, 0, 0, 0.749019607843137)]
( q; l0 ], M1 C7 m; e1 n+ s, v0 R: x, r) t# K
[color=rgba(0, 0, 0, 0.749019607843137)]8 y u s4 R! ^( f$ ]
9 M5 n8 M5 J5 m8 k: ^, A[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
" c$ P+ f8 f) K0 w# k% t" h {; `[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
, m/ W! l: k9 w1 l[color=rgba(0, 0, 0, 0.749019607843137)]
0 v, ?2 }( ]" c% N
) q( b' R" l! W[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小4 W; d( O: ^- n7 V3 l" ^6 M7 `/ {1 B8 v
[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量: p. U. ]( s- n
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
, a1 _% ?6 ` r1 c; l[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)# q4 y, S' w) _4 a
[color=rgba(0, 0, 0, 0.749019607843137)]//{& {6 h9 P! P4 S( _; s) \0 ^
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)( r" X& D1 j/ v* x/ f$ @$ p: C
[color=rgba(0, 0, 0, 0.749019607843137)]// {
K7 s$ o: e* M. I) K1 Z[color=rgba(0, 0, 0, 0.749019607843137)]// return;
) m2 p5 Y& B, A9 e[color=rgba(0, 0, 0, 0.749019607843137)]// }
' Z! G: @6 \) y7 O" Z7 v$ d5 J[color=rgba(0, 0, 0, 0.749019607843137)]// count++;) E& k6 R" W# U3 c6 Y: a
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);- Y2 q5 f) H9 A0 T/ `. S! A
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);
. u! n# C- n! m+ k# E/ K[color=rgba(0, 0, 0, 0.749019607843137)]//
3 B3 e' I* H! ]. l5 c[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量 i& ^! ]$ R) t9 Q/ ]/ x
[color=rgba(0, 0, 0, 0.749019607843137)]//}4 M$ W7 T( n0 Q* j. c& b
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之5 y8 Y9 _7 J: Q; }, V) W
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)
6 [5 A& E9 r( o9 d4 _& K6 a[color=rgba(0, 0, 0, 0.749019607843137)]{4 \# ?8 @2 S+ E( U0 B
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;4 E& c0 U3 L( K6 C5 R# U; t" W
[color=rgba(0, 0, 0, 0.749019607843137)]} O7 n7 b; o, O7 P
[color=rgba(0, 0, 0, 0.749019607843137)]1
; ?" i% u) K' X! e+ R' k[color=rgba(0, 0, 0, 0.749019607843137)]2
/ i0 Z9 N3 ]- g* ]+ \/ r1 n& [* K( `[color=rgba(0, 0, 0, 0.749019607843137)]3; y" d# I* d/ ]7 C1 z) R0 n( t8 s
[color=rgba(0, 0, 0, 0.749019607843137)]4) {5 o5 e7 z/ I
[color=rgba(0, 0, 0, 0.749019607843137)]53 |. x* [+ _ l1 ^5 W
[color=rgba(0, 0, 0, 0.749019607843137)]6
+ Q! J% X% t: C/ S: m" ~[color=rgba(0, 0, 0, 0.749019607843137)]72 }' g& Q" H4 `6 j6 H0 l: c
[color=rgba(0, 0, 0, 0.749019607843137)]81 ~6 ^ ?6 s9 T( g; C
[color=rgba(0, 0, 0, 0.749019607843137)]9
& \' H1 Y4 E8 L/ u) ^, c[color=rgba(0, 0, 0, 0.749019607843137)]10
4 y, ~/ J, D+ M! ^6 h% \[color=rgba(0, 0, 0, 0.749019607843137)]11
0 T/ O; x# q6 C1 r! A4 p0 N j[color=rgba(0, 0, 0, 0.749019607843137)]12$ X0 a' ~3 L6 e: S3 j, o. N
[color=rgba(0, 0, 0, 0.749019607843137)]13
9 `6 d1 e, p$ _3 W5 {2 a* I[color=rgba(0, 0, 0, 0.749019607843137)]14# A- C! |* u/ P1 D, h- W
[color=rgba(0, 0, 0, 0.749019607843137)]15
0 o) d, }& j# j) ~. g[color=rgba(0, 0, 0, 0.749019607843137)]16- I2 s) F/ a7 C( h
[color=rgba(0, 0, 0, 0.749019607843137)]17
/ \) B: `% x: T# v7 @6 }[color=rgba(0, 0, 0, 0.749019607843137)]18
0 o5 G! K- J0 W+ x- x5 W[color=rgba(0, 0, 0, 0.749019607843137)]19+ _& \/ n6 ~6 O. X1 p
[color=rgba(0, 0, 0, 0.749019607843137)]20" C- }, w) l* ]% y
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数% t: W* r2 E, _ r4 {
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数
* e1 Q3 ?- a$ M: h3 \/ k4 L[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root), V1 c) d* i/ k- y$ ]; w7 ?
[color=rgba(0, 0, 0, 0.749019607843137)]{
) }( y4 O, l1 }$ P- ~4 A* Q4 y7 [[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点1 a4 t$ \3 \' x
[color=rgba(0, 0, 0, 0.749019607843137)] { U9 J, r4 t6 K, |3 F* A
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
8 n. F7 g: n- P: T& M ]2 B[color=rgba(0, 0, 0, 0.749019607843137)] }
" P: g5 r& U# s. k! |4 ]! }[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空( g; B! j7 J+ Y% ^! P1 }# e
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)0 s7 {$ i6 W3 D5 S
[color=rgba(0, 0, 0, 0.749019607843137)] {
6 Z# b) e( \+ N+ i1 @[color=rgba(0, 0, 0, 0.749019607843137)] return 1;3 L' ?; N( s, U E
[color=rgba(0, 0, 0, 0.749019607843137)] }
; [6 ?. m( ~- |) |6 e[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
; K8 G- ^- K7 a( d3 Q$ ?[color=rgba(0, 0, 0, 0.749019607843137)]}' K9 B$ j) L0 y* d
[color=rgba(0, 0, 0, 0.749019607843137)]1
( x( I- z5 j7 l5 N[color=rgba(0, 0, 0, 0.749019607843137)]2
4 k9 a% I/ s {3 L[color=rgba(0, 0, 0, 0.749019607843137)]3
$ o' f0 P- g* s. S[color=rgba(0, 0, 0, 0.749019607843137)]4! _' k1 m4 P$ I# t
[color=rgba(0, 0, 0, 0.749019607843137)]5
7 c' ]1 ?! F, W- L( ?4 m[color=rgba(0, 0, 0, 0.749019607843137)]6) ^/ Z1 I4 F( b# \# T% [) O
[color=rgba(0, 0, 0, 0.749019607843137)]7( P- B8 Z* ~( v4 y
[color=rgba(0, 0, 0, 0.749019607843137)]8
4 N$ O! N1 L( K2 O4 f4 ^; w[color=rgba(0, 0, 0, 0.749019607843137)]9
' j( J& s8 L6 p4 p[color=rgba(0, 0, 0, 0.749019607843137)]10
# m n/ {" F( F[color=rgba(0, 0, 0, 0.749019607843137)]112 k ?1 P6 I$ L
[color=rgba(0, 0, 0, 0.749019607843137)]125 \7 y! n7 B0 Q0 [* _! [
[color=rgba(0, 0, 0, 0.749019607843137)]131 C' M* h: a1 u3 g( U% R
[color=rgba(0, 0, 0, 0.749019607843137)]14$ F& c( v6 g, u1 n* y; p" b5 M% z
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度# ]% q% p* K: Y8 W: u0 m+ s
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)( |( u2 h s% `. Z( S
[color=rgba(0, 0, 0, 0.749019607843137)]{
- j2 A+ P& f; H) C[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0" C- w- @: E! m2 x2 ]
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)7 X) f( M8 W# D* z# b4 _
[color=rgba(0, 0, 0, 0.749019607843137)] {6 q6 _8 x5 ]+ X% j* m
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;# |' r4 X3 F' Z( C9 e& _
[color=rgba(0, 0, 0, 0.749019607843137)] }
6 g2 R) G, j# u( `9 B[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树9 t" G. D- M# c; @, I, @8 f+ ~
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度$ K, [; j2 V. }. G# |4 Z/ t
[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度
" Z# d' ~7 H! j) r1 Z" N/ c[color=rgba(0, 0, 0, 0.749019607843137)]
9 u3 }, f# ]. _5 C
g8 c% C6 ]6 ~0 O0 k5 J8 c7 C" H4 e[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;2 k* T/ E ~( ^+ I7 f
[color=rgba(0, 0, 0, 0.749019607843137)]}
. T6 e: E! D' o$ M[color=rgba(0, 0, 0, 0.749019607843137)]19 [+ l( ], e" U6 A# {
[color=rgba(0, 0, 0, 0.749019607843137)]2
/ o0 h! @( H2 F5 ^% K; ][color=rgba(0, 0, 0, 0.749019607843137)]3- h4 H# {& u0 Y5 U. P! _2 g7 ?! K
[color=rgba(0, 0, 0, 0.749019607843137)]4
- j& a: ^* W: e/ i[color=rgba(0, 0, 0, 0.749019607843137)]57 |) D/ h# j7 @$ s
[color=rgba(0, 0, 0, 0.749019607843137)]6
, k$ D' L$ Y8 T/ z# O2 v! u, G0 V q[color=rgba(0, 0, 0, 0.749019607843137)]7# A( }9 A8 |5 Y+ ]. j
[color=rgba(0, 0, 0, 0.749019607843137)]8
# o. }7 C# C$ o5 M$ P[color=rgba(0, 0, 0, 0.749019607843137)]96 S; Q2 h6 C' ]! L1 [0 g; B" \
[color=rgba(0, 0, 0, 0.749019607843137)]10
% I+ d" e5 ~5 M& y) d* _0 f9 u! c: H[color=rgba(0, 0, 0, 0.749019607843137)]111 H2 E& C5 M5 g* k W, O0 B& o
[color=rgba(0, 0, 0, 0.749019607843137)]12
5 E `8 [0 `) ]& S8 R[color=rgba(0, 0, 0, 0.749019607843137)]134 K9 V' z- X1 y% l9 a0 t5 `) J
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数) ^5 C9 R8 p! Q# M" _: h5 T" I s
[color=rgba(0, 0, 0, 0.749019607843137)] q* D7 B) J: Q4 A" v$ t! i) y5 V
5 a/ ^( Y, e& e[color=rgba(0, 0, 0, 0.749019607843137)]
4 N1 o" P8 }; P" e: o+ G- p8 R- @7 [" K I X% S
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。8 u; k d: O k3 w6 i5 |, H
[color=rgba(0, 0, 0, 0.749019607843137)]
# d+ ?, [0 Z- X3 Y7 M/ L/ E T4 \3 j' P
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
?7 J$ `) T' W* E& L, A: a9 k" \[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
% X/ A! l2 h( e }, r3 M[color=rgba(0, 0, 0, 0.749019607843137)]{
- P0 |1 Y+ S& q$ F. H; w/ {[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);+ C* G" F$ `: B4 `9 F6 q
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)0 P4 `( t3 K2 t- K, H; e
[color=rgba(0, 0, 0, 0.749019607843137)] {
9 U) b" I! N& L6 i$ l8 N[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
0 v- p, p/ z' x) H( l/ I0 ^. A[color=rgba(0, 0, 0, 0.749019607843137)] }" T2 m6 v& A3 T8 Q4 R* }
[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
1 B7 d9 D! a; k, s& U4 L[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1); p6 O* D+ b, O# T! L1 g! g
[color=rgba(0, 0, 0, 0.749019607843137)] {
5 t% ^4 ~, h" E3 \6 v4 q" H5 d[color=rgba(0, 0, 0, 0.749019607843137)] return 1;# m! ^$ q' l; Q- \+ r7 x
[color=rgba(0, 0, 0, 0.749019607843137)] }
/ W0 N/ k: ^3 r[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层! G9 _) v0 r$ F* O- u* j
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
4 n. o5 u/ p0 I* {" b$ s9 t[color=rgba(0, 0, 0, 0.749019607843137)]}
5 M: ]9 A7 Z' \2 E3 J7 Y _[color=rgba(0, 0, 0, 0.749019607843137)]14 D+ ^* |$ s) B
[color=rgba(0, 0, 0, 0.749019607843137)]2; T9 V1 g, U; [! W! \
[color=rgba(0, 0, 0, 0.749019607843137)]3
: W! S1 f! L6 g: a+ F[color=rgba(0, 0, 0, 0.749019607843137)]4: O! i- C6 B D1 I, ?
[color=rgba(0, 0, 0, 0.749019607843137)]5
* ?5 x- D+ m) N3 |/ B- J @[color=rgba(0, 0, 0, 0.749019607843137)]6, U) P6 ]+ M* {) I
[color=rgba(0, 0, 0, 0.749019607843137)]7, S( ]4 q7 U) u% Q @$ x3 Q, F: [
[color=rgba(0, 0, 0, 0.749019607843137)]80 _& |$ ?( F V1 t" @6 Z6 D
[color=rgba(0, 0, 0, 0.749019607843137)]91 `1 Y+ y: p) C& G4 A
[color=rgba(0, 0, 0, 0.749019607843137)]10
# H7 [, }: \/ \# D[color=rgba(0, 0, 0, 0.749019607843137)]111 h/ n% e' A- Q E
[color=rgba(0, 0, 0, 0.749019607843137)]121 g! R' z: n$ c( V5 ^
[color=rgba(0, 0, 0, 0.749019607843137)]130 X; T3 \9 [- O, c- h; \8 f: _0 }+ r
[color=rgba(0, 0, 0, 0.749019607843137)]14( e: \! D: N9 Y, Y! P8 q, k
[color=rgba(0, 0, 0, 0.749019607843137)]15
' u3 u8 ^% Y8 G+ S[color=rgba(0, 0, 0, 0.749019607843137)]166 ]) n. C L/ J
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找, ~! k0 J. i6 E1 Z) u! J5 [* r
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
y9 G" T) e/ Z+ a" i5 M8 @* \' a[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
3 u7 a7 p! y/ ^' D[color=rgba(0, 0, 0, 0.749019607843137)]{
) e2 U0 r/ Y3 @- O& ~3 e[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
& U9 @) U3 u) [# e* B$ k# z1 Q[color=rgba(0, 0, 0, 0.749019607843137)] {9 V0 t, i* D f; @$ Z4 U
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;9 Q+ U$ l% y5 D, D9 t2 R4 ]
[color=rgba(0, 0, 0, 0.749019607843137)] }) y! @# q- U/ t3 E* I
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)
5 o/ \8 ?: k' w. c" k' {[color=rgba(0, 0, 0, 0.749019607843137)] {6 d$ E, y6 b) f% J
[color=rgba(0, 0, 0, 0.749019607843137)] return root;( f$ N" I$ [$ \/ V
[color=rgba(0, 0, 0, 0.749019607843137)] }
1 C4 L X7 s6 m* ][color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
( |+ D x d4 n[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);
J3 k& P. S' n[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)7 t' T( y9 _& g5 q! R
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;" n7 ~+ S' U# s' R4 H
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树
$ Q+ z( A4 E! Y" c/ ^: C[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);0 k0 T$ h# o& r" H) Z9 u
[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)! E* m2 x. h7 O* e5 r; w3 X
[color=rgba(0, 0, 0, 0.749019607843137)] return rret;
% m% X; I4 l6 |3 N2 G[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
, n$ r4 f! o z% ^3 r7 P[color=rgba(0, 0, 0, 0.749019607843137)]}
, v: j9 v% S, Z5 \0 P6 |[color=rgba(0, 0, 0, 0.749019607843137)]————————————————$ A" }. C! \7 X3 ]1 w2 Q2 j
[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! t4 S6 p) [$ p[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212+ W' s9 h2 C h. l. C) z
: o8 ?# s" O4 I
! z: }; H+ \9 z[color=rgba(0, 0, 0, 0.75)]% G3 c2 x @, I; M
' V q! U5 [" U
Y3 @; U% a6 ~% V C/ q' m {6 c! i. V& I, l: i, D8 ^) n! p
|
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
