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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
     m4 i# Y, D( {
2.        tree_nodename：节点名字或序号
   6 G* R& ]! m, \! _. c% T( T
3.        tree_nodevalue：节点对应的值4 H- W7 e. |+ F3 ~
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空\" Z; T. s4 x\" m
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空$ A: V. S0 W1 l; o, f
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   7 @0 j$ E- b4 o\" M4 g  b
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。( f1 w  Q1 M( G$ m( _  c0 Z! H  f
   
8. ! A\" h5 c4 `& W; }: e4 I# @\" D
   
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。3 h4 ~! a/ Z; b) R5 V
   
10. 
    3 r\" }7 D8 _! {& T7 j+ l5 b6 T
11.        %matlab源程序
    * i( |/ u6 z) O1 p2 I% p1 }
12.        %输入：树的深度、树的广度、搜索的值
    ' i/ r* `4 n3 N4 ~
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    ( A1 p6 r, S1 i4 p  D\" G
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    , b, P6 b/ b& s! Q) h* o
15.        %根据树的深度、节点的儿子数量计算树总的节点个数% [5 K+ w* U# T8 b  o* x
    
16.        node_num = 0;+ z0 `0 O2 B+ s+ l# J\" w& m4 s
    
17.        for n= 0 : (tree_depth-1)
      W0 `& n( z1 d- c, C& P1 W: @! J
18.               node_num = node_num + tree_width ^ n;; j/ }: B/ R$ t2 f+ d
    
19.        end5 a; X) H# S; D# Z+ a- P8 r
    
20. 
    / a\" ?4 ]# R( w* ]+ ~( V) R/ s1 f, X
21.        %为树的存储空间赋值
    / b: h% J6 B+ U: a5 S- k
22.        %node name，按照广度优先为节点排号  f) L/ E+ S3 s4 d/ `
    
23.        tree_nodename = (1 : node_num);
    # w# {8 Z5 M- b6 V% X\" v
24.        %node value
    , @+ g7 Y2 [, h9 F2 ]5 c) l) ?; ~
25.        tree_nodevalue = rand(1 : node_num);
    2 X( n8 U8 O8 v& ~
26.        %node father and son
    ; w\" z5 p* q1 S* a8 U7 {/ B. n
27.        tree_nodefather(1) = 0;0 m- {; [/ j1 ^8 A/ S8 A1 N
    
28.        tree_nodeson = zeros(1, node_num);
    3 m7 z+ `9 ~* X6 ~0 V' E
29.        n = 2;2 j/ J; b$ T+ x# c  F4 ^6 L7 W
    
30.        k = 1;6 e# F' d& n& G! L3 m6 b4 f
    
31.        while n <= node_num
    , T; L( I( W. X1 n
32.               for m = 1 : tree_width
    2 g. n; q- g' F  M. N
33.                      tree_nodefather(n) = k;
    ; ?9 O% ?+ K( m7 {' G
34.                      if m==11 }( n8 v0 @, I9 B3 s0 ]$ u
    
35.                             tree_nodeson(k) = n;
    1 @) w. A: {0 E$ r$ ?$ e
36.                      end- N* A; g8 O$ ^% N3 S) V  w$ Y
    
37.                      n = n + 1;$ f  M+ a! p- _
    
38.               end
    # j+ R/ u1 C\" i9 d
39.               k = k + 1;
    , ]% X7 K* ~  c
40.        end
    1 z2 M. Y. x4 d7 C' @8 s! P
41.        %node neighbor2 n. x, i- e8 s& j0 g3 e\" ]
    
42.        tree_nodeneighbor(1) = 0;$ b  {/ F\" @: ?) @# P5 H. ?  J
    
43.        n = 2;
    : `0 V; Y- W% X6 D& m0 ]/ S\" b
44.        while n <= node_num' w# `, r2 K2 }1 \$ x* Z9 Y6 T
    
45.               for m = 1 : tree_width2 w! ~/ N5 N- K9 b$ Y) m/ W6 ?
    
46.                      if m ==tree_width  U1 ]$ Z/ f4 P% k. h
    
