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