【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
, N7 Z4 W P; v4 y' Y/ h' j7 H
% C+ r8 h3 \$ |[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
% l% Z$ u/ F5 |% N8 m/ L[color=rgba(0, 0, 0, 0.749019607843137)]前言" @' a. u' i$ I5 |+ `2 F! L# j
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式) d2 @: b( ?: ]; S( r! B
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）) U# }, ^# k- [5 P5 J& R
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历+ Z: Y1 F1 @$ m
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
a/ }/ S% @* `2 R[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
) E) {: c2 b) I2 W/ d5 `/ A[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度3 m; e/ [2 @3 A6 M
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
4 u4 S1 ]0 A9 n: K[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找7 U3 @7 x3 h p2 b
[color=rgba(0, 0, 0, 0.749019607843137)]前言, e/ _2 m+ w, s; N9 O2 e' N; K* N
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
' L( c! u: i2 M1 g5 L: \[color=rgba(0, 0, 0, 0.749019607843137)]( T& z2 b* S) T
5 w1 C, U- {0 ~8 E3 y4 h[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式0 e9 c' j/ e M4 T: T
[color=rgba(0, 0, 0, 0.749019607843137)]3 Z: I& e# |: R5 }
2 I4 |( ^7 u' m+ g[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：
; J# U% F- H2 @' `+ p8 B[color=rgba(0, 0, 0, 0.749019607843137)]9 f. e; v9 w1 K* y( i- K: Z7 c
* Z' s8 z6 b$ S4 Y$ r. J[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树& [, Z! Y6 E o
[color=rgba(0, 0, 0, 0.749019607843137)]
9 T6 Y* j; U5 H5 ^% r3 B+ k( R+ K+ M g. R, l
[color=rgba(0, 0, 0, 0.749019607843137)]
/ b! j# k" \ H, ~, J9 z- R5 \$ H' E0 b- J" m: Q; Q+ b' s, a
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树5 `3 u$ @8 v2 R1 }6 J$ s; r9 f
[color=rgba(0, 0, 0, 0.749019607843137)] J. ]5 l0 I2 U* b: R1 q2 D
: \& l: h7 P/ [& N8 i( H8 ~3 J[color=rgba(0, 0, 0, 0.749019607843137)]8 `( E. r7 ?; s3 [1 ], i" m
; ~6 \; H3 B/ Y2 H0 i" X
[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根6 T! u G( x, \( F0 R
[color=rgba(0, 0, 0, 0.749019607843137)]" J Q( b# W: K; d. t. q' R6 ?
8 [7 K* f$ _% s0 {[color=rgba(0, 0, 0, 0.749019607843137)]
; K& l0 Z/ Q1 e. \5 C' \$ f2 Z5 V3 G! O" o* S, ]! [- G
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）$ t. y& F5 O3 M9 L- t6 L: @
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
+ e% B9 ~% ]/ ~: s5 z[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；1 h) ^) \1 k8 x' ]" a$ \6 w
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；0 I% | i# N/ t Y9 X) e
[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；/ q; R, q1 ^$ a
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；; m. q% w- B( \2 ]
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
9 k* P- I. y. r[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
/ J- h$ y( f: |[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
8 B) Q& n) T5 a1 y1 F[color=rgba(0, 0, 0, 0.749019607843137)]# e0 K8 Z* l* H% [
1 H+ Z5 v( `2 k5 q
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
, R. ^( |7 z& Z4 [0 ]4 U[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 16 j% g9 Q+ l' a* _1 ^
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
# ]) z) ~3 L8 n3 K1 g2 V[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
! n+ \! i. y2 v$ B+ Q[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
5 Y9 Y, @2 n- ~. d[color=rgba(0, 0, 0, 0.749019607843137)]% R6 y& n' r# r- J X! }
" V N* X- `6 H0 B; t[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;* c; k m% y4 m0 T: @/ K( [" {% e
[color=rgba(0, 0, 0, 0.749019607843137)]& D( w1 k) {% D( ]8 h
# \+ J% F' p# v6 n* v[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体$ _5 O4 X9 e# m) J
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode. @; P: O$ D! {
[color=rgba(0, 0, 0, 0.749019607843137)]{
" |6 u5 G8 C, d; h2 w[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;
/ N- ]* Z6 p2 e9 W1 z[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;
9 P0 N- d) V/ V' E[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
& u% g2 `% x( @& q[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;8 t. e+ j! p v2 d, n/ d0 k, A
[color=rgba(0, 0, 0, 0.749019607843137)]
2 g7 U& t( x/ g3 ~6 ^6 a/ R7 H1 ^& n( t% R7 `2 i x5 Z
[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
5 l9 O( e$ @5 w- U/ t[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
) h7 T {- `% {[color=rgba(0, 0, 0, 0.749019607843137)]{5 J+ }' d! i# m: q8 C* Q! q
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
8 S( @# b$ y% Z[color=rgba(0, 0, 0, 0.749019607843137)] {
7 @" P8 I, O: ~- ]7 \, e[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
6 C9 z6 b* E! X[color=rgba(0, 0, 0, 0.749019607843137)] return;
0 E7 t6 N/ z% E, _" K5 ^' A[color=rgba(0, 0, 0, 0.749019607843137)] }* u# ?$ e, k$ @9 ]3 l) s4 k. c
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
4 G7 R# W6 W5 k% x% X[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);
1 ]4 J# r H1 n7 Z. M4 k" r" f[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);4 w: S! I! i1 {8 q
[color=rgba(0, 0, 0, 0.749019607843137)]}
1 C( S& B, }7 C$ \ E4 O[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历( G; c/ K; b" i3 {" M) @2 m
[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)" N/ F1 v: K* _( J5 L8 T0 O
[color=rgba(0, 0, 0, 0.749019607843137)]{. I- ]* I9 u& g5 w2 I3 L% c
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)! U/ K: O+ N" l T
[color=rgba(0, 0, 0, 0.749019607843137)] {
- N5 W: Q7 h5 p/ a+ Z, b- l; z7 u( `; ]( [[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
# [ i& v6 @% t. n0 _[color=rgba(0, 0, 0, 0.749019607843137)] return;) A, Z* b6 H0 q* w5 @0 `
[color=rgba(0, 0, 0, 0.749019607843137)] }
6 C2 e4 j4 n- U; Q% E[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);$ C- y7 ^# P% A% p) j0 a1 z
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
/ B' _" J, O( q; v$ x[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);7 }- h' f$ ^' x! v' `/ m8 \# f
[color=rgba(0, 0, 0, 0.749019607843137)]}
2 B9 B' H2 j) T1 Y[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历9 ]! S$ ^0 I- }
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)* p3 R7 ]; X% e6 s+ o
[color=rgba(0, 0, 0, 0.749019607843137)]{8 |% p1 _. T4 Z
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
; }$ |2 D7 F3 v3 {[color=rgba(0, 0, 0, 0.749019607843137)] {
& Z1 p, B* ]$ V' W6 \8 Y[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");" H4 @, ?; I9 ~$ V" \& M
[color=rgba(0, 0, 0, 0.749019607843137)] return;$ K y, N/ d) ^& M$ C" t: R6 S
[color=rgba(0, 0, 0, 0.749019607843137)] }
5 `4 q! d) M' p8 W$ v[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);
7 I0 T% p1 p* u9 W; X: p; x[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
- V, C2 w3 U$ y[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
$ Z/ \) X# c+ \$ n2 X+ C[color=rgba(0, 0, 0, 0.749019607843137)]}% D4 B$ [3 I* \; k# {' F K" Y6 H
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构
8 Z/ _% `3 o. R2 ]3 q[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()
3 V7 Q0 k. y6 H9 d[color=rgba(0, 0, 0, 0.749019607843137)]{
! [" [$ b3 K0 O$ r[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间
3 X: N# m/ b; A+ }0 V[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
: x1 K, g+ h% ?* w( k% r/ E[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
8 _; r' m; n2 O2 P4 W+ G[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
' P d+ v1 r' M[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);6 Y9 C! U$ d: E+ ^
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
" `. X, @6 `, @/ j& f, y[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);6 u6 I' t4 l' E) \* w% N3 q# ~
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));3 O6 e& T8 x7 i
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);
+ Q9 j& z- {0 v5 w2 n[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
5 P% q2 d5 n u& t! ]* D) `* b' }, v/ m6 {[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);9 I0 w; T- h! ~! s# C+ g
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
( ]0 f5 m1 `& d# P4 o8 a# O s[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);' N& M9 N+ W5 `9 `3 B) u7 c
[color=rgba(0, 0, 0, 0.749019607843137)]
) i |/ c, N! k8 ^; x* O- A; Q8 ~. z' F+ @7 N& f
[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1; C# ` U+ C, m5 {. V$ G0 n0 Z x
[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;! a# O2 u& _" [, g! t9 ]
[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;
8 H8 e7 j6 M% ]2 E8 C( ?[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;' d. m/ ]+ C5 a' m0 o1 G& q, @0 T
[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;# Z3 W' R* y+ B; K, [' X u9 Y
[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
" P% x2 g0 O; U, G7 f[color=rgba(0, 0, 0, 0.749019607843137)]
# \/ n' a! F0 w2 i
2 v# z3 f# M1 t+ v2 z! C- o- s% ^[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;" t& Q) W# \3 {) J: R
[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;6 U9 [" F p9 W5 v4 F5 X! h
[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;
6 _+ K3 z4 v+ @% m[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
" Z( [6 Q5 [8 [, s" P- G; d[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;
% ~! `5 C3 |3 q h[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;
. L( K t, ?) Z8 y3 I3 ^[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;
+ c3 z$ x/ ~" R2 w$ J; G[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;
4 k! W2 w6 H/ m! O" C[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;. J9 Z& N0 V* n/ G1 Y% X$ a8 M
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;, a2 D9 X/ ^8 b: O1 G
[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;
# M& o; e0 s e9 x& c6 T[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;
" L' M4 z( }+ C/ R" G1 i1 s[color=rgba(0, 0, 0, 0.749019607843137)]
( T2 K2 K' E1 n7 a! |+ F8 u+ ~7 ?! A. v# D
[color=rgba(0, 0, 0, 0.749019607843137)] return n1;% C) S+ i2 G; Z F+ }
[color=rgba(0, 0, 0, 0.749019607843137)]}1 l4 J% m6 n6 g6 g: V7 m- [
[color=rgba(0, 0, 0, 0.749019607843137)]
8 W9 S) W6 \& x' a$ u: L( ^
+ L/ `+ o# e6 s. l7 R; L& T$ r[color=rgba(0, 0, 0, 0.749019607843137)]int main()3 r/ F/ V$ h0 Q& R: W. C
[color=rgba(0, 0, 0, 0.749019607843137)]{0 j9 F5 W9 W3 V
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构
% s- l4 C! Y* t' `5 i/ l# b2 V+ P[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();& s6 q. v0 F: `& |
[color=rgba(0, 0, 0, 0.749019607843137)]
4 S2 j- ` Z! c# x8 e$ B- L7 L1 G; T" f, ?7 k2 [8 y
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历
8 V+ |/ `* e3 a; C( m[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");
& z( z! w) K# C7 @) t7 u$ r& E[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);
+ L8 x. G: @, T+ {[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");: w8 I7 k- L# u0 t
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历
8 [: @. N- q+ C0 X3 A" R% R$ N[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");5 P9 ]3 t; M1 @' B+ C& I( y: `
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);
8 ~( q: \/ ]& r8 k0 n[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");* Y. S: |8 v) F4 p$ |7 H
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历
0 u- X8 t- u* v" ^4 _9 Y& k: C[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");
- \8 {/ H! O8 P1 _* J[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
5 {! m! F( ]( d' w[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
% H' c- }& w, J% y. A' o[color=rgba(0, 0, 0, 0.749019607843137)]
' [& F5 K/ w! G& n x2 n5 T
8 a+ N$ k( I9 B[color=rgba(0, 0, 0, 0.749019607843137)] return 0;6 t# G" y( @4 R0 C, q; p
[color=rgba(0, 0, 0, 0.749019607843137)]}
# ]0 |3 r r" C$ Z Q& k- b[color=rgba(0, 0, 0, 0.749019607843137)]16 v! `# y7 J. G
[color=rgba(0, 0, 0, 0.749019607843137)]2
: G, \# ?% t' d9 v1 k( q" S[color=rgba(0, 0, 0, 0.749019607843137)]3/ u/ A- r: C8 |- `, M
[color=rgba(0, 0, 0, 0.749019607843137)]4
& G2 v. u4 r& x* J6 i* e[color=rgba(0, 0, 0, 0.749019607843137)]5
" |$ Q q9 q6 j/ ?[color=rgba(0, 0, 0, 0.749019607843137)]60 u# x7 d ]# W$ e' z. o8 b' W
[color=rgba(0, 0, 0, 0.749019607843137)]7* v6 l; K& _% z% S G
[color=rgba(0, 0, 0, 0.749019607843137)]8
; r' A# g5 a) b3 F1 ^5 r4 Y7 e- ][color=rgba(0, 0, 0, 0.749019607843137)]9
% q2 M" g' z; G0 O% N5 x: D" T[color=rgba(0, 0, 0, 0.749019607843137)]10
2 K, z+ M, ]0 g' D# K) K: x[color=rgba(0, 0, 0, 0.749019607843137)]11
7 A9 i, a8 S) ?' N[color=rgba(0, 0, 0, 0.749019607843137)]12
% K' j: a# J3 o D[color=rgba(0, 0, 0, 0.749019607843137)]13# X I9 u) G& a2 o* M
[color=rgba(0, 0, 0, 0.749019607843137)]14
3 Z( ` H; e7 m7 i1 {& f- E[color=rgba(0, 0, 0, 0.749019607843137)]15
+ _ u! O* ~; l) P, s[color=rgba(0, 0, 0, 0.749019607843137)]16
+ f% K' F# G G[color=rgba(0, 0, 0, 0.749019607843137)]17
' e1 v* s& j, c/ {; e[color=rgba(0, 0, 0, 0.749019607843137)]189 V) C8 {" j; I0 z1 j E2 t
[color=rgba(0, 0, 0, 0.749019607843137)]19
# o7 g& Z* C/ F6 D+ p5 |/ }' P[color=rgba(0, 0, 0, 0.749019607843137)]20
% U k" }4 U$ ?% o[color=rgba(0, 0, 0, 0.749019607843137)]21- O4 s/ S: O1 e+ ]
[color=rgba(0, 0, 0, 0.749019607843137)]22: k9 m. \% a: W5 s4 e# |! R4 r `
[color=rgba(0, 0, 0, 0.749019607843137)]235 \" X S d. F
[color=rgba(0, 0, 0, 0.749019607843137)]24) e4 V s g6 c/ T* K1 ?) h3 Y
[color=rgba(0, 0, 0, 0.749019607843137)]253 p% ~! [& V/ w! g5 C0 r; f
[color=rgba(0, 0, 0, 0.749019607843137)]26
% P0 |' j' c' D% s! a* n4 c% c1 @[color=rgba(0, 0, 0, 0.749019607843137)]27) o' F( u: w# `5 G
[color=rgba(0, 0, 0, 0.749019607843137)]28! y' G! S% d% E
[color=rgba(0, 0, 0, 0.749019607843137)]29! I9 m' N1 o1 I" R) G' p6 T
[color=rgba(0, 0, 0, 0.749019607843137)]30/ d" _, O+ w! E# ~1 r, f; H
[color=rgba(0, 0, 0, 0.749019607843137)]31+ [+ Q! |- H1 U2 b, @( W v q
[color=rgba(0, 0, 0, 0.749019607843137)]32$ F1 J7 w3 R9 p& H7 U& z
[color=rgba(0, 0, 0, 0.749019607843137)]33% @9 F- X+ B7 `! z% t, C
[color=rgba(0, 0, 0, 0.749019607843137)]349 W6 V5 M; ~# e9 ^$ }4 A o* N
[color=rgba(0, 0, 0, 0.749019607843137)]359 T' v1 y5 B4 D2 D9 V& W! I
[color=rgba(0, 0, 0, 0.749019607843137)]36
. V* e9 ?% V7 w3 F1 R[color=rgba(0, 0, 0, 0.749019607843137)]374 H* H# w; u" l
[color=rgba(0, 0, 0, 0.749019607843137)]384 [$ k, m: M( D+ q7 q# P2 f* Q
[color=rgba(0, 0, 0, 0.749019607843137)]392 D4 C% y& l$ _/ b3 u5 M
[color=rgba(0, 0, 0, 0.749019607843137)]40# J1 j Y( m, \) v8 f
[color=rgba(0, 0, 0, 0.749019607843137)]41
/ B& d3 F( R6 p4 l% `9 Z; H[color=rgba(0, 0, 0, 0.749019607843137)]42: H! M1 f1 I' x
[color=rgba(0, 0, 0, 0.749019607843137)]43: p0 q! b8 y% d9 z# i
[color=rgba(0, 0, 0, 0.749019607843137)]44
* Q; U: }1 A$ J+ N, x" b[color=rgba(0, 0, 0, 0.749019607843137)]452 F9 o6 s; Y$ [7 H
[color=rgba(0, 0, 0, 0.749019607843137)]46
" f* L! u1 h4 M" @3 D[color=rgba(0, 0, 0, 0.749019607843137)]47
3 @. B- J0 w6 s/ N+ c9 F' `; U[color=rgba(0, 0, 0, 0.749019607843137)]480 L7 F' g, N3 A/ e6 C( T3 M
[color=rgba(0, 0, 0, 0.749019607843137)]49$ l( R I: D- G- g b) @, M) W
[color=rgba(0, 0, 0, 0.749019607843137)]50/ v5 c* J% `' K, f4 c2 W# D& c
[color=rgba(0, 0, 0, 0.749019607843137)]51
% `1 W* s* m! E0 N[color=rgba(0, 0, 0, 0.749019607843137)]52
; u4 {* U( p, S3 ^+ T. H1 h[color=rgba(0, 0, 0, 0.749019607843137)]53
4 {5 `) ?* s- ~( @/ [[color=rgba(0, 0, 0, 0.749019607843137)]54. B @0 Y1 T3 L( t$ B( d" C
[color=rgba(0, 0, 0, 0.749019607843137)]55
* \( f$ P4 s- y8 S/ h1 i, x[color=rgba(0, 0, 0, 0.749019607843137)]56$ J2 X, q/ t* g% g0 E+ l* k
[color=rgba(0, 0, 0, 0.749019607843137)]575 k0 X$ K9 @: h5 V( y
[color=rgba(0, 0, 0, 0.749019607843137)]58
- c7 u- D& r/ ~8 x5 w; C! o[color=rgba(0, 0, 0, 0.749019607843137)]59
, E3 e" ^6 ] B8 K[color=rgba(0, 0, 0, 0.749019607843137)]60
, @! T. e# ^/ g; V/ ~( O[color=rgba(0, 0, 0, 0.749019607843137)]61
0 E% h4 H! O/ [[color=rgba(0, 0, 0, 0.749019607843137)]62
$ k5 e6 Z! F1 Z- D! f[color=rgba(0, 0, 0, 0.749019607843137)]63
+ |! ^- v' x% @- m[color=rgba(0, 0, 0, 0.749019607843137)]64) m+ W& }) ]$ W% q) s1 V
[color=rgba(0, 0, 0, 0.749019607843137)]650 l( r8 O: Q9 b8 B) ?
[color=rgba(0, 0, 0, 0.749019607843137)]66
" h: ~8 }) ? M$ M[color=rgba(0, 0, 0, 0.749019607843137)]67" Q6 k! C* E9 n8 o
[color=rgba(0, 0, 0, 0.749019607843137)]680 s a" A( Z9 o7 j$ J0 K
[color=rgba(0, 0, 0, 0.749019607843137)]69. V1 `) ~0 u# J4 H: f2 i$ y
[color=rgba(0, 0, 0, 0.749019607843137)]70/ g$ @+ ]; |) g; m
[color=rgba(0, 0, 0, 0.749019607843137)]71- i& N! y- }3 ~. _4 E4 \& J$ }$ ~
[color=rgba(0, 0, 0, 0.749019607843137)]72
& h$ l# C9 Y- b4 t$ n w: a+ E) c[color=rgba(0, 0, 0, 0.749019607843137)]73! r% [( B& c9 o( Z$ o
[color=rgba(0, 0, 0, 0.749019607843137)]74% ]; ?4 I/ ^8 w1 p
[color=rgba(0, 0, 0, 0.749019607843137)]75
, T. E0 P u9 k! I9 c3 e2 b) h1 [[color=rgba(0, 0, 0, 0.749019607843137)]76$ ^+ c) _$ e6 n* D# m3 _8 H
[color=rgba(0, 0, 0, 0.749019607843137)]77 m' e2 s) U, Y' I
[color=rgba(0, 0, 0, 0.749019607843137)]78
: O' o. y% Y0 L- g: K0 D* c[color=rgba(0, 0, 0, 0.749019607843137)]79
6 G: J9 H8 x3 l" }1 K$ \[color=rgba(0, 0, 0, 0.749019607843137)]80/ M, V G8 z' C, v* \; D1 o
[color=rgba(0, 0, 0, 0.749019607843137)]81% b3 d- ?) x& A5 P, W4 X: D; k
[color=rgba(0, 0, 0, 0.749019607843137)]823 y( x6 u* a) \' A
[color=rgba(0, 0, 0, 0.749019607843137)]837 I" J' m, f0 ]8 w R5 l% P9 l
[color=rgba(0, 0, 0, 0.749019607843137)]846 G. i3 t! v+ { G8 O) i5 _
[color=rgba(0, 0, 0, 0.749019607843137)]85) X2 w( ~$ x J
[color=rgba(0, 0, 0, 0.749019607843137)]86, _ @4 }7 B) I0 }1 p. q
[color=rgba(0, 0, 0, 0.749019607843137)]87- e; P: C3 ]1 e7 E4 a
[color=rgba(0, 0, 0, 0.749019607843137)]88, W, ?2 ?* _- G' N* i
[color=rgba(0, 0, 0, 0.749019607843137)]89& R3 \# Y* P" t+ T. q. |& E x
[color=rgba(0, 0, 0, 0.749019607843137)]90
5 m# i6 V; j8 S' Q' M4 f6 }[color=rgba(0, 0, 0, 0.749019607843137)]91 E" g% N* c+ t
[color=rgba(0, 0, 0, 0.749019607843137)]92) a% q, b1 M7 M+ v
[color=rgba(0, 0, 0, 0.749019607843137)]93
3 C! i% X3 C" r[color=rgba(0, 0, 0, 0.749019607843137)]94
! D; d* r/ u* d7 O/ A* z! I[color=rgba(0, 0, 0, 0.749019607843137)]95
2 \) ~# h3 l/ Q, B3 V# o( [[color=rgba(0, 0, 0, 0.749019607843137)]96. ^# n+ D+ y6 p. K0 R( w+ E+ {0 j
[color=rgba(0, 0, 0, 0.749019607843137)]971 }* ?0 v) [+ L) N
[color=rgba(0, 0, 0, 0.749019607843137)]98. W e2 D5 D1 X2 M0 E# D1 s( L
[color=rgba(0, 0, 0, 0.749019607843137)]99) _4 Z. m. G/ n! G- |0 i
[color=rgba(0, 0, 0, 0.749019607843137)]100
9 l# l( A& [6 ~# k% k8 `# I[color=rgba(0, 0, 0, 0.749019607843137)]101. f3 E& o8 _( \* E3 u/ I
[color=rgba(0, 0, 0, 0.749019607843137)]102/ B$ }, g; ?% |' _8 a5 z& {* y0 k$ E4 [
[color=rgba(0, 0, 0, 0.749019607843137)]1034 l E2 o [# c `8 O4 O% L
[color=rgba(0, 0, 0, 0.749019607843137)]104
0 o. I7 a3 f" g. p2 y[color=rgba(0, 0, 0, 0.749019607843137)]105
& g3 _+ L0 }2 d' ^[color=rgba(0, 0, 0, 0.749019607843137)]1061 C8 ?+ l7 S9 L1 \* D: O) H" Y+ b
[color=rgba(0, 0, 0, 0.749019607843137)]107
! @. M$ q h4 [2 k3 P) A; ^0 `/ u[color=rgba(0, 0, 0, 0.749019607843137)]108: A$ f5 m6 I# C, t+ L5 d/ c
[color=rgba(0, 0, 0, 0.749019607843137)]1099 h& Q& T$ X4 q, V4 r4 T
[color=rgba(0, 0, 0, 0.749019607843137)]110% T" C" G$ P: k
[color=rgba(0, 0, 0, 0.749019607843137)]111
; K1 ~5 X; c5 v& T( d[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：1 v. d# y+ \$ Z. [: y% J( p
[color=rgba(0, 0, 0, 0.749019607843137)]& Y. O/ z! ~% e% X/ }9 A1 |
7 n2 J2 l, @5 S9 K1 N4 L8 Y[color=rgba(0, 0, 0, 0.749019607843137)]
4 X' I. ]+ {; x7 t4 ]* A* m3 j
3 O& Z3 f* L& U' u! S* T[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小4 j, x- m9 D% P: A. O; y* s
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)# X+ w# K# v' X# W. B3 O
[color=rgba(0, 0, 0, 0.749019607843137)]
1 J$ j. W: x) e: ]4 u1 d5 ` P8 E6 x! _' U" ~
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
- t! B* ^! O8 i9 F( C* u1 `[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
5 K4 p) F7 r9 F$ v7 ~[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
5 h6 p1 Q- i" q. z) M0 d% I L, y3 k[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
- o. J7 A @3 I0 t; i[color=rgba(0, 0, 0, 0.749019607843137)]//{
6 E( p5 }1 o: W* N[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)3 b$ g5 Q; s! y( R/ H7 S, r+ _
[color=rgba(0, 0, 0, 0.749019607843137)]// {
) h) F' Q \$ B5 k[color=rgba(0, 0, 0, 0.749019607843137)]// return;
9 p- E% F% \/ f4 x5 ?/ l0 E h+ ~[color=rgba(0, 0, 0, 0.749019607843137)]// }
) U; w/ Y, [- p" t# q' l[color=rgba(0, 0, 0, 0.749019607843137)]// count++;: [/ g2 v6 ]( l; C
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);% g0 Q8 w0 d1 N* k; [$ t5 G' @
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);
+ I% F! x* Q8 G& F; T[color=rgba(0, 0, 0, 0.749019607843137)]//* ]! C; @/ W) N
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量5 Y) w% j4 {) |2 ?
[color=rgba(0, 0, 0, 0.749019607843137)]//}" G* h' A5 M* ]
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之5 Z) T8 N, t, Y0 T* T/ k; o) {) C# p
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)5 i5 F; y! X) k9 o' Q7 [
[color=rgba(0, 0, 0, 0.749019607843137)]{- b- h2 V/ m# V5 h. M, h+ \/ }
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;2 m8 ?3 Z) j2 D6 R0 D6 J/ o' ?0 L
[color=rgba(0, 0, 0, 0.749019607843137)]}
, g- V& d. d/ ^1 d1 K% V r3 z[color=rgba(0, 0, 0, 0.749019607843137)]1
& l4 t( m/ A- f* t& u3 D[color=rgba(0, 0, 0, 0.749019607843137)]2
0 X, R6 G/ G6 t[color=rgba(0, 0, 0, 0.749019607843137)]3
6 H2 x" L/ A$ z: u- r9 T9 l5 J[color=rgba(0, 0, 0, 0.749019607843137)]45 w" ^' d8 g& ?- ]% A5 T7 ?
[color=rgba(0, 0, 0, 0.749019607843137)]5
, j* Y0 X' Z& y. V% S9 C% m+ g[color=rgba(0, 0, 0, 0.749019607843137)]6
: Q# C! }8 i1 o[color=rgba(0, 0, 0, 0.749019607843137)]7 @, I5 }2 m0 [# b7 z$ R1 R$ T* u
[color=rgba(0, 0, 0, 0.749019607843137)]87 [+ s4 R0 n. o' f- `7 i
[color=rgba(0, 0, 0, 0.749019607843137)]95 s$ d/ Z3 S l8 s8 I* z: j' t
[color=rgba(0, 0, 0, 0.749019607843137)]106 Q) d% K: ~( i; e( t
[color=rgba(0, 0, 0, 0.749019607843137)]11
& r$ o" |# c- Y B) U3 `[color=rgba(0, 0, 0, 0.749019607843137)]12; Y- X' N4 \5 h# t8 ^- O
[color=rgba(0, 0, 0, 0.749019607843137)]134 g4 P" h# w1 ?3 g* T
[color=rgba(0, 0, 0, 0.749019607843137)]14
" _3 A7 Y% _; [9 v/ a0 B5 t. f[color=rgba(0, 0, 0, 0.749019607843137)]15
$ H. |# B7 Y+ j" N/ O/ Q[color=rgba(0, 0, 0, 0.749019607843137)]161 [; z( W2 g- v
[color=rgba(0, 0, 0, 0.749019607843137)]17; v1 u! b: I0 L7 ]: b# j# u
[color=rgba(0, 0, 0, 0.749019607843137)]18, X' \8 Y( f2 O. m! k
[color=rgba(0, 0, 0, 0.749019607843137)]19
4 E: U1 i$ x. @. L0 f0 }7 L[color=rgba(0, 0, 0, 0.749019607843137)]20
. ^" e2 Y3 y1 Z- J1 g4 {[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数5 r0 q6 X( z$ q% Y" x. ]; n
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数) q6 ^6 U- y3 ]$ i( |
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
! p! }% B' r6 [" a! Q[color=rgba(0, 0, 0, 0.749019607843137)]{" ]$ p E U/ _9 U: P: `: |( ?
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点1 X! ?3 c' O9 R: J1 S
[color=rgba(0, 0, 0, 0.749019607843137)] {; l7 S* G6 r2 c, N8 h
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;, }. K8 r6 e/ {. v# t5 d3 H! \
[color=rgba(0, 0, 0, 0.749019607843137)] }3 s9 ]2 _, |. P, F0 U0 c
[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空
4 E/ q- f h2 g( }% W& t& D[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)' q* z2 ]4 j) S! U; e1 p& ^: a. i
[color=rgba(0, 0, 0, 0.749019607843137)] {
~, r/ v4 l5 c3 m# g[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
' `9 P7 H3 b! q- a4 F[color=rgba(0, 0, 0, 0.749019607843137)] }
; I% |8 n4 @' v[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
: U$ \6 ]$ U" e( z o) ^[color=rgba(0, 0, 0, 0.749019607843137)]}7 t/ K4 S; e$ N- R9 D1 t
[color=rgba(0, 0, 0, 0.749019607843137)]1
6 L6 e+ Z: N g8 ^% q# M/ w) n7 n! i[color=rgba(0, 0, 0, 0.749019607843137)]2 k) w6 e0 t9 G2 N
[color=rgba(0, 0, 0, 0.749019607843137)]39 x3 ]- c R/ w1 i, N$ S
[color=rgba(0, 0, 0, 0.749019607843137)]4
" G+ \% ]9 v! e[color=rgba(0, 0, 0, 0.749019607843137)]5
9 m; P4 |! Y$ M1 O5 Z1 w p[color=rgba(0, 0, 0, 0.749019607843137)]6; f$ }# o$ H/ p7 F: N# y
[color=rgba(0, 0, 0, 0.749019607843137)]71 w. C7 e8 M) C# m: Q3 V9 e
[color=rgba(0, 0, 0, 0.749019607843137)]8
& f0 N# X" G" E7 h* O! p R[color=rgba(0, 0, 0, 0.749019607843137)]92 l7 J7 l( K2 Y
[color=rgba(0, 0, 0, 0.749019607843137)]104 z4 N: K9 k" {/ M& x1 E
[color=rgba(0, 0, 0, 0.749019607843137)]11
" Y& R B5 F8 a: `4 s[color=rgba(0, 0, 0, 0.749019607843137)]12
* W$ O4 Y9 M. A" g[color=rgba(0, 0, 0, 0.749019607843137)]13
7 s" n% e; i' A% y) N[color=rgba(0, 0, 0, 0.749019607843137)]14
/ [) r, {# F+ T, Q4 M[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
" C6 |; C' Q# T1 ^( k1 X[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
7 z) E+ p; I5 C& s: ~5 J4 {/ V9 W[color=rgba(0, 0, 0, 0.749019607843137)]{, F# E) E0 r/ C" K
[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为04 b. U4 o/ g: X
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
$ N6 m; u% v- t& U$ i[color=rgba(0, 0, 0, 0.749019607843137)] {- g0 B- W* j1 j
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
V, ~. w- X3 i- j9 ^- o[color=rgba(0, 0, 0, 0.749019607843137)] }
1 p8 ?$ H8 ^0 {; d) T0 O& |! B[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树+ d6 |. d. f5 ~2 L _4 R/ H
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度
% z0 E2 G& F4 e/ R1 S, e. X[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度6 b1 |' K N( O
[color=rgba(0, 0, 0, 0.749019607843137)]2 i8 ?- e4 t1 W3 f7 o8 [* N6 X
# ]- t% D6 U/ }8 t$ `- q[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;
- j5 k& H8 T" a; p[color=rgba(0, 0, 0, 0.749019607843137)]}
: _' t% Z" ?# E: {( o1 H# ]- `[color=rgba(0, 0, 0, 0.749019607843137)]1
& c* h& g0 J& Y* X9 Y w[color=rgba(0, 0, 0, 0.749019607843137)]2# L7 @/ N V4 \
[color=rgba(0, 0, 0, 0.749019607843137)]3$ {, n% r8 {* j" U8 E
[color=rgba(0, 0, 0, 0.749019607843137)]4 N( l) R7 V, R- h, d+ d
[color=rgba(0, 0, 0, 0.749019607843137)]55 n, Q6 G; V9 `. M3 T2 g
[color=rgba(0, 0, 0, 0.749019607843137)]6
" ^3 `$ {; L i b# }$ j6 m" a[color=rgba(0, 0, 0, 0.749019607843137)]7; M" ~: [0 z1 P
[color=rgba(0, 0, 0, 0.749019607843137)]8" H* `5 N0 \% d( {, {4 o1 n
[color=rgba(0, 0, 0, 0.749019607843137)]9
- V4 C s8 j X' v- Z. c$ F[color=rgba(0, 0, 0, 0.749019607843137)]101 K X. g% E" l* n# ?8 M2 @8 `
[color=rgba(0, 0, 0, 0.749019607843137)]113 o1 l- [$ ]% c' L9 \4 C: u, P
[color=rgba(0, 0, 0, 0.749019607843137)]12
$ T( N* W$ ]& J3 W2 x[color=rgba(0, 0, 0, 0.749019607843137)]13* x# H% @5 E% h( R
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
3 S! D; L5 U: c7 F) P[color=rgba(0, 0, 0, 0.749019607843137)]
3 M' [, x$ L$ R! i' q4 s% U* Z* a, w$ }) h
[color=rgba(0, 0, 0, 0.749019607843137)]
( e+ T, a* M ]/ o) E$ |* E6 C, B- X/ n9 K7 Q
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。/ s1 H5 D+ [! C% N% t8 z
[color=rgba(0, 0, 0, 0.749019607843137)]
$ e) S3 P; i0 q9 U0 H4 {& G5 [. D5 @9 r3 H+ C9 O/ m) a: r
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数- }7 V2 L& N6 R5 V
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
9 m! d0 k# A/ P8 h% {& f4 k2 D[color=rgba(0, 0, 0, 0.749019607843137)]{
/ d6 ?8 B- r! U& y6 N[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);4 ]" B& W+ G# f# E/ }
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
3 V( x5 c5 w- H+ `4 G( p0 s[color=rgba(0, 0, 0, 0.749019607843137)] {3 L) S' Q: E) ~! h$ h1 ?7 b' L" g
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
7 _% `$ F6 x, c$ |% u[color=rgba(0, 0, 0, 0.749019607843137)] }
1 A& A7 x0 u9 F# s$ D4 S8 b9 A[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
6 B, u- Q# o% i# z6 |[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1)
. q7 Q6 @/ u) {5 D, f: t( c[color=rgba(0, 0, 0, 0.749019607843137)] {
0 N% H- G' @& j1 R8 B# O[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
1 }8 Y" s( l$ w5 f% f ~" C[color=rgba(0, 0, 0, 0.749019607843137)] }
# j+ E5 p, F( B( N! x[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层 g1 y/ Z$ ?9 }! j/ C0 P
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
/ U0 g+ G% ^5 X3 T& n+ T[color=rgba(0, 0, 0, 0.749019607843137)]}. d& ~% C8 F9 d$ o6 c
[color=rgba(0, 0, 0, 0.749019607843137)]1
9 _3 u$ k0 D% p[color=rgba(0, 0, 0, 0.749019607843137)]25 S0 a0 e7 P2 F+ |7 |
[color=rgba(0, 0, 0, 0.749019607843137)]3
$ l& V4 y0 Y& K) W[color=rgba(0, 0, 0, 0.749019607843137)]4# Z: T% L8 ]3 b0 E* H
[color=rgba(0, 0, 0, 0.749019607843137)]5
$ `% Q3 X2 e" ~/ N[color=rgba(0, 0, 0, 0.749019607843137)]6
N6 E S! o: W) C$ i[color=rgba(0, 0, 0, 0.749019607843137)]77 V, `, V# H+ x; }' |8 a, \) p w
[color=rgba(0, 0, 0, 0.749019607843137)]8# X, _' P7 o0 B4 ^
[color=rgba(0, 0, 0, 0.749019607843137)]9 `" R5 Y* A2 i1 h4 t ]: Z6 F
[color=rgba(0, 0, 0, 0.749019607843137)]10
1 |+ ?( ~) m6 {: j! m" N7 R[color=rgba(0, 0, 0, 0.749019607843137)]11
& H8 m8 _1 e; ]& c( u. I) y[color=rgba(0, 0, 0, 0.749019607843137)]12, T s' k) i3 }/ @4 F
[color=rgba(0, 0, 0, 0.749019607843137)]136 w2 K3 Z- `; S5 M0 b' S8 Q
[color=rgba(0, 0, 0, 0.749019607843137)]14
1 m3 `1 l; ?0 E- K- r5 w[color=rgba(0, 0, 0, 0.749019607843137)]155 T' Z, K$ Q# j Z
[color=rgba(0, 0, 0, 0.749019607843137)]161 z" }4 Y r" i& B
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找, \! e% r$ l3 N5 w$ R
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找' ?& ~# `* a: m7 I
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
- b* A% }' A9 ?) w0 W[color=rgba(0, 0, 0, 0.749019607843137)]{8 `. P% n3 D, i3 U
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)% n4 W8 t/ w2 N1 m/ t! c, B4 a! M+ s
[color=rgba(0, 0, 0, 0.749019607843137)] {0 X' W: h9 O( Z; u
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;) }; _0 o3 z9 A3 s' Y& N2 U: d
[color=rgba(0, 0, 0, 0.749019607843137)] }
i& {# {) }- Z! P ^3 O7 l* h1 h[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)( C) P: @0 `/ h9 a }0 M# v, ]/ ~
[color=rgba(0, 0, 0, 0.749019607843137)] {) F! C5 O; C: e a2 m' S
[color=rgba(0, 0, 0, 0.749019607843137)] return root;
1 j- U/ _2 W+ F0 Y% a[color=rgba(0, 0, 0, 0.749019607843137)] }
. Q1 K6 w( N" m, x[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树3 I. [# _7 Z. Q( B
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);# ?+ `) }$ |, n' ] K% b
[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)
3 Y0 Y% P9 b; _% l4 ~7 r[color=rgba(0, 0, 0, 0.749019607843137)] return lret;5 L! ^" R5 w& i
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树0 V% q0 V# e8 [3 ~
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);" w* Y: K& l2 x9 p, \0 v* R; u
[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)
8 M9 ?) o& ~ j7 P2 M7 [: Z6 x[color=rgba(0, 0, 0, 0.749019607843137)] return rret;
* ?- ]- d" S* A4 A, J% `[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;1 B% f ?3 q6 q. f1 T8 Y {& B# G
[color=rgba(0, 0, 0, 0.749019607843137)]}
7 ~5 }- d0 W/ a* b0 Z% ][color=rgba(0, 0, 0, 0.749019607843137)]————————————————
! [& ~8 f7 A0 X+ O, Q- F/ C, Y3 B) T: M[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- u% G: Z! J/ } n0 @[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212 \& s6 G4 g: a
# h! u: P6 p2 }; l* C. e, \; x
7 g, W6 e/ c" z. g; D
[color=rgba(0, 0, 0, 0.75)]
! B# B/ H6 s. H9 l* C% R v2 l! s! ?3 Y. Y6 {& o0 t; v2 e0 h
8 {1 X# x/ X, I; B5 h( n5 d$ j9 a: M5 H' I; F- z- P+ M- g2 Q
|
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
