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 孩子表示法/链接表示法