数学建模社区-数学中国

标题: 求树的节点个数求法，求助啊！！！ [打印本页]
作者: qiandongdong    时间: 2014-8-20 23:31
标题: 求树的节点个数求法，求助啊！！！
求树的节点个数的求法啊或matlab代码，我是新手，真心编了好久没结果。请前辈们帮帮忙啊~
作者: madio    时间: 2014-8-21 00:16
就是一个遍历树的所有节点的算法，我帮你找到一个
  1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
    . X1 P) d" _) T. U
  2.        tree_nodename：节点名字或序号! N5 v# N. R2 y  P, S
  3.        tree_nodevalue：节点对应的值, b8 ^* u: S" h
  4.        tree_nodefather：节点父亲，如果没有父亲，值为空8 S7 g2 d: l1 s/ V9 ~! h
  5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空6 V! m' B- F1 ?8 B2 S; H( x
  6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
    , ?+ u4 [, y- W) F/ y  n) A- f" u+ n
  7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
    2 o; [# P/ r0 p2 ^; E) W* I" M$ `

  8. 7 {0 n9 j+ P7 z3 D' @5 a
  9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
    + i/ b4 s- A4 i) Y& r* e
  10. 4 |; @+ `+ [7 X+ X5 D
  11.        %matlab源程序
    4 h+ @4 B9 x$ Z+ F
  12.        %输入：树的深度、树的广度、搜索的值& n) |  v' S0 A
  13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空7 T; m5 x3 [6 }9 T5 C2 m8 s
  14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    5 x3 l6 l& V8 u4 _% ]
  15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    " S$ i4 e' M* }. e. e
  16.        node_num = 0;
    ; G0 Y7 Z" i5 g
  17.        for n= 0 : (tree_depth-1)% g& h  W! ~6 S/ j
  18.               node_num = node_num + tree_width ^ n;
    ; M9 J% H2 p) x: `0 K2 q; z: I" o
  19.        end
    / L+ [* ?4 u2 P; j2 \

  20. 9 C2 _! \5 q: q* c, s
  21.        %为树的存储空间赋值7 h# l) H2 g6 y) y+ @! q' b7 g6 d
  22.        %node name，按照广度优先为节点排号
    6 J6 [$ X( n; d% U3 d" ~6 Q7 A. {
  23.        tree_nodename = (1 : node_num);
    2 C3 }! ]$ U, c6 A
  24.        %node value' W- R. C5 w7 j
  25.        tree_nodevalue = rand(1 : node_num);
    2 f" D% V4 M3 Q9 v  A; |, _* i
  26.        %node father and son
    . _% m# X9 Q# T: j' y
  27.        tree_nodefather(1) = 0;
    & a( z( X$ F: P! c" g0 n7 i: v
  28.        tree_nodeson = zeros(1, node_num);
    . ~- Q* V1 K) R- q" z' k
  29.        n = 2;
    : {7 l! f3 v8 L( N+ E2 p  d) H$ X
  30.        k = 1;
    2 [8 E$ [( b8 ~# Z, A
  31.        while n <= node_num
    6 p2 E! w; v' X* B
  32.               for m = 1 : tree_width
    + F# i. X& B' m2 R% \
  33.                      tree_nodefather(n) = k;3 T1 }/ q7 m3 R' n3 G; b& }
  34.                      if m==1
    5 t; u/ M! v/ V3 E
  35.                             tree_nodeson(k) = n;
    % s4 A" \+ H9 y7 x
  36.                      end5 j* J+ S4 K0 J! c/ V& k1 F# k* g2 e
  37.                      n = n + 1;
    ( i0 `7 j% E! B5 s0 _) }! X; R" ~
  38.               end
    * Y+ F% d5 b# r
  39.               k = k + 1;* e1 o; s% n( Q5 h* ~/ [
  40.        end+ _! a1 D4 {3 @4 f% i
  41.        %node neighbor1 G2 Q( K1 Z) |0 }$ }  J* G
  42.        tree_nodeneighbor(1) = 0;( r* w6 ]# Y- ]; Z3 A7 s$ P0 z7 J
  43.        n = 2;
    0 L1 O) J! E( w, Y  Q' |0 e
  44.        while n <= node_num
    : G$ M0 V3 _7 z- g' x1 \4 V
  45.               for m = 1 : tree_width8 ~  U# y( O2 M4 o
  46.                      if m ==tree_width* j+ I+ B2 W8 ~2 b' i& D
  47.                             tree_nodeneighbor(n) = 0;
    * d* Z  X1 ~1 w  P& F  _
  48.                      else6 i+ }' m7 k# m- D) \- O* x) q
  49.                             tree_nodeneighbor(n) = n + 1;; l1 y( y  _0 a
  50.                      end
    ! }# X2 }- p& ~/ F3 ^( n
  51.                      n = n + 1;
    5 a6 U1 o) b0 L2 n: V2 e
  52.               end. i" i3 G( p) U) `, }4 B8 g7 C
  53.        end
    . O& W. V3 S- i. J# q9 O; L0 T: F
  54.   I; C0 r% e% b1 X, Q* H" X
  55.        %下面是有效程序段，用栈实现0 T" ~5 H1 }1 k( b
  56.        stack = zeros(1, tree_depth);
    % n6 s6 [7 T4 I1 Q
  57.        nodeinstack = zeros(1, node_num);
    0 W! ^: {- k& N. g# ]
  58.        stack_ptr = 1;( K; U& {) c6 }+ ~6 ?3 m+ I
  59.        stack(1) = 1;
    7 F; j) c7 B& D! H; _
  60.        nodeinstack(1) = 1;0 c) [6 L7 X0 F7 ^
  61.        valueintree = seek_value;' Y6 @9 _) H4 c& w3 m" t: u. r; K
  62.        nodeintree = 0;
    " F  ^* h: J; Q) |( I

  63. & H+ G7 o1 W: K0 e
  64.        while stack_ptr > 0
    6 Z8 c. |3 G( o7 j
  65.               n = stack(stack_ptr);
    # R1 ^/ K! ~& s; E0 H" {
  66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    6 K7 q! U5 x' F& J7 x) l
  67.               %如果搜索到值，返回8 }7 ?+ F& i9 Q
  68.                      valueintree = tree_nodevalue(n);/ {7 x  b% w8 A
  69.                      nodeintree = tree_nodename(n);
    2 v7 h) p0 o$ I( }( T1 _! `! v
  70.                      break;$ {7 F/ W$ @# ?; C' P* q
  71.               end
    6 m) b0 m. X% E3 o2 @/ p
  72. ; H+ }! P9 G: x6 p9 F, S9 w5 S
  73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    ' i4 z* ]1 {+ H! t0 p- G/ l9 ?0 x8 D
  74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈6 A  _  |! \+ m0 N9 v6 e9 W
  75.                      stack_ptr = stack_ptr + 1;; U9 z. _0 w7 _4 t" ?
  76.                      m = tree_nodeson(n);
    0 x$ N7 X7 h2 }$ h" h
  77.                      stack(stack_ptr) = m;
    9 M7 ^* D7 C: d2 q% T
  78.                      nodeinstack(m) = nodeinstack(m) + 1;
    & |4 w* m# U% ]# M% C( O- ?# P
  79.               elseif tree_nodeneighbor(n) ~= 0
    ( K3 r* E: ^& I/ y6 {0 |3 j
  80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈
    " I6 n9 o, L- u! ?
  81.                      m = tree_nodeneighbor(n);! ?- h& v4 I& t7 j7 e
  82.                      stack(stack_ptr) = m;: R! ~2 c/ ^$ m4 ~
  83.                      nodeinstack(m) = nodeinstack(m) + 1;
    & R! [  k4 V( o2 r. D/ V
  84.               else, M: \$ @& Q, s% i  q; H# m
  85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    , o! a) f7 f- t+ c
  86.                      stack_ptr = stack_ptr - 1;, N: Z# @) G# f+ p1 _$ t
  87.                      m = stack(stack_ptr);
    ) [0 s  Z; N% H' z5 b% t' D" g
  88.                      nodeinstack(m) = nodeinstack(m) + 1;
      ~0 p$ k% g7 m
  89.               end2 m. s5 U( J5 o, g- I& b$ ]
  90.        end
复制代码




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5