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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   . u9 ~) I/ _' j
2.        tree_nodename：节点名字或序号- K$ k' b0 J( R: j4 p5 Z  @/ t' `0 n! K7 Z
   
3.        tree_nodevalue：节点对应的值
   , G) {- T4 d3 s- k6 _
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   1 l6 g9 S* o5 U0 f\" B) r! W
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   ! e8 B- z# }$ s
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空% [3 B0 J* w( ?7 P' M- h) I\" v& W
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   4 k: @- I+ |) O& g8 h+ n# o3 y# A
8. 
     b6 \: J) d& a3 q6 L$ p
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。7 d0 W) k: Q( L, X* [
   
10. 4 {% N: a) Z; J1 c8 g' h
    
11.        %matlab源程序
    % \; u  n3 t: c. v- D7 V2 d) c, R5 P
12.        %输入：树的深度、树的广度、搜索的值1 c; S- u! k; d& q$ I% {, }
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    . ?3 ?. r5 ?4 V: ?0 H2 p* b# T. V
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)( e4 M$ [3 ~0 b$ e/ Q9 A
    
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
      O( h( a1 c6 t% ]/ }% g4 i
16.        node_num = 0;3 q1 s, w7 n' q) J: N
    
17.        for n= 0 : (tree_depth-1); F& c' k! @: E$ i
    
18.               node_num = node_num + tree_width ^ n;
    6 L& x3 E( T$ a9 C! A
19.        end9 m- x4 e\" a+ ^/ b$ T+ ?- z! L
    
20. 
    : }6 x* Y, i$ s
21.        %为树的存储空间赋值
    : W. Q  ~, K( K
22.        %node name，按照广度优先为节点排号
    , F( e9 T3 l  k2 a' M: B; q
23.        tree_nodename = (1 : node_num);
    2 F4 ~* p. \7 y0 S4 O1 \3 Y
24.        %node value4 Z! N$ Z3 z8 A; H9 I
    
25.        tree_nodevalue = rand(1 : node_num);
    9 n3 @  e8 e1 R8 S1 Q! L, L
26.        %node father and son
    2 F8 S8 B- h  v2 z) P\" p
27.        tree_nodefather(1) = 0;# z( T, v5 ^, o8 p9 X4 N  t
    
28.        tree_nodeson = zeros(1, node_num);
    ) G* d, `: r5 S5 }' y0 I6 T
29.        n = 2;$ x2 y\" o' c( |) L\" y9 h
    
30.        k = 1;1 U! n; Z# ^9 _: q- R/ m
    
