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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：3 r7 g' X/ x+ K9 ~
   
2.        tree_nodename：节点名字或序号
   * |$ Y1 [; P# ]- N, r* q$ r0 ^
3.        tree_nodevalue：节点对应的值1 D% G( N4 f% ~8 R
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   . X! Z. V. r& p
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空* s' b1 U# A% n9 p
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空# H2 p; t& Z+ o7 R
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。1 B' Q+ b6 k: \1 ^& @9 r
   
8. 
   * G& ~9 O5 l# S0 c6 [2 J8 W5 P
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。4 p0 ^2 p# n. F  ]5 g
   
10. 3 o\" @) H. u6 k; y
    
11.        %matlab源程序
    2 m# h: V* H2 e* s  ?+ {
12.        %输入：树的深度、树的广度、搜索的值
    1 \  v  ?1 M/ |/ p5 l9 w+ L
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空2 n& @( H8 p8 Z
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    2 i) o  q' L. ^; x' n  ?
15.        %根据树的深度、节点的儿子数量计算树总的节点个数* z; v5 _% Z# F' m' p3 A& n
    
16.        node_num = 0;; U( p. ^7 I: y! G; `8 M
    
17.        for n= 0 : (tree_depth-1)
    5 Q; s: U& F$ e  R9 N6 Z7 M
18.               node_num = node_num + tree_width ^ n;
    2 |' d' m8 }0 R# s$ s+ k# Y& U
19.        end
    ! r& ~: B! k1 j) v
20. 
    ( h# P! f' {2 w1 ]6 `
21.        %为树的存储空间赋值
    ( R6 _# g* D! y0 ^6 U& W8 v1 I* t: |
22.        %node name，按照广度优先为节点排号$ c5 H( x9 R* K9 p- a; r8 T7 q\" h
    
23.        tree_nodename = (1 : node_num);
    * n  o\" c+ M4 j$ ^  W
24.        %node value
    ( m* Z, j( J5 R
25.        tree_nodevalue = rand(1 : node_num);
    1 u0 W/ @! O9 H/ C4 e% b# a: B
26.        %node father and son2 h1 k- @- x) H% Q$ ]
    
27.        tree_nodefather(1) = 0;
    7 m; }9 k2 x$ {! ]* g  p
28.        tree_nodeson = zeros(1, node_num);5 K2 ^* x' [& t- ~, d2 d
    
29.        n = 2;% M& L4 K/ U4 |  S  v
    
30.        k = 1;/ H  B0 F7 d, l+ q2 I
    
31.        while n <= node_num
    # E7 w0 U7 K1 l2 _3 P* i
32.               for m = 1 : tree_width
    5 S* d$ o9 U* f' i6 S  f' L
33.                      tree_nodefather(n) = k;  B4 f4 T2 N. H
    
34.                      if m==1
    ' a  v5 \\" z# ]
35.                             tree_nodeson(k) = n;
    0 V0 F& I: t$ j, \
36.                      end$ N8 V$ u! |6 ]9 m' D' P
    
37.                      n = n + 1;) n! ~  [* z! q$ e1 R. ?
    
38.               end
    + _4 N* }4 M% a% M\" |\" @3 J
39.               k = k + 1;
    7 ^6 U9 ]1 P\" c8 \- u3 c% D
40.        end5 F  K3 g) P2 q. a& |
    
41.        %node neighbor
    9 [+ M$ L# q( K- s7 E1 Z1 P6 J
42.        tree_nodeneighbor(1) = 0;# U6 O- B  I! x5 G2 }
    
43.        n = 2;
    2 Q) n- Y; K7 {8 E0 w
44.        while n <= node_num
    3 H$ V9 j$ }* M8 J
45.               for m = 1 : tree_width
    ( r) s$ f# w+ h
46.                      if m ==tree_width1 _% U$ w, {. w, t' [$ r- w! I
    
47.                             tree_nodeneighbor(n) = 0;3 z& z' e: k/ D. _' v7 i6 `
    
48.                      else* j5 f* B9 B1 u' t) D
    
49.                             tree_nodeneighbor(n) = n + 1;7 |  m  }& z* f
    
50.                      end
    * O4 r6 \1 d  e% C7 ]
51.                      n = n + 1;
    : C0 ~3 S$ ?/ s  ~! m8 _- @
52.               end
    ; n. M' n0 u# h
53.        end
    9 ?; ?$ {* r& {/ ]9 ~, ?# U3 |
54. 
    / M: A% j; r/ m\" N5 v) ~
55.        %下面是有效程序段，用栈实现- |6 p1 A  a1 s5 {) h
    
56.        stack = zeros(1, tree_depth);
    # P4 p4 s7 C' T3 q
57.        nodeinstack = zeros(1, node_num);
    / g\" r  G  c1 v  ~/ r' i
58.        stack_ptr = 1;
    6 b6 @( C1 r) i
59.        stack(1) = 1;
    0 M4 Q& q0 u- |/ s: |1 x' n
60.        nodeinstack(1) = 1;) P; ~* Z) L) \/ c+ c
    
61.        valueintree = seek_value;
    . F1 \: i* d+ L8 |1 Q
62.        nodeintree = 0;) T\" ]1 R# Y- U3 O( ?4 L
    
63. 
    - y- f! U1 F7 `2 y
64.        while stack_ptr > 0
    & D- |, ?9 K1 ?9 k. L8 c
65.               n = stack(stack_ptr);/ d* z6 {- d3 A0 }: [2 e: g
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3# S% C' p) l. K% `: t$ M* N
    
67.               %如果搜索到值，返回  K& s) \\" B5 q\" t$ X* B, n3 f
    
68.                      valueintree = tree_nodevalue(n);% _' n$ J0 P, V2 O! Z: {
    
69.                      nodeintree = tree_nodename(n);* n) w/ O9 ]* E! |
    
70.                      break;
    - y2 r  h9 \/ ?3 w$ V
71.               end
    ) x9 S- d% Y! o3 X& B
72. : a+ T; ?/ ~- `  r* w/ Z
    
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    ; @2 l. \1 `3 {6 p  u( S
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    0 i7 E; O$ T. t  y
75.                      stack_ptr = stack_ptr + 1;4 {5 a6 n# P\" H\" |2 e. C
    
76.                      m = tree_nodeson(n);
    & M6 T! b. l& K' p: K
77.                      stack(stack_ptr) = m;
    , B7 P5 ~- ~+ g5 \$ @5 @\" N
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    * x$ F  {6 m\" F* k
79.               elseif tree_nodeneighbor(n) ~= 0. h- U/ a! k4 ~
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    6 j8 {& N' N/ x
81.                      m = tree_nodeneighbor(n);- }, r\" L0 y9 f( V! D2 t7 N5 A' K
    
82.                      stack(stack_ptr) = m;
    ' B* c' M8 v6 [1 r
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    2 V. M- H# u& m1 \# U/ g
84.               else) }1 W7 l4 B9 R  v- L+ ]
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    * {. M\" g$ a3 l
86.                      stack_ptr = stack_ptr - 1;
    : Z8 o& T3 x0 c) P8 K' r6 x7 ^. g- f& \
87.                      m = stack(stack_ptr);
    5 \1 N) w) c) z1 `5 W
88.                      nodeinstack(m) = nodeinstack(m) + 1;
    7 k, H5 I9 I7 H
89.               end: l0 U\" R& |2 i- S; ~\" N
    
90.        end

复制代码