求树的节点个数求法，求助啊！！！

qiandongdong

求树的节点个数的求法啊或matlab代码，我是新手，真心编了好久没结果。请前辈们帮帮忙啊~

madio

就是一个遍历树的所有节点的算法，我帮你找到一个

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   ( a. w  _' c( _3 d
2.        tree_nodename：节点名字或序号
   4 @. |, t1 j5 O
3.        tree_nodevalue：节点对应的值
   * ?9 q; s\" n- h/ f4 Y0 x. W: U+ _
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   / S  {8 X! H7 L) h
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   3 G6 p0 L: {) L, p- }1 N2 _
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空0 P/ F- k1 U3 i. @, o: z( l. C
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。0 Q( a% ^' ]& [8 Z) Q5 ^- H
   
8. 
   ! E0 B  l3 i8 d. x\" I2 ?# W
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   0 l% O# P; _  g* k  X4 h' M
10. . n\" I- b1 z# Y% B6 j/ ^7 D1 D
    
11.        %matlab源程序
    4 K, L8 I$ a% V4 v+ T7 z
12.        %输入：树的深度、树的广度、搜索的值
    $ a2 t. `) G( i. L8 b! ~
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
      |# r8 p\" R% J& ^) E
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)8 F& Y; d5 q# h
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数1 j! P! D! x& l
    
16.        node_num = 0;
    ; Q% }' B1 c3 M% z5 i3 L4 _4 S6 t
17.        for n= 0 : (tree_depth-1)
    2 @) V0 \& K, t\" V
18.               node_num = node_num + tree_width ^ n;
    . k6 D2 B0 x' l
19.        end
    ) ]8 @& V/ P0 E5 ~
20. 
    ( Q: W. v! v, H; R' N3 J0 o$ u
21.        %为树的存储空间赋值
    5 a' e# _\" l/ H/ ?. W  e6 M
22.        %node name，按照广度优先为节点排号
    8 |5 ~* X  U$ l3 m$ _
23.        tree_nodename = (1 : node_num);
    / g! s% ]4 f$ @: d4 \
24.        %node value3 N& G( r$ O! o# {6 {
    
25.        tree_nodevalue = rand(1 : node_num);6 w! R0 R  _) ?4 A; Y$ L
    
26.        %node father and son
    ( N5 [2 e& R6 J5 Q% s7 g6 E
27.        tree_nodefather(1) = 0;
    4 {# @$ X) m1 a7 {5 }8 U
28.        tree_nodeson = zeros(1, node_num);
    ! o! u) U0 u! A! ~1 C
29.        n = 2;
    , V5 X& G$ a. s* U) E
30.        k = 1;4 z; o$ |, G- Z
    
31.        while n <= node_num
    0 p) D0 E/ T/ f4 N1 j$ k\" H. T1 @, h
32.               for m = 1 : tree_width
    8 x9 L( f) i4 w$ R/ r7 [
33.                      tree_nodefather(n) = k;
    ' t8 |2 _4 y; }  e
34.                      if m==15 T; d\" m: U* P+ j* m& I
    
35.                             tree_nodeson(k) = n;! v: a, J4 c9 ?) {4 J# k
    
36.                      end\" Q2 s/ k1 w2 N. k+ a( ]2 e3 S
    
37.                      n = n + 1;. l% i- a) }. y0 Y\" m: n3 ^& y
    
38.               end& V/ c, `& ~' q+ F- x( k) M! n8 J. c
    
39.               k = k + 1;
    / C\" N  B5 Y  L/ P+ j2 ~2 H
40.        end
    + j: g* W2 Z5 f, t, l( g$ y
41.        %node neighbor
    . a+ F- G% U# y
42.        tree_nodeneighbor(1) = 0;
    5 }6 u% ~- i% f' F6 _1 V8 ?
43.        n = 2;
    ( J* X4 h* z. h3 ~5 J
44.        while n <= node_num
      b; V/ N) D! R+ h# I+ P2 A1 \) v+ p
45.               for m = 1 : tree_width
    # D/ q. q1 \  K8 K6 L
46.                      if m ==tree_width
    % W. }3 J7 s/ I
47.                             tree_nodeneighbor(n) = 0;( @( O4 @9 o\" T0 Z( X
    
48.                      else* z5 w, w  L( g# @
    
49.                             tree_nodeneighbor(n) = n + 1;
    / A: k% B4 c9 e( O  ~  i3 R6 @; O5 i9 a
50.                      end- l% ~+ ?/ |+ _8 W2 r( {
    
51.                      n = n + 1;
    1 z0 D2 l8 m: d5 C/ k) v7 k0 d
52.               end
    / o/ D' X- S6 j; `! s
53.        end
    $ R; z& j) U\" e) w4 }+ L
54. , P) L! g; ~1 g1 v
    
55.        %下面是有效程序段，用栈实现
    \" `4 ?, e/ A& j2 N+ [( r
56.        stack = zeros(1, tree_depth);/ Y/ x# w( Y6 l# y5 ?3 |5 e4 t/ H/ _
    
57.        nodeinstack = zeros(1, node_num);
    0 w: w- l! L) }+ g- \( s
58.        stack_ptr = 1;- x$ b5 d5 b1 Q9 r
    
59.        stack(1) = 1;\" e# l9 u9 W9 w( s- n
    
60.        nodeinstack(1) = 1;! x9 f$ b% {\" `& m1 u0 A
    
61.        valueintree = seek_value;& K3 v/ v* G- c0 P& S- A
    
62.        nodeintree = 0;
    , r0 Y1 K: G( B6 t0 A$ o3 d) c
63. 
    \" D1 e) H- S( k
64.        while stack_ptr > 0/ C$ U) O9 W6 T\" q9 m+ C
    
65.               n = stack(stack_ptr);
    ' B7 l4 p, k3 P* Q& ]1 e+ {6 b4 t
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3! o7 V0 N$ O+ Q( H1 q& {
    
67.               %如果搜索到值，返回
    2 E$ w1 o8 G9 D2 t( b) r; d
68.                      valueintree = tree_nodevalue(n);8 B$ Y\" w\" P. E
    
69.                      nodeintree = tree_nodename(n);
    6 j( `# ?6 v: b2 x; \
70.                      break;, d  _* S. n2 G: I  h# L
    
71.               end
    6 @9 H: A% }* ~3 z$ g
72. 5 [/ W, K8 @9 [0 G4 W( P9 _8 r
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    / [# S6 d9 ^' j: I% i$ t7 ^# |+ ~
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈, m5 g8 S, ?+ Z& ?; A6 Q
    
75.                      stack_ptr = stack_ptr + 1;
    $ p: E6 B( N$ o; V
76.                      m = tree_nodeson(n);
    4 A, t$ Y( t, {
77.                      stack(stack_ptr) = m;1 x' ?. Q% S# R1 y
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    5 e2 y/ Q1 u* [- c: I0 V  U4 g% h
79.               elseif tree_nodeneighbor(n) ~= 0
    2 @: G( m  ?+ ~
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈/ T# v; N& _) m- Z9 B& B) v/ K
    
81.                      m = tree_nodeneighbor(n);
    $ g- _  T) k4 L! U6 t; J: A3 ^3 B
82.                      stack(stack_ptr) = m;
    ! G# C7 |! F, u6 f, B1 M
83.                      nodeinstack(m) = nodeinstack(m) + 1;' J# g$ P/ a. B2 I6 P4 `
    
84.               else
    4 A3 U- n4 c8 {
85.               %再否则，出栈，然后将父亲节点的入栈次数加一& l\" x. V0 ^' V3 u7 P6 ]3 H
    
86.                      stack_ptr = stack_ptr - 1;
    - ]\" ~3 _1 m$ e. m- p
87.                      m = stack(stack_ptr);
    \" i$ W/ o; B4 u5 I+ g  @2 ]
88.                      nodeinstack(m) = nodeinstack(m) + 1;5 S7 d$ ?) `/ c: }8 |! b6 E: v
    
89.               end: O( Y7 i  W8 Q; E
    
90.        end

复制代码