31.        while n <= node_num
    ( c5 [1 G* \' t! q
32.               for m = 1 : tree_width
    \" v9 n1 O  _& t: f0 p4 k
33.                      tree_nodefather(n) = k;( o0 I  K8 T' a+ b% z' [
    
34.                      if m==1
    : @& P7 e8 b' E+ b& |2 |, A2 Z
35.                             tree_nodeson(k) = n;& @+ R+ w7 S6 y9 D! f
    
36.                      end1 ^' K9 b* D2 }) A, O
    
37.                      n = n + 1;. ?* X0 C4 B6 E  l# ~' r+ N2 I
    
38.               end
    & s& V7 b& A; z, b- w: N' }( d
39.               k = k + 1;
    8 G4 {. B! f: Q% o( D% a\" }
40.        end
    . Q% n5 m3 r7 Q6 j% {% a7 f# H
41.        %node neighbor. l5 p: L4 H: a# I+ D
    
42.        tree_nodeneighbor(1) = 0;, U- r- O! o! g+ n; K1 R9 ?# Q3 u1 F2 X
    
43.        n = 2;
    # U- R' x8 u2 w; \& q3 Y/ p+ M\" l
44.        while n <= node_num
    0 V, H$ @6 C! V$ ^% m( \* Q
45.               for m = 1 : tree_width
    0 Y: `  L/ Z$ ~7 s( t
46.                      if m ==tree_width
    # ]+ V% x6 P& Q; m\" V9 A0 k
47.                             tree_nodeneighbor(n) = 0;
    ! ?6 |* g! o3 O! E
48.                      else
    1 f* K2 L\" A9 M1 j/ V% a
49.                             tree_nodeneighbor(n) = n + 1;  A7 i9 ~4 K' D  d9 Z4 Z
    
50.                      end
    * N0 |: y+ y  b9 n
51.                      n = n + 1;& b% l\" V& h' k+ @
    
52.               end: C% f7 [, c- j\" @' T4 [) i6 x
    
53.        end
    # [( X3 k  x$ O$ z& V6 f8 |
54. 
    ' @9 x/ v. k\" s) o. U
55.        %下面是有效程序段，用栈实现+ w* M7 Q( v, E0 e4 V& v
    
56.        stack = zeros(1, tree_depth);
    ! L- ~6 \0 V7 ^; b/ N
57.        nodeinstack = zeros(1, node_num);
    # x; V6 Y( F7 Z* Q. w  p
58.        stack_ptr = 1;7 B3 G8 L5 b$ L0 _' A
    
59.        stack(1) = 1;) ]\" i- H, v/ s
    
60.        nodeinstack(1) = 1;
    ; s0 L4 J. v, Q\" `
61.        valueintree = seek_value;% N6 I! q; P1 E) |3 Z! M, g9 a
    
62.        nodeintree = 0;
    ( _/ H' ]\" I  J' ~! ]8 G
63. 5 g8 v* U; f1 p5 u* k: X
    
64.        while stack_ptr > 0
    6 w0 t5 |# i0 G( ]5 ?0 @6 E/ E
65.               n = stack(stack_ptr);
    5 ^* i/ A3 T. s5 J/ z0 T
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    ; w, e8 q2 V3 w1 q% L4 G( D
67.               %如果搜索到值，返回) I\" `' S* Z, `1 z3 H- G
    
68.                      valueintree = tree_nodevalue(n);7 h; V8 N\" a8 b
    
69.                      nodeintree = tree_nodename(n);
    % ~\" _; ?) G+ V
70.                      break;
    5 }- J( F5 ^1 q* T* Z
71.               end
    3 R5 A3 F. ]( u4 e! R9 m* L! e
72. 3 ~\" d, u, w' G  A7 R! ~. v/ ~
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    - A' ^/ L/ o* R/ c
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    / U& B) w0 n/ F
75.                      stack_ptr = stack_ptr + 1;$ E. Z* P0 P. p
    
76.                      m = tree_nodeson(n);& ?# k4 _& Y5 F* e! T: N4 k$ X3 M9 f
    
77.                      stack(stack_ptr) = m;6 y! l* l1 u2 M$ {4 r; {  R
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;. z8 e. c; R; n\" ]4 k4 u
    
79.               elseif tree_nodeneighbor(n) ~= 03 d0 J4 D% z' n: T1 ^
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    ( x$ k/ E. k2 [
81.                      m = tree_nodeneighbor(n);
    / x5 v4 }8 I6 j3 w3 y
82.                      stack(stack_ptr) = m;1 b1 ?1 u  M5 W2 R! K- \7 ~& o\" j
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    1 M( S5 o; c3 y# V\" {
84.               else
    , m/ N/ U& `0 O
85.               %再否则，出栈，然后将父亲节点的入栈次数加一* Q2 ?3 R: c! H9 A# ]: b2 o
    
86.                      stack_ptr = stack_ptr - 1;
    , w7 W) I: E1 @2 W7 p) }1 s
87.                      m = stack(stack_ptr);2 X, w8 F: M& X- F- V8 ~
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    / p) E* ?6 n' ~3 s
89.               end
    , t! \# c8 h% m: e. H5 k
90.        end

复制代码