47.                             tree_nodeneighbor(n) = 0;  b! M( J6 i, K0 C5 H; U& v% T3 Q+ z
    
48.                      else
    ' b+ j) V' ]; z& [# \3 A* c
49.                             tree_nodeneighbor(n) = n + 1;
      W& P9 |3 h# I$ N( K
50.                      end
    ) W  c! r# p# p5 B  ]# p! O6 I3 N# }, e
51.                      n = n + 1;2 ?$ _& U1 R0 \1 ?
    
52.               end  X- u  l% W) m- X# ?9 _4 j
    
53.        end
    % g! j& @3 ?# a, H! f: X) k9 n# r$ [
54. 
    0 c0 m8 s5 o' E# `$ }. d
55.        %下面是有效程序段，用栈实现3 x. `( ~$ `# V: P' B1 {
    
56.        stack = zeros(1, tree_depth);! K. d( l/ J- t& r/ e! N6 p
    
57.        nodeinstack = zeros(1, node_num);; N, n\" n+ r$ U4 W/ i: ~/ x
    
58.        stack_ptr = 1;6 D2 k3 n( ^, \+ t: s1 Z, L3 \
    
59.        stack(1) = 1;
    & A3 g1 d& d; d1 W# A# u
60.        nodeinstack(1) = 1;# r8 M1 P4 H! q, H3 y
    
61.        valueintree = seek_value;/ S) C0 L: o: o
    
62.        nodeintree = 0;
    2 K3 H0 [; P1 ~' g/ V- w8 @5 i, i- @
63. 
    4 i$ _. ~( s1 G$ U
64.        while stack_ptr > 0
    + L8 ]8 f, D7 K' H9 q
65.               n = stack(stack_ptr);0 j' F8 b  k. Y3 W, |  {
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    6 s  f- R0 P4 V% P
67.               %如果搜索到值，返回! L& M/ B! t( g1 ^
    
68.                      valueintree = tree_nodevalue(n);. u1 y0 J. x8 s  _
    
69.                      nodeintree = tree_nodename(n);# c$ X) g: q* R  ^# `8 r
    
70.                      break;9 [- k* S7 z. K
    
71.               end
    * ^% V: \. f# k$ z+ f
72. 
    . t9 q* h5 Z# Z\" M
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    4 T5 B  ~/ m3 Y- e  Z
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    : r1 H$ F/ n7 t) P1 N  ]! s
75.                      stack_ptr = stack_ptr + 1;
    5 T) y$ A: K+ r
76.                      m = tree_nodeson(n);; ?+ Z: T1 Z5 y* F6 p5 S* z, a
    
77.                      stack(stack_ptr) = m;
    * k! X$ Q2 s\" p/ z1 w
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    : r. M4 v. u% \
79.               elseif tree_nodeneighbor(n) ~= 0
    ! U& s3 {, t0 r# d+ Y/ {
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈3 i0 _: B& M  i: T5 _2 l, `. _! e
    
81.                      m = tree_nodeneighbor(n);! O% F) v, K% i% W
    
82.                      stack(stack_ptr) = m;
      x! [- A( w: S7 |( |
83.                      nodeinstack(m) = nodeinstack(m) + 1;. J3 R; a3 W/ D; s; l) E; J
    
84.               else
    . `- X$ e, v8 y6 ?8 \* P
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    ' I% [0 B5 J: G  _
86.                      stack_ptr = stack_ptr - 1;$ B; c; T9 T7 X( o* X5 q. c/ Z! M
    
87.                      m = stack(stack_ptr);
    ) X: p# ?2 X, l4 W
88.                      nodeinstack(m) = nodeinstack(m) + 1;- g& b0 b0 ]/ m4 T+ P\" p
    
89.               end
    * B. j6 P. J3 X
90.        end

复制代码