189 8069 5689
假设有如下一颗二叉树
创新互联服务紧随时代发展步伐，进行技术革新和技术进步，经过十年的发展和积累，已经汇集了一批资深网站策划师、设计师、专业的网站实施团队以及高素质售后服务人员，并且完全形成了一套成熟的业务流程，能够完全依照客户要求对网站进行成都网站设计、成都网站制作、建设、维护、更新和改版，实现客户网站对外宣传展示的首要目的，并为客户企业品牌互联网化提供全面的解决方案。
得到的结果是[1 2 3 4 6 5]
得到的结果是[2 1 6 4 3 5]
得到的结果是[2 6 4 5 3 1]
第一种实现：
得到的结果是[[1] [2 3] [4 5] [6]]
第二种实现：
得到的结果是[1 2 3 4 5 6]
很简单，就是一个递归过程。在函数中以先序遍历的第一个结点在中序遍历中为界把中序遍历分为两半，再分别把左一半和右一半作为这个结点的左子树和右子树进行递归。完成递归之后再打印该结点即可。结束递归的条件是左子树或右子树没有结点。下面是简单的程序示意，可以用任意语言实现：
import sys
rflist = list(sys.argv[1])
rmlist = list(sys.argv[2])
def printTreeRootLast(r, rflist, rmlist):
r[0] = rflist.pop(0)
rmLeftNodes = rmlist[:rmlist.index(r[0])]
if len(rmLeftNodes) == 0:
r[1] = None
else:
r[1] = [None, None, None]
printTreeRootLast(r[1], rflist, rmLeftNodes)
rmRightNodes = rmlist[rmlist.index(r[0])+1:]
if len(rmRightNodes) == 0:
r[2] = None
else:
r[2] = [None, None, None]
printTreeRootLast(r[2], rflist, rmRightNodes)
print r[0],
root = [None, None, None]
printTreeRootLast(root, rflist, rmlist)
二叉树的遍历有3种方式：
a
/ \
/ \
b e
/ \ \
/ \ \
c d f
（先序）先根遍历：（根左右）先访问根，再访问左子树，最后访问右子树，则可得如下的序列：abcdef
（中序）中根遍历：（左根右）先访问左子树，再访问根，最后访问右子树，则可得如下的序列：cbdaef
（后序）后根遍历：（左右根）先访问左子树，再访问右子树，最后访问根，则可得如下的序列：cdbfea
本文给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p-data);
push(s,p);
p=p-lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p-rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p-lchild;
}//endwhile
if (!StackEmpty(s))
{
p=pop(s);
visite(p-data); //访问根结点
p=p-rchild; //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;
do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p-lchild;
}
while (!StackEmpty(s) s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p-data); //tag为R，表示右子树访问完毕，故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr-rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
5.1树的概念
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；
3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
5.树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5. 2 二叉树
1.二叉树的基本形态：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
2.两个重要的概念：
(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。
如下图：
完全二叉树
满二叉树
3.二叉树的性质
(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；
(2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，
则N0=N2+1；
(4) 具有n个结点的完全二叉树的深度为int（log2n）+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I1，则其父结点的编号为I/2；
如果2*I=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*IN，则无左儿子；
如果2*I+1=N，则其右儿子的结点编号为2*I+1；若2*I+1N，则无右儿子。
4.二叉树的存储结构：
(1）顺序存储方式
type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n] of node;
(2)链表存储方式，如：
type btree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;
5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。
6.二叉树的遍历运算（递归定义）
(1)先序遍历
访问根；按先序遍历左子树；按先序遍历右子树
(2)中序遍历
按中序遍历左子树；访问根；按中序遍历右子树
(3)后序遍历
按后序遍历左子树；按后序遍历右子树；访问根
例1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。
program erchashu1;
var b:array[1..31] of char;
e:array[1..63] of byte;
n,h,i,k:integer;
procedure tree(t:integer);
begin
if e[t]=0 then exit
else
begin
write(b[t]);e[t]:=0;
t:=2*t;tree(t);
t:=t+1;tree(t);
end;
end;
begin
repeat
write('n=');readln(n);
until (n0) and (n6);
fillchar(e,sizeof(e),0);
k:=trunc(exp(n*ln(2)))-1;
for i:=1 to k do e[i]:=1;
for i:=1 to 26 do b[i]:=chr(64+i);
for i:=1 to 5 do b[26+i]:=chr(48+i);
h:=1 ;tree(h);
writeln;
end.
例2.用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。
program tree1;
const n=15;
type node=record
data:char;
l,r:0..n;
end;
var tr:array[1..n] of node;
e:array[1..n] of 0..1;
i,j:integer;
procedure jtr;
var i:integer;
begin
for i:=1 to n do
with tr[i] do
readln(data,l,r);
end;
procedure search(m:integer);
begin
with tr[m] do
begin
write(data);
if l0 then search(l);
if r0 then search(r);
end;
end;
begin
jtr;search(1);writeln;
end.
例3 用链表存储方式生成上述二叉树，中序遍历之。
1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H)))
2.根据广义表串（以#结束）生成二叉树。
program ltree;
const n=8;
type trlist=^node;
node=record
da:char;
l,r:trlist;
end;
var s:array[1..n] of trlist;
p,root:trlist;
ch:char;
top,k:integer;
procedure creat(var head:trlist);
begin
read(ch);
top:=0;
while ch'#' do
begin
case ch of
'A'..'Z':begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil;
if top0 then
case k of
1:s[top]^.l:=p;
2:s[top]^.r:=p;
end
end;
'(':begin top:=top+1;s[top]:=p;k:=1;end;
')': top:=top-1;
',': k:=2;
end;
read(ch);
end;
head:=s[1];
end;
procedure inorder(head:trlist);
begin
if head^.lnil then inorder(head^.l);
write(head^.da);
if head^.rnil then inorder(head^.r);
end;
begin
write('Input tree string:');
creat(root);
inorder(root);
end.
5.3 二叉树的应用
1. 哈夫曼树与哈夫曼码
树的路径长度：一棵树的每一个叶结点到根结点的路径长度的和。
带权二叉树：给树的叶结点赋上某个实数值（称叶结点的权）。
带权路径长度：各叶结点的路径长度与其权值的积的总和。
哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。
如何构建哈夫树：（思想是：权越大离跟越近）
program gojiantree;
const n=4;m=7;
type node=record
w:real;
parent,lchild,rchild:0..m
end;
htree=array[1..m] of node;
var htree1:htree;
procedure gjtree(var ht:htree);
var i,j:integer;
small1,small2:real;
p1,p2:0..m;
begin
for i:=1 to m do
with ht[i] do
begin
w:=0;lchild:=0;rchild:=0;parent:=0;
end;
for i:=1 to n do read(ht[i].w);
for i:=n+1 to m do
begin
p1:=0;p2:=0;
small1:=1000;small2:=1000;
for j:=1 to i-1 do
if ht[j].parent=0 then
if ht[j].wsmall1 then
begin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end
else if ht[j].wsmall2 then begin small2:=ht[j].w;p2:=j end;
ht[p1].parent:=i;
ht[p2].parent:=i;
ht[i].lchild:=p1;
ht[i].rchild:=p2;
ht[i].w:=ht[p1].w+ht[p2].w;
end;
end;
begin
gjtree(htree1);
end.
哈夫曼码：哈夫曼树的非叶结点到左右孩子的路径分别用0，1 表示，从根到叶的路径序列即为哈夫曼码。
哈夫曼码是不会发生译码多义性的不等长编码，广泛应用实际中。
（原因是任何一字符的编码不是更长编码的前缀部分，为什么？）
2.排序二叉树
排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下：
program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
begin
if leftnil then hyt1(left);
write(w:4);
if rightnil then hyt1(right);
end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a[i],first);
hyt1(root);writeln;
end.
3.堆排序
堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有
Ri=R2i 和Ri=R2i+1(或=)
堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。
堆排序的思想是：
1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）
2）当未排序完时
输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。
程序如下：
program duipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procedure sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a[i];
while j=m do
begin
if (jm) and (a[j]a[j+1]) then j:=j+1;
if ta[j] then
begin a[i]:=a[j];i:=j;j:=2*i; end
else exit;
end;
a[i]:=t;
end;
begin
for i:=1 to n do read(a[i]);
for i:=(n div 2) downto 1 do
sift(a,i,n);
for i:=n downto 2 do
begin
write(a[1]:4);
a[1]:=a[i];
sift(a,1,i-1);
end;
writeln(a[1]:4);
end
这是我学习二叉树时用过的例子，运行没有问题，你自己按照上面弄下吧。由于图贴不了，实在抱歉。
学生会组织机构管理问题的设计方案
1． 问题描述
学生会组织机构管理问题中的数据元素具有如下形式：
firstchild data rightbrother
firstchild: 指向第一个孩子结点
rightbrother: 指向右兄弟结点
data: 学生会成员信息，其自然情况包括：职位，姓名，性别，年级，班级。
2． 功能需求
要求完成以下功能：
(1) 插入：将某学生插入到某部门；
(2) 删除：将某学生在某个部门删除；
(3) 修改：修改某个部门的组成情况；
(4) 查询：查询学生会的组织机构状况；
(5) 输出：按部门输出学生会全体成员。
3． 实现要点
(1) 为方便对学生会组织机构的各项操作，学生会的组织机构用孩子兄弟表示法进行存储。为该存储结构设计一个模板类，设计成员函数完成上述功能。
(2) 为树的孩子兄弟表示法设计一个结点类，将结点的数据部分作为私有成员隐藏在类的内部，并提供查找右兄弟、查找第一个孩子等操作。
(3) 简单起见，学生会成员的自然情况包括职位、姓名、性别、年级、班级，为其设计一个学生类，将各自然情况作为私有成员隐藏在类的内部，并提供相应成员函数实现对数据进行访问。
(4) 在主函数中提供操作菜单，先对该组织机构进行初始化，即根据实验数据建立一棵树，再根据用户的输入完成相应功能并输出结果。
4． 类定义
为树的孩子兄弟表示法建立结点类(Node)，其类定义如下：
template class T
class Node
{
public:
Node(T* data) { _data = data; _firstChild = NULL; _brother = NULL;}//有参构造函数
~Node() {} //无参析构函数
NodeT* getFirstChild() { return _firstChild; } //访问结点第一个孩子
NodeT* getBrother() { return _brother; } //访问结点的右兄弟
T* getData() { return _data; } //取结点数据域的值
void setFirstChild(NodeT* node) { _firstChild = node; } //为结点的第一个孩子赋值
void setBrother(NodeT* node) { _brother = node; } //为结点的右兄弟赋值
void setData(T* data) { _data = data; } //为结点的数据域赋值
private:
T* _data; //结点的数据域
NodeT* _firstChild; //结点的头孩子指针
NodeT* _brother; //结点的右兄弟指针
};
在结点类中，提供了如下成员函数：
（1） 函数的声明：Node(T* data)；
完成的功能：初始化一个新结点
（2） 函数的声明：NodeT* getFirstChild()；
完成的功能：返回指向结点的第一个孩子结点的指针
（3） 函数的声明：NodeT* getBrother()；
完成的功能：返回指向结点的右兄弟结点的指针；
（4） 函数的声明：T* getData()；
完成的功能：返回结点数据域的值
（5） 函数的声明：void setFirstChild(NodeT* node)；
完成的功能：为结点的第一个孩子赋值
（6） 函数的声明：void setBrother(NodeT* node)；
完成的功能：为结点的右兄弟赋值
（7） 函数的声明：void setData(T* data)；
完成的功能：为结点的数据域赋值
为数据域的学生会成员建立成员类（Member）,其类定义如下：
class Member
{
public:
Member(string position, string name, string sex, string grade, int classes); //有参构造函数
void print(void); //打印数据
string getPosition() const { return _position; }//获取学生职务
string getName() const { return _name; } //获取学生姓名
string getSex() const { return _sex; } //获取学生性别
string getGrade() const { return _grade; }//获取学生所在年级
int getClasses() const { return _classes; }//获取学生所在班级
//操作符重载用来判断结点中数据是否相等，若相等则返回1否则返回0
int operator==(Member stu) const
{
return _name == stu.getName()
_sex == stu.getSex()
_grade == stu.getGrade()
_classes == stu.getClasses()
_position == stu.getPosition();
}
private: //学生会成员属性
string _position; //职位
string _name; //姓名
string _sex; //性别
string _grade; //年级
int _classes; //班级
};
在成员类中，提供了如下成员函数：
（1） 函数的声明：Member(string position, string name, string sex, string grade, int classes);
完成的功能：初始化一个新的数据成员
（2） 函数的声明：void print(void);
完成的功能：打印出数据成员信息
（3） 函数的声明：string getPosition() const；
完成的功能：返回学生会成员的职务
（4） 函数的功能：string getName() const；
完成的功能：返回学生会成员的姓名
（5） 函数的声明：string getSex() const；
完成的功能：返回学生会成员的性别
（6） 函数的声明：string getGrade() const；
完成的功能：返回学生会成员的年级
（7） 函数的声明：int getClasses() const；
完成的功能：返回学生会成员的班级
（8） 函数的声明：int operator==(Member stu) const；
完成的功能：比较数据域的值（即学生会成员的所有属性）是否相等，若相等返回1，否则返回0
为学生会组织机构的管理建立树类（Tree）,其类的定义如下：
template class T
class Tree
{
NodeT* _root; //指向根结点的头指针
T* _tempDate; //结点数据域中的数据
public:
Tree(T* data) {_root = new NodeT(data);} //有参构造函数，初始化一棵树//的根结点
~Tree(void) {Release(_root);} //析构函数，释放树中各结点的存储空间
void Insert(T* oldData, T* newData); //插入函数
void DeleteNode(T* date); //删除树中某结点及其孩子
void Update(T* oldData, T* newData); //修改函数
NodeT* FindNode(std::string position,Function function); //查询函数
void LeverOrder(Function function); //层序遍历树
private:
void Release(NodeT* node); //析构函数调用
NodeT* FindNode(T* data); //插入函数调用
void InsertBrother(NodeT* node,T* data); //插入兄弟结点
void InsertChild(NodeT* node, T* data); //插入第一个孩子结点
};
在树类中，提供了如下成员函数：
（1） 函数的声明：Tree(T* data)；
完成的功能：初始化一棵树
（2） 函数的声明：~Tree(void)；
完成的功能：释放树的存储空间
（3） 函数的声明：void Insert(T* oldData, T* newData);
完成的功能：将新结点插入到合适的位置
下面是演示结果：
例如将（文艺部员，刘琳，女，一，3 ）插入到（文艺部长，王一，女，一，5）的孩子结点中：
（5） 函数的声明：void DeleteNode(T* date);
完成的功能：释放要删除结点及其孩子结点的存储空间
如下将演示删除的过程：
例如：删除（秘书长，李四，女，一，4）这个结点：
（6） 函数的声明：void Update(T* oldData, T* newData);
完成的功能：修改结点的数据信息
例如要将（学习部长，刘一，女，二，4）修改为
（学习部长，周瑜，男，二，5）
（7） 函数的声明：NodeT* FindNode(std::string position,Function function);
完成的功能：查询树中的结点信息，并输出符合条件的结点的数据信息
例如查询副主席的所有成员显示如下：
（8） 函数的声明：void LeverOrder(Function function);
完成的功能：层序遍历一棵树，输出树中所有结点的数据信息
未进行任何操作前的学生会所有成员如下：
插入后显示树中的所有成员如下：
删除后显示树中的所有成员：
修改后显示如下：