数学建模社区-数学中国

标题: 【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历 [打印本页]
作者: 杨利霞    时间: 2022-9-15 11:55
标题: 【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历0 q' Y7 s+ I7 Z

4 r' @: [) L0 Q[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
4 A; q% J; W0 V" W! @$ b[color=rgba(0, 0, 0, 0.749019607843137)]前言4 [  c: {4 M& @5 v- O( k& N8 D! t: B
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式+ h, ~( x- P" S9 g
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）" C  E; `3 e, D) x3 [, f
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历8 ^2 a8 M7 K/ E3 {
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小+ U  C' Q9 C; \* ?/ b7 E) M
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
( p" ?0 V% L2 S( c$ H+ b[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
; c; U  A; o0 ^; o[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数' o7 r4 B4 j+ P2 F! L
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
% Z- s# a/ T: G5 ]  C$ |. E[color=rgba(0, 0, 0, 0.749019607843137)]前言3 s  ^9 V, V% m/ H/ }, P/ |+ [
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
$ `0 x6 C, i, H[color=rgba(0, 0, 0, 0.749019607843137)]/ _% @, J) i! {7 n9 I( S& h

5 N6 ~4 p; x7 L( R; X[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式1 {# I7 }% \: G5 \
[color=rgba(0, 0, 0, 0.749019607843137)]9 k4 n: L0 [4 z
3 G+ V7 ?) Z: C9 P8 p: L6 X
[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：2 a* m  w" l  |3 r+ o) y4 U
[color=rgba(0, 0, 0, 0.749019607843137)]" y0 h7 @' E5 s; ]. j
" g" q+ b* M/ s  @. K# c
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树# X5 n! j5 Y9 ?/ W+ O, @' b: ?
[color=rgba(0, 0, 0, 0.749019607843137)]  W0 z- T" U1 m' P' c- w
0 w2 F- M5 C+ r7 A
[color=rgba(0, 0, 0, 0.749019607843137)]' |& m! B: B; f4 T8 Q# n" W8 M# f
( I* U) w9 F1 y, T7 ~
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树
( D2 y, q' i8 p2 ?$ s[color=rgba(0, 0, 0, 0.749019607843137)]/ J7 j$ V3 C5 n+ l3 I

, ?0 }- B) ?% b+ C[color=rgba(0, 0, 0, 0.749019607843137)]
- t( F0 V; q7 |2 A& @
$ V3 Z1 @  O- m" g2 W: B9 \[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根2 V" O8 V% ^9 M1 L2 [4 X; G
[color=rgba(0, 0, 0, 0.749019607843137)]
, @1 s+ B, {$ K# |( |7 y8 \; f+ w: I
[color=rgba(0, 0, 0, 0.749019607843137)]& A9 a: [/ r$ K% f0 J& e. d" {
2 o) r6 r! m* A
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）7 M5 n- `  C/ I% d
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
$ C& ~1 E8 F0 T[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
+ k# x9 b% |' C[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
) A. g$ L$ c) t. e- x" P[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
- r: q+ S! M4 i0 N0 `3 O[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；
  \/ U) m: u7 ~3 V4 P8 I% [$ [[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；( m3 V0 y+ a, r) D4 J, e4 g
[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；" U1 m& v8 P9 ~  C- r
[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。5 z8 y4 \) D# M& T" P
[color=rgba(0, 0, 0, 0.749019607843137)]( \" z. M2 C3 G5 O! a6 E% \
; d1 `  G% n& J
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
5 c& V- s5 J2 u( N8 `# z) U& t[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1) ]1 i. J  w1 `! ]* y$ D& e
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
) P4 p0 P' ]7 p! z0 H' [[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>& v( E+ R  ?) e' U5 v/ I# U# p
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>( X- ^  p7 @& Z  G- }: G( l
[color=rgba(0, 0, 0, 0.749019607843137)]4 h' H# `0 H3 M1 S' J2 T6 {

* K% C7 h; l6 ?) v; E[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;" c$ ^8 {2 b( G4 }/ B; c
[color=rgba(0, 0, 0, 0.749019607843137)]
2 o5 }, B0 C' v6 ]+ j0 l- ~! f! s; q  e9 K: k. f
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体8 b6 Q( Y* t* i- d4 J! R7 C
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
# _4 M1 H  H! E1 I$ w7 i[color=rgba(0, 0, 0, 0.749019607843137)]{( F% k0 Z$ M7 M2 m! d
[color=rgba(0, 0, 0, 0.749019607843137)]        BTDataType data;
# i, `& ~4 a6 H% ^[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* left;
  o8 \" N9 p- s8 x: o7 D[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* right;
1 S9 `; ^# k( B8 ]' c  g1 ~[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;0 n6 S/ \1 ~. t
[color=rgba(0, 0, 0, 0.749019607843137)]/ ^: j# R4 t: w, S$ x7 {

4 a" J9 R+ x- i* a% P# L5 s* B[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
0 b- T$ h) O1 R" R5 Z6 Q. u[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
4 v/ P% K9 c. {& C[color=rgba(0, 0, 0, 0.749019607843137)]{1 M5 V: h0 N7 F4 Y) {
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
; K  T+ S7 S2 F( |, `8 `[color=rgba(0, 0, 0, 0.749019607843137)]        {
' k! f! V+ \9 j% i- V) H[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");& ~% W, g/ D1 C) Q: J5 P
[color=rgba(0, 0, 0, 0.749019607843137)]                return;
# U/ ~; E/ z4 O[color=rgba(0, 0, 0, 0.749019607843137)]        }- t: V% j  V$ C! {/ H; H* g
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);) p- g* Q! Q# ^1 ~5 }& L/ e
[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->left);  t% ?" O7 g: C" n
[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->right);  T. v. ~2 O$ t0 P* E- Y
[color=rgba(0, 0, 0, 0.749019607843137)]}
4 n, e& m- v' T" ~3 O1 ][color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
5 B) {9 M" g1 V[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
3 j$ G2 x# X, |( l3 E  S[color=rgba(0, 0, 0, 0.749019607843137)]{7 b; z9 _: {, N0 p  p7 T
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
* N7 u) U6 J6 j/ O7 C1 ][color=rgba(0, 0, 0, 0.749019607843137)]        {/ W! M, R4 `8 z5 w: Q$ M+ i- W
[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");
$ c  Q' c/ Y# a$ p% G! S. l5 M[color=rgba(0, 0, 0, 0.749019607843137)]                return;
7 I/ I0 j" Z: p) b/ z[color=rgba(0, 0, 0, 0.749019607843137)]        }
* N# x8 Z' u* l; _& w[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->left);3 a- n8 q, Y; v
[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);, v, N  J! E' j% ]+ q
[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->right);6 X7 k& p4 s# e6 _
[color=rgba(0, 0, 0, 0.749019607843137)]}
5 F" B- h& X+ z# t- w[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历4 V' @  ]( T1 [
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)6 q8 |& C* F2 s0 {; M4 g
[color=rgba(0, 0, 0, 0.749019607843137)]{
+ [7 i6 z7 z+ A+ Y4 b! x[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
8 ?  c+ {( t: T" T5 N[color=rgba(0, 0, 0, 0.749019607843137)]        {6 p) {7 A$ V5 E4 }$ g$ C5 R9 R4 g
[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");
+ z+ G5 n* Q. ?( @" c  z[color=rgba(0, 0, 0, 0.749019607843137)]                return;
+ b8 c+ }  w% O# Z, `. |0 G8 W0 R[color=rgba(0, 0, 0, 0.749019607843137)]        }4 c$ m) ?, d7 b, ^- \9 K/ ~7 H# ?
[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->left);0 c; Y* f8 t; a: l  E
[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->right);
) x4 V3 e. y3 T* D' A- A[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);( o$ A' l6 b5 K# X: w! m
[color=rgba(0, 0, 0, 0.749019607843137)]}, }8 {- y: F7 R# q/ C; P5 X
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构
+ }/ w0 q# S  K, @. k[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()6 T9 u4 G4 `! |) A# f
[color=rgba(0, 0, 0, 0.749019607843137)]{' v" Z/ G1 s0 N% m  |% N+ \7 R. d
[color=rgba(0, 0, 0, 0.749019607843137)]        //先动态开辟6个结点的空间6 \6 G$ u1 T5 ]1 i/ S3 Q# U1 n9 N
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));$ |2 O2 A3 ~- t
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n1);* S% J5 C. t7 L) W4 S
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));' I2 }7 P& Y7 ~& s& Z2 q
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n2);+ y" F- R) G# f9 k8 l2 V7 \
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));  a! C1 z" L0 H3 s
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n3);6 b& `/ u/ e  H- S( }
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));( u3 H- ~1 S& a
[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n4);
1 u& |: b/ O1 }% @[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
+ R( n5 k( |9 w. N[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n5);. N+ [% V7 d' W
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
# u. U/ F" H5 w% W" L7 q4 D[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n6);7 c% L  C/ U! e9 M0 l/ a! @4 q( L
[color=rgba(0, 0, 0, 0.749019607843137)]- C& v+ Z- _8 I. u! p

* c  I4 d, Z+ y7 [8 S9 T& ]- g7 D[color=rgba(0, 0, 0, 0.749019607843137)]        n1->data = 1;2 T) K- }9 B5 Z7 i- Z/ g
[color=rgba(0, 0, 0, 0.749019607843137)]        n2->data = 2;
; c' z% b  s+ r) n1 I) b[color=rgba(0, 0, 0, 0.749019607843137)]        n3->data = 3;( D- ?; R, x* L, E* V# l1 _+ u
[color=rgba(0, 0, 0, 0.749019607843137)]        n4->data = 4;  n" i: m, b  \' q3 {
[color=rgba(0, 0, 0, 0.749019607843137)]        n5->data = 5;* @5 j% B4 r* [8 g4 F/ [7 K3 E5 q
[color=rgba(0, 0, 0, 0.749019607843137)]        n6->data = 6;1 N4 H7 j; E, d2 `, q
[color=rgba(0, 0, 0, 0.749019607843137)]
6 B6 M7 l' w9 e& i0 U! }3 ?. G( d2 c" C
[color=rgba(0, 0, 0, 0.749019607843137)]        n1->left = n2;
3 s7 h) F! K+ r" j6 x# ?[color=rgba(0, 0, 0, 0.749019607843137)]        n1->right = n4;2 k) X# O3 i& |' f6 u7 m
[color=rgba(0, 0, 0, 0.749019607843137)]        n2->left = n3;
, g8 H7 a" L" e$ N" b[color=rgba(0, 0, 0, 0.749019607843137)]        n2->right = NULL;1 ~) D. B- Q" M- Z- j. I
[color=rgba(0, 0, 0, 0.749019607843137)]        n3->left = NULL;; I5 k8 |& v1 v5 |
[color=rgba(0, 0, 0, 0.749019607843137)]        n3->right = NULL;
! Z  l/ p5 b5 t) F. h2 g[color=rgba(0, 0, 0, 0.749019607843137)]        n4->left = n5;' [/ h8 M. A& {' a0 Y
[color=rgba(0, 0, 0, 0.749019607843137)]        n4->right = n6;0 k6 N. c% e( [3 x2 q4 Z
[color=rgba(0, 0, 0, 0.749019607843137)]        n5->left = NULL;
3 w/ H, u2 R' ^% @- {[color=rgba(0, 0, 0, 0.749019607843137)]        n5->right = NULL;( p4 P) X( g& f- w1 _' e
[color=rgba(0, 0, 0, 0.749019607843137)]        n6->left = NULL;6 ~/ {4 @9 W1 o5 G0 u
[color=rgba(0, 0, 0, 0.749019607843137)]        n6->right = NULL;+ A4 c, c/ D. I
[color=rgba(0, 0, 0, 0.749019607843137)]
" K& O3 H; F5 g" U: ]2 _; o6 r: d& R; _
[color=rgba(0, 0, 0, 0.749019607843137)]        return n1;
  U9 `. |; _: @; C7 Y7 p. }0 |( f. ^[color=rgba(0, 0, 0, 0.749019607843137)]}# W/ d9 k! P* _3 U$ }
[color=rgba(0, 0, 0, 0.749019607843137)]& E1 ?- o: U4 {1 w( ?. _
/ P  h; ^) a0 f% X8 E+ u  A
[color=rgba(0, 0, 0, 0.749019607843137)]int main()
% V2 U  Q/ w9 S0 r' S) I[color=rgba(0, 0, 0, 0.749019607843137)]{
* v' ]' h) b- p* ]  s3 K1 B/ `5 x: V! x[color=rgba(0, 0, 0, 0.749019607843137)]        //先创建一个简单的二叉树结构
- x- r! M( m: u[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* root = CreateTree();3 D( ~: {* l. M
[color=rgba(0, 0, 0, 0.749019607843137)]8 j* {) k8 F: Z9 c" J2 w/ _2 b

- R" T2 w/ |9 D7 @% {, w[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树前序遍历
. r& W8 i9 `4 @" h3 e, h4 l2 @[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树前序遍历:");
% ?. L, W/ {8 k& B, F2 r; }8 ^, U1 D[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root);
! n( n" e$ f, n$ {4 u[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
7 T* Y8 R* s' w1 X& M/ B[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树中序遍历
1 f, g# h, u" x7 k( ?/ V[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树中序序遍历:");
& H! q4 m7 I: `- F. B: w, r[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root);
, n6 v, W  n/ e7 i! O9 m[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
: N. {7 ]8 h# M[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树后序遍历
  \0 Z) y/ A. \, G[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树后序遍历:");% ^* ^7 z6 x5 n" _" ^
[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root);
9 ]6 n6 ]2 \4 e4 c[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
' k7 }  \, `4 I' N7 ^[color=rgba(0, 0, 0, 0.749019607843137)]$ \5 |1 I" ]0 Z4 @- M5 l, ~" z
+ S7 X+ W  n% a
[color=rgba(0, 0, 0, 0.749019607843137)]        return 0;: M0 t4 h  |# f+ {9 v7 Z- M6 {0 _
[color=rgba(0, 0, 0, 0.749019607843137)]}
; W3 K- ?) p2 j+ ^! |% t7 W" l[color=rgba(0, 0, 0, 0.749019607843137)]1
( V  l0 h3 L9 G2 C[color=rgba(0, 0, 0, 0.749019607843137)]2
. t6 k( `# ]& Z/ g" e[color=rgba(0, 0, 0, 0.749019607843137)]39 a' l" D2 x; ~& ?3 c7 \: m
[color=rgba(0, 0, 0, 0.749019607843137)]4! S  K0 B/ x9 }
[color=rgba(0, 0, 0, 0.749019607843137)]5
& ^7 {8 @" k  `1 ~[color=rgba(0, 0, 0, 0.749019607843137)]6. e: |8 M% K! w7 S
[color=rgba(0, 0, 0, 0.749019607843137)]7
9 v3 I0 B3 H% _2 ^$ {- a; i[color=rgba(0, 0, 0, 0.749019607843137)]8, T8 E! H4 i) \# ^8 O
[color=rgba(0, 0, 0, 0.749019607843137)]93 p: `) z; l. z* ^6 q" E/ F
[color=rgba(0, 0, 0, 0.749019607843137)]10
/ k( h# l# `) z$ a[color=rgba(0, 0, 0, 0.749019607843137)]11
) f5 h9 ]" a  r. G1 z( v4 z2 S0 i[color=rgba(0, 0, 0, 0.749019607843137)]12( n9 k' a) k8 ^5 Z% O
[color=rgba(0, 0, 0, 0.749019607843137)]13
* y" N4 m( h5 Z& l; c[color=rgba(0, 0, 0, 0.749019607843137)]14
# \4 r/ y1 s5 {( m+ X8 b% x3 J[color=rgba(0, 0, 0, 0.749019607843137)]15
0 V' f- p. q! @% [( w6 t6 C[color=rgba(0, 0, 0, 0.749019607843137)]16
1 @; h- _* E6 K+ Y8 d, m7 S; P[color=rgba(0, 0, 0, 0.749019607843137)]17. i, ]: S$ r% J' D: ~2 Z+ j  Y
[color=rgba(0, 0, 0, 0.749019607843137)]18
, P8 E# T! T2 T+ l[color=rgba(0, 0, 0, 0.749019607843137)]19/ w$ A1 b# F; o, E+ F6 z
[color=rgba(0, 0, 0, 0.749019607843137)]20
% w' D+ T: W# x6 r& T3 s[color=rgba(0, 0, 0, 0.749019607843137)]21( }7 j- X9 {" L
[color=rgba(0, 0, 0, 0.749019607843137)]229 }# k7 l" l$ f; F' ]' O6 a! a
[color=rgba(0, 0, 0, 0.749019607843137)]23
* E% o5 e0 D- T6 E/ b+ k[color=rgba(0, 0, 0, 0.749019607843137)]24/ m( m4 _3 O' F; X: N" T% f
[color=rgba(0, 0, 0, 0.749019607843137)]25& i4 P. l- o: r7 ^% q# v
[color=rgba(0, 0, 0, 0.749019607843137)]26- w. d$ L8 k5 W4 A
[color=rgba(0, 0, 0, 0.749019607843137)]27
: U2 v, j/ b, K+ u# b$ O[color=rgba(0, 0, 0, 0.749019607843137)]28
6 G2 e. ^. M  b  c  ~[color=rgba(0, 0, 0, 0.749019607843137)]298 a( w: \6 d  g1 s
[color=rgba(0, 0, 0, 0.749019607843137)]30
$ S, z+ R: d9 ]- M[color=rgba(0, 0, 0, 0.749019607843137)]31
- a: n0 X  H( B1 @[color=rgba(0, 0, 0, 0.749019607843137)]32
  X. @+ `" K2 Y0 Y  ^[color=rgba(0, 0, 0, 0.749019607843137)]33: t' u6 Y6 _$ T7 u
[color=rgba(0, 0, 0, 0.749019607843137)]34
- z( @& F" D) |& b; u$ m& H[color=rgba(0, 0, 0, 0.749019607843137)]35- i  o5 @/ ~" x2 ~* \
[color=rgba(0, 0, 0, 0.749019607843137)]36
( E9 q7 |$ [6 X, ^3 L  U[color=rgba(0, 0, 0, 0.749019607843137)]37; x$ P0 b; G/ `- t7 r
[color=rgba(0, 0, 0, 0.749019607843137)]38
$ l# l- |/ c" ^, @[color=rgba(0, 0, 0, 0.749019607843137)]39: {3 F  D4 n# ?0 a% @* D
[color=rgba(0, 0, 0, 0.749019607843137)]40
, f! ^# s6 D: J[color=rgba(0, 0, 0, 0.749019607843137)]41
$ B9 W' B  j9 i9 P  ^+ |[color=rgba(0, 0, 0, 0.749019607843137)]42/ ]8 e; g- H; n0 C$ ^5 B
[color=rgba(0, 0, 0, 0.749019607843137)]43
% [5 W8 j' M7 U* F; H[color=rgba(0, 0, 0, 0.749019607843137)]44! V9 J/ X; T: D1 i
[color=rgba(0, 0, 0, 0.749019607843137)]45
0 D: |" K2 G% P- i! D[color=rgba(0, 0, 0, 0.749019607843137)]46
% h1 Y% I4 C6 E+ }( k4 \[color=rgba(0, 0, 0, 0.749019607843137)]47
- b" @/ N4 t2 w9 n[color=rgba(0, 0, 0, 0.749019607843137)]48; E8 t: v7 P5 M/ w; _' E
[color=rgba(0, 0, 0, 0.749019607843137)]49
9 C$ M+ m% c: E[color=rgba(0, 0, 0, 0.749019607843137)]50
' {3 a; h! k+ D[color=rgba(0, 0, 0, 0.749019607843137)]51
6 c4 U2 I) q% Y) L[color=rgba(0, 0, 0, 0.749019607843137)]52
  Y, j( p3 b$ J& y7 z[color=rgba(0, 0, 0, 0.749019607843137)]536 r) T. B( g2 p: A4 h; L- \* j7 P
[color=rgba(0, 0, 0, 0.749019607843137)]54% j! R$ f" R4 e: M
[color=rgba(0, 0, 0, 0.749019607843137)]557 _2 q, V. F- I# b
[color=rgba(0, 0, 0, 0.749019607843137)]56
" v& ]3 v' Z# u, C+ z6 f7 L[color=rgba(0, 0, 0, 0.749019607843137)]574 m4 F: ^3 ^3 r' Z, {3 z
[color=rgba(0, 0, 0, 0.749019607843137)]58
. ]9 }; z% Y! l* u, N2 i2 V. X3 z[color=rgba(0, 0, 0, 0.749019607843137)]59
# P* }) g/ g3 [& r9 n5 ^1 \& c[color=rgba(0, 0, 0, 0.749019607843137)]60
: m- P% Q; E& u, _[color=rgba(0, 0, 0, 0.749019607843137)]61
4 h- _3 R1 X9 e% q6 m8 l[color=rgba(0, 0, 0, 0.749019607843137)]625 S( K) d: J6 {% @
[color=rgba(0, 0, 0, 0.749019607843137)]63
5 u; i( ~+ B7 Q# c- S$ ^2 J5 A6 q[color=rgba(0, 0, 0, 0.749019607843137)]64& w% N9 \& ~' B+ W  g+ i
[color=rgba(0, 0, 0, 0.749019607843137)]65; J8 x7 T  H, ~5 X
[color=rgba(0, 0, 0, 0.749019607843137)]66
& X# Y' v4 n* O# Q; t[color=rgba(0, 0, 0, 0.749019607843137)]67
* K, J/ q: k; h( L[color=rgba(0, 0, 0, 0.749019607843137)]68$ N2 R7 v& A+ L5 {; x1 p, K: L* I
[color=rgba(0, 0, 0, 0.749019607843137)]69
- M. c% Q' M" H. F: v[color=rgba(0, 0, 0, 0.749019607843137)]70. a' D' \6 O/ l3 }
[color=rgba(0, 0, 0, 0.749019607843137)]716 {, c  D8 V6 S+ V
[color=rgba(0, 0, 0, 0.749019607843137)]72  Y* G) c* q$ K. K/ i' a
[color=rgba(0, 0, 0, 0.749019607843137)]734 @/ |1 p  G8 U; [4 n3 ?
[color=rgba(0, 0, 0, 0.749019607843137)]741 g- @# q) k7 g3 t7 |
[color=rgba(0, 0, 0, 0.749019607843137)]75
$ N! U8 }. K# U" ~9 u8 I$ K# y[color=rgba(0, 0, 0, 0.749019607843137)]76
& k: l8 {+ \9 G9 ^( e[color=rgba(0, 0, 0, 0.749019607843137)]77
" E1 s! A( L0 X! [4 r0 V4 r8 I[color=rgba(0, 0, 0, 0.749019607843137)]78
6 c' Z/ E! K' X7 U  m) D3 x) t[color=rgba(0, 0, 0, 0.749019607843137)]79
, j/ u; O$ t! U1 _5 K% t[color=rgba(0, 0, 0, 0.749019607843137)]805 l( O& _( k  b( i, X
[color=rgba(0, 0, 0, 0.749019607843137)]81. {* ~7 M, b6 i; P  z: O
[color=rgba(0, 0, 0, 0.749019607843137)]82' U7 O1 f8 e7 t( l3 |4 c6 p- b9 l/ R" N
[color=rgba(0, 0, 0, 0.749019607843137)]83( v! V+ y8 Q( m$ \; F4 S, ~
[color=rgba(0, 0, 0, 0.749019607843137)]84
, K3 f3 y  y( a1 R3 w. @[color=rgba(0, 0, 0, 0.749019607843137)]855 l1 \9 r9 X0 |! D. ^0 o) E
[color=rgba(0, 0, 0, 0.749019607843137)]86' T4 W8 }9 a2 P9 d5 ?7 K
[color=rgba(0, 0, 0, 0.749019607843137)]874 P8 H8 I* z% z
[color=rgba(0, 0, 0, 0.749019607843137)]88
/ {, q! @2 z3 b$ Y0 n8 a; g[color=rgba(0, 0, 0, 0.749019607843137)]89
0 z1 i+ ~, t6 d[color=rgba(0, 0, 0, 0.749019607843137)]90' q6 J$ g8 L6 Q3 h
[color=rgba(0, 0, 0, 0.749019607843137)]91
9 ?* y. O) g6 E3 o[color=rgba(0, 0, 0, 0.749019607843137)]92
/ _  y; `' b  d1 K[color=rgba(0, 0, 0, 0.749019607843137)]931 F) ]1 a- z7 h0 s7 }
[color=rgba(0, 0, 0, 0.749019607843137)]94
' \  \/ d2 y& o2 x4 G. r[color=rgba(0, 0, 0, 0.749019607843137)]95
  V7 G% P) y- ^/ C! r8 ?, p[color=rgba(0, 0, 0, 0.749019607843137)]96$ X, M; ~/ F# P& y0 Y' |: ]
[color=rgba(0, 0, 0, 0.749019607843137)]97
$ ~0 B3 K% Y9 Y: U[color=rgba(0, 0, 0, 0.749019607843137)]98
2 D  d) j$ L. z[color=rgba(0, 0, 0, 0.749019607843137)]99
* O" E& d6 n) _5 e[color=rgba(0, 0, 0, 0.749019607843137)]100* M* N  X) z' @) f3 Y# e: ~
[color=rgba(0, 0, 0, 0.749019607843137)]101
, H. t' F- k$ B/ X8 h& m1 q[color=rgba(0, 0, 0, 0.749019607843137)]102
: h$ k+ W' M8 S9 T, N[color=rgba(0, 0, 0, 0.749019607843137)]103
4 Q( E$ C5 c4 Z' _! H  h[color=rgba(0, 0, 0, 0.749019607843137)]104
" |/ _8 {* v  D. |. C% I1 A+ S[color=rgba(0, 0, 0, 0.749019607843137)]105- |% Z- u1 i4 Z7 W
[color=rgba(0, 0, 0, 0.749019607843137)]1065 s6 b" r" i) D1 g3 y
[color=rgba(0, 0, 0, 0.749019607843137)]107- Y6 `% b* p3 u: o  W
[color=rgba(0, 0, 0, 0.749019607843137)]108
) w/ y6 ]2 w& ~# l; m' y[color=rgba(0, 0, 0, 0.749019607843137)]109
/ Q* Q. F0 a5 E[color=rgba(0, 0, 0, 0.749019607843137)]1103 H5 G& I: \9 y  z2 i- G& Y
[color=rgba(0, 0, 0, 0.749019607843137)]111# C4 ~0 B% p$ S1 C* g( U
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
+ U, O: I( E' D[color=rgba(0, 0, 0, 0.749019607843137)]. D3 S; Y4 @. D" v5 h" N, d5 G3 V' n
% v& }! ?4 p9 V: |0 I7 O, [
[color=rgba(0, 0, 0, 0.749019607843137)]1 ^4 A" z- e3 l; F

* f2 j# p5 G& `; A: |[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小3 h9 g) s3 \  Z
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
- r8 W1 h: |0 g6 V5 ~5 \- W% J: T[color=rgba(0, 0, 0, 0.749019607843137)]) u* g0 O# y/ u' k! E/ p$ k( z# `
6 D% _- h) f( |$ r  k* A( z
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
' B8 c5 ?0 `  d/ P+ a[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量" B- s0 W- N% o
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
+ T3 O. M% q1 H' v" d0 G: l( O[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
" B' ]( O$ C; r2 {! o" H* @[color=rgba(0, 0, 0, 0.749019607843137)]//{
) `3 A; ^/ F8 U8 u* x[color=rgba(0, 0, 0, 0.749019607843137)]//        if (root == NULL)
$ h6 D- z# Y- E8 T9 |! ~. `9 b3 V[color=rgba(0, 0, 0, 0.749019607843137)]//        {
8 i5 K7 o8 L: B) V' V* [! m[color=rgba(0, 0, 0, 0.749019607843137)]//                return;6 V  j6 W( z8 `/ u
[color=rgba(0, 0, 0, 0.749019607843137)]//        }% R/ J$ Z3 h! ~$ h& h/ m
[color=rgba(0, 0, 0, 0.749019607843137)]//        count++;
3 `4 [/ Z. f7 y1 w* ]; Y. ]) t; D[color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->left);
5 p: M' n1 \5 M) L[color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->right);) t# r" q# G& S8 C& v6 H* W6 s
[color=rgba(0, 0, 0, 0.749019607843137)]//( s. B* K- e; E+ C
[color=rgba(0, 0, 0, 0.749019607843137)]//        return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量7 w% f( }! g3 a3 ~% K: O  i( A5 P
[color=rgba(0, 0, 0, 0.749019607843137)]//}
! V: h3 X- s' a6 l: j3 R( p. U! M3 r[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之1 o, Q+ k+ i. o0 I
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)' @  w: w) t( e9 M7 ?0 F& L
[color=rgba(0, 0, 0, 0.749019607843137)]{
$ N! S  X" |& L  ?[color=rgba(0, 0, 0, 0.749019607843137)]        return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;, [6 ?# r  e. U6 J8 P+ U! F
[color=rgba(0, 0, 0, 0.749019607843137)]}
2 Y: ^/ O4 N1 n$ M! f4 M[color=rgba(0, 0, 0, 0.749019607843137)]1
! G9 b' V% q1 u; N[color=rgba(0, 0, 0, 0.749019607843137)]2
7 W; h" _, m: k& {/ L7 J[color=rgba(0, 0, 0, 0.749019607843137)]3
# p/ x/ Q9 ?+ e4 ?2 ~' a[color=rgba(0, 0, 0, 0.749019607843137)]42 y4 R& z; y( E+ c5 R9 K& o9 o
[color=rgba(0, 0, 0, 0.749019607843137)]5
* A  M$ s9 u  Q* g[color=rgba(0, 0, 0, 0.749019607843137)]6
" K8 }0 \# c9 r0 n/ ]8 H. z[color=rgba(0, 0, 0, 0.749019607843137)]7
% N7 W/ J1 V7 V! }! t$ r6 o[color=rgba(0, 0, 0, 0.749019607843137)]8$ p& }! Z7 u  l9 o' a3 x
[color=rgba(0, 0, 0, 0.749019607843137)]9
7 Y* n: O& K  q9 i+ ~[color=rgba(0, 0, 0, 0.749019607843137)]10+ b% Q4 D& w+ n0 D
[color=rgba(0, 0, 0, 0.749019607843137)]11, O2 e  [8 l9 q6 U; h1 E
[color=rgba(0, 0, 0, 0.749019607843137)]12
+ D# c. H2 d, {[color=rgba(0, 0, 0, 0.749019607843137)]13
* ]5 d5 m2 M1 |* A[color=rgba(0, 0, 0, 0.749019607843137)]142 B/ T/ q) p9 N, d4 {
[color=rgba(0, 0, 0, 0.749019607843137)]15
# g" a+ X' f1 ^8 O[color=rgba(0, 0, 0, 0.749019607843137)]16
' C- g! a2 _# @! B2 \[color=rgba(0, 0, 0, 0.749019607843137)]17. }2 i/ S6 J2 @9 @% [
[color=rgba(0, 0, 0, 0.749019607843137)]18
' c" k0 N4 S$ i[color=rgba(0, 0, 0, 0.749019607843137)]19
2 Z) r7 r, U  t. w0 M- M( B[color=rgba(0, 0, 0, 0.749019607843137)]20
: w2 B4 x% O4 w7 |" Z; l[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
8 a# {& o- _  `2 C4 ]) B( ][color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数
+ E# _% L2 i* }0 b% \[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)3 s" R8 J6 q* H( _+ s+ \# f! |
[color=rgba(0, 0, 0, 0.749019607843137)]{3 ^+ _7 l+ B5 m. g; T0 a
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)//首先得考虑空树的情况,0个叶子结点
9 V% X2 d5 L- O0 Y+ p$ F+ @' ][color=rgba(0, 0, 0, 0.749019607843137)]        {: G! l+ e8 d2 N0 g
[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;
8 j$ U, e2 s3 q7 H6 g( v[color=rgba(0, 0, 0, 0.749019607843137)]        }1 s6 s# |* U* t
[color=rgba(0, 0, 0, 0.749019607843137)]        //叶子结点的特征就是左右子树为空
: u7 Z% v8 h7 V# F5 x3 G[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->left == NULL && root->right == NULL)! o5 O' P/ m$ b/ @: ]  N. R% o
[color=rgba(0, 0, 0, 0.749019607843137)]        {
' G0 [& g6 l% [[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;9 j8 _7 g. Q3 Y
[color=rgba(0, 0, 0, 0.749019607843137)]        }
9 o. V% e* s7 k+ T; o. l[color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLeafSize(root->left) + TreeLeafSize(root->right);
! i# h* w9 T0 t+ W" k[color=rgba(0, 0, 0, 0.749019607843137)]}( @  U& b4 K( o5 b7 i
[color=rgba(0, 0, 0, 0.749019607843137)]1* U0 P: W; F& U
[color=rgba(0, 0, 0, 0.749019607843137)]2
7 k/ c2 D3 b( L" o+ ]7 L0 a[color=rgba(0, 0, 0, 0.749019607843137)]3
9 B! j5 N# v$ H[color=rgba(0, 0, 0, 0.749019607843137)]4
& a5 w' N+ I/ M$ H9 Y[color=rgba(0, 0, 0, 0.749019607843137)]5
$ O) a' h4 c3 W- B[color=rgba(0, 0, 0, 0.749019607843137)]6
& o( D4 l  s$ E/ M7 h  L7 S3 ~[color=rgba(0, 0, 0, 0.749019607843137)]7
3 m* {7 Z- w  P0 i[color=rgba(0, 0, 0, 0.749019607843137)]8
) ~0 f  t  t3 X# z( W[color=rgba(0, 0, 0, 0.749019607843137)]9& n( L1 r0 z1 ]; F1 q# P
[color=rgba(0, 0, 0, 0.749019607843137)]10  ]- Z; g0 A% U. x+ M
[color=rgba(0, 0, 0, 0.749019607843137)]11: J7 E. o4 D7 I
[color=rgba(0, 0, 0, 0.749019607843137)]12
  R, W6 L3 U# n* |; O  h, m[color=rgba(0, 0, 0, 0.749019607843137)]13
2 E3 Q9 U1 R! Z: }: p[color=rgba(0, 0, 0, 0.749019607843137)]14) S$ l7 J0 C6 c, |. f; V+ k6 `
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度9 E% y# h8 ~* v' x, Y4 w1 Z. Q
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
% R' r) q. ]; l9 p[color=rgba(0, 0, 0, 0.749019607843137)]{" S$ X- }" u/ y7 d! Z4 I
[color=rgba(0, 0, 0, 0.749019607843137)]        //空树高度为0
+ `6 e9 L" `' N1 Q2 B7 z% Q[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
1 q5 S6 r) o4 H. {[color=rgba(0, 0, 0, 0.749019607843137)]        {
( E2 R9 j/ U& Z  A) T" V9 M[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;3 _4 r2 I, u4 N- P4 j- s
[color=rgba(0, 0, 0, 0.749019607843137)]        }
8 ^* }% F, C! _9 ^& H) W3 k5 s# X[color=rgba(0, 0, 0, 0.749019607843137)]        //树的高度是较高的那棵子树7 m" S  e' @8 D# f  D6 R
[color=rgba(0, 0, 0, 0.749019607843137)]        int lh = TreeHeight(root->left);//左子树的高度2 L! f, p- `1 H
[color=rgba(0, 0, 0, 0.749019607843137)]        int rh = TreeHeight(root->right);//右子树的高度. K; h$ B6 u; J& @2 e. b7 r
[color=rgba(0, 0, 0, 0.749019607843137)]8 Q+ `/ Y+ n* W4 p# j
8 N: @2 v5 P) r2 Z# I0 V' N( n! A
[color=rgba(0, 0, 0, 0.749019607843137)]        return lh > rh ? lh + 1 : rh + 1;, l0 @) g5 \- y
[color=rgba(0, 0, 0, 0.749019607843137)]}1 z+ n0 ?9 T  [" W; ?+ Q) k0 [
[color=rgba(0, 0, 0, 0.749019607843137)]1- U' n- q, \, a+ p  N
[color=rgba(0, 0, 0, 0.749019607843137)]2) a, k- g9 v2 \5 g7 v7 b; u6 l
[color=rgba(0, 0, 0, 0.749019607843137)]36 C! b9 M- r  Y
[color=rgba(0, 0, 0, 0.749019607843137)]4/ f9 n% I7 ~8 q( @1 Y3 z$ z& E
[color=rgba(0, 0, 0, 0.749019607843137)]52 n) S+ {, ?6 }8 x9 n; e
[color=rgba(0, 0, 0, 0.749019607843137)]6
2 e" Z5 Q. y! y& ]2 ]) @( L1 ~[color=rgba(0, 0, 0, 0.749019607843137)]78 Q: ~8 Z* [9 M; g! }( c
[color=rgba(0, 0, 0, 0.749019607843137)]8
2 G5 m2 S3 z, A( u. q[color=rgba(0, 0, 0, 0.749019607843137)]9. @! A3 p6 u4 }
[color=rgba(0, 0, 0, 0.749019607843137)]10
7 G- N* j6 f: S* J# I/ D' q! \/ C# r8 X[color=rgba(0, 0, 0, 0.749019607843137)]11
0 T; R. ^5 g& q) j+ O[color=rgba(0, 0, 0, 0.749019607843137)]12' k) ~4 N! F2 ]3 D2 p
[color=rgba(0, 0, 0, 0.749019607843137)]13# d- B% |+ j+ s, R
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数" z' p; M# A7 D: n6 j* g" v
[color=rgba(0, 0, 0, 0.749019607843137)]
. x0 O% K" \# B( ^% D) G* b- S/ D/ o; D- G0 t
[color=rgba(0, 0, 0, 0.749019607843137)]$ @' g5 G! i4 `
0 ]; x  X: @; ]& x! Q# M3 N
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
% X- J" `! p& k[color=rgba(0, 0, 0, 0.749019607843137)]
! @! V3 k9 J7 q# B9 R2 ~* o" z# W& l* x2 h' ?9 Y1 U/ y
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数5 T" b& I1 F* C6 P
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
1 Q7 ^; C9 |0 \5 Z[color=rgba(0, 0, 0, 0.749019607843137)]{
, ], C/ D5 a5 K7 L; G# w3 P[color=rgba(0, 0, 0, 0.749019607843137)]        assert(K > 0);
5 C- ~) D; f& Z& O: {[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
" @9 B; O  p8 l* G[color=rgba(0, 0, 0, 0.749019607843137)]        {6 [8 X# g) h8 [8 H) m* c( y" q
[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;0 m4 U. W/ p* |
[color=rgba(0, 0, 0, 0.749019607843137)]        }
/ E! V6 B, v6 U2 R8 [[color=rgba(0, 0, 0, 0.749019607843137)]        //如果是第一层(递归出口); Y0 n2 i9 G+ o$ q* V' w) @
[color=rgba(0, 0, 0, 0.749019607843137)]        if (K == 1)
! r' I8 i: j3 n[color=rgba(0, 0, 0, 0.749019607843137)]        {
: \! j, O1 z' x: h- p  U9 ^[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;
- E0 w" ^: a0 f[color=rgba(0, 0, 0, 0.749019607843137)]        }
& c, Q7 Y. k0 J: O[color=rgba(0, 0, 0, 0.749019607843137)]        //转换成子树的第K-1层) |2 S* l, m  G8 @& X8 ~
[color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
! J, t1 `  u  G2 J6 ~[color=rgba(0, 0, 0, 0.749019607843137)]}
6 g7 n" F9 Q. V9 j5 R[color=rgba(0, 0, 0, 0.749019607843137)]1
5 U+ F6 g$ Z$ _0 F1 v4 n: t[color=rgba(0, 0, 0, 0.749019607843137)]2
+ e  H' \5 G' v, E( X[color=rgba(0, 0, 0, 0.749019607843137)]33 G" m: \1 h9 g
[color=rgba(0, 0, 0, 0.749019607843137)]4% H5 Q4 x' y6 o
[color=rgba(0, 0, 0, 0.749019607843137)]5% }7 V/ L6 U; V; |. m, J  d& H5 B
[color=rgba(0, 0, 0, 0.749019607843137)]6
; h3 z) x) }+ M( H[color=rgba(0, 0, 0, 0.749019607843137)]7
1 r7 b3 q7 h4 b) A[color=rgba(0, 0, 0, 0.749019607843137)]8. P. M+ F( k5 k" U0 \0 |7 D! D
[color=rgba(0, 0, 0, 0.749019607843137)]9
. }1 O( k3 p# o/ t0 i  T5 S# ?[color=rgba(0, 0, 0, 0.749019607843137)]10
- x2 G7 W4 n6 O7 h[color=rgba(0, 0, 0, 0.749019607843137)]11
5 n2 K8 A/ n! z( n[color=rgba(0, 0, 0, 0.749019607843137)]12
+ R3 n8 }% \, V. q# o[color=rgba(0, 0, 0, 0.749019607843137)]13% h4 a1 m+ `9 K" P) o1 b6 J3 g* i
[color=rgba(0, 0, 0, 0.749019607843137)]14
* [1 s+ J/ b/ `+ k6 z[color=rgba(0, 0, 0, 0.749019607843137)]15& z' J: l' Z" \
[color=rgba(0, 0, 0, 0.749019607843137)]16
, e: f/ j* F$ @5 b[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
! k4 a' B& ^" A[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
3 `0 z3 k3 h7 T" I0 v[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
! W0 l6 b7 h! V# ]1 ~9 H: l% P[color=rgba(0, 0, 0, 0.749019607843137)]{) k; s* ?5 y  v* ~
[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
6 R4 m$ V! b5 K8 H+ n, v  q[color=rgba(0, 0, 0, 0.749019607843137)]        {! s$ p' h* l6 m7 x+ \8 N; u/ l
[color=rgba(0, 0, 0, 0.749019607843137)]                return NULL;
& z3 ?3 ~* u6 i" s5 H& l; @[color=rgba(0, 0, 0, 0.749019607843137)]        }
6 L$ b3 |3 U. W3 _, a[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->data == data)1 _( ]/ ?, p. ^' T- |! a
[color=rgba(0, 0, 0, 0.749019607843137)]        {
+ B' a9 w7 ^, f0 |- }! E[color=rgba(0, 0, 0, 0.749019607843137)]                return root;% D( S$ h) _# J! z; \4 z
[color=rgba(0, 0, 0, 0.749019607843137)]        }0 z$ r& |' U9 m& j( ]# J  d
[color=rgba(0, 0, 0, 0.749019607843137)]        //先查找左子树
- ]0 L+ X$ R7 P* P, L# D; I; ^[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* lret = TreeFind(root->left, data);/ M. R5 X8 T& N# q2 E8 ]/ Q+ S
[color=rgba(0, 0, 0, 0.749019607843137)]        if (lret)
, W; l/ z  f/ v3 S[color=rgba(0, 0, 0, 0.749019607843137)]                return lret;
! F+ G4 f' m2 |. a[color=rgba(0, 0, 0, 0.749019607843137)]        //再查找右子树  F% U, Y1 A- y! I
[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* rret = TreeFind(root->right, data);
- u' i9 D; Z1 ]3 J  S& O$ ^[color=rgba(0, 0, 0, 0.749019607843137)]        if (rret), f" N9 M0 R* L9 z$ I( r
[color=rgba(0, 0, 0, 0.749019607843137)]                return rret;9 {( M% R# A0 w7 A; L8 c
[color=rgba(0, 0, 0, 0.749019607843137)]        return NULL;
* A& t& K; s: e$ Z/ n[color=rgba(0, 0, 0, 0.749019607843137)]}
5 M+ E& `) _  W[color=rgba(0, 0, 0, 0.749019607843137)]————————————————, s: m3 t& r, v" v
[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。+ q  Z& v$ v7 _" r* A1 w+ f4 G
[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
# X+ J, T) v5 t
- ?+ I" n  M( U: M- h. A2 m0 j, R  d* m8 @
[color=rgba(0, 0, 0, 0.75)]
, Y! Z% N* s/ b% g( F2 H1 [% r' \" B, o9 `6 q
+ \  x7 v2 |( F, X8 K  w& S
: O! j. S  p, J




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5