二叉树 日志

huangyhg

1)      先序序列

#define leng sizeof (struct bnode)

2)      前序线索二叉树----线索指向前序遍历中前趋,后继的线索二叉树.

3)      线索二叉树的存储结构

3.1结点结构

左小孩 左标志 结点值 右标志 右小孩

4)      中序遍历序列和前(或后)序序列唯一确定一棵二叉树

Comment: 由前序序列和后序序列不能唯一确定一棵二叉树

5)      前序遍历的递归算法

preorder (struct nodeb * root)

{

  if(root)

  {

    printf("%c", root->data);   // visit root node

   preorder(root->lchild);       // iterate left tree

   preorder(root->rchild);      // iterate right tree

  }

}

6)      中序遍历非递归算法

preorder (struct nodeb *t)         // t is root point

{

  struct bnode * st[maxleng +1];

  int top = 0;     // stack is empty

  do

  {

    while (t)

    {

      if (top = naxleng)

        exit("overflow");

      st[++top] = t;       // push root into stack

      t = t->lchild;

      if (top)

      {

        t = st[top--];     // pop root

        printf("%c", t->data);

        t = t->rchild;

      }

    }

    while(top||t)

  }

}

7)      树和森林

7.1 树的存储结构

7.1.1 双亲 表示法/数组表示法

7.1.2 孩子表示法/链接表示法