rev1ve's blog
0%

数据结构学习笔记

发表于 更新于 分类于 阅读次数： Valine：

记录有关数据结构的代码练习

线性表

顺序表

表的定义

静态分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L){
	for(int i=0; i<MaxSize; i++){
		L.data[i]=0;
		L.length=0;
	}
}

int main(){
	SqList L;
	InitList(L);
	for(int i=0; i<MaxSize; i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	}
	return 0;
}

执行结果如下

image-20241013205426572

动态分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdlib.h>
#include <stdio.h> 
#define InitSize 10

typedef struct{
	int *data;
	int MaxSize;   //顺序表最大容量 
	int length;    //顺序表当前长度 
}SeqList;

void InitList(SeqList &L){
	//用malloc函数申请一片连续存储空间
	L.data=(int*)malloc(InitSize*sizeof(int));
	L.length=0;
	int MaxSize=InitSize;
}

void IncreaseSize(SeqList &L, int len){
	int *p=L.data;
	L.data=(int*)malloc((L.length+len)*sizeof(int));
	for(int i=0; i<L.length; i++){
		L.data[i]=p[i];         //将原来的数据复制到新区域
	}
	L.MaxSize=L.MaxSize+len;    // 顺序表最大长度增加 len 
	free(p);                    //释放原来的内存空间 
}

int main(){
	SeqList L;
	InitList(L);           //初始化顺序表 
	IncreaseSize(L, 5);    //动态增加长度5 
	return 0;
}

表的基本操作

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];              //静态分配定义表
	int length;
}SqList;

void InitList(SqList &L){
	for(int i=0; i<MaxSize; i++){
		L.data[i]=i;
		L.length=7;                 //初始化长度为7
	}
}

void ListInsert(SqList &L, int i, int e){
	for(int j=L.length; j>=i; j--){
		L.data[j]=L.data[j-1];      //使用后移方法，将前面的值往后移一位 
	}
	L.data[i]=e;
	L.length++;
}

int main(){
	SqList L;
	InitList(L);
	ListInsert(L, 3, 3);            //往第三个位置插入元素3
	for(int i=0; i<L.length; i++){
		printf("L.data[%d]=%d\n", i, L.data[i]);
	}
	return 0;	
}

执行结果如下

image-20241013213806415

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}SqList; 

void InitList(SqList &L){
	for(int i=0; i<MaxSize; i++){
		L.data[i]=i;
		L.length=7;
	}
}

void ListDelete(SqList &L,int i){
	int e=L.data[i-1];
	for(int j=i; j<=L.length; j++){
		L.data[j-1]=L.data[j];      //使用前移法，将后面的值前移一位 
	}
	printf("L.data[%d]=%d is deleted\n",i-1,e);
	L.length--;
}

int main(){
	SqList L;
	InitList(L);
	ListDelete(L, 3);
	for(int i=0; i<L.length; i++){
		printf("L.data[%d]=%d\n", i, L.data[i]);
	}
	return 0;
}

执行结果如下

image-20241014000318515

按位查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L){
	for(int i=0; i<MaxSize; i++){
		L.data[i]=i;
		L.length=7;
	}
}

int GetElem(SqList L, int i){
	return L.data[i-1];
}

int main(){
	SqList L;
	InitList(L);
	for(int i=0; i<MaxSize; i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	}
	int elem=GetElem(L, 3);
	printf("find the elem is %d",elem);
	return 0;
}

执行结果如下

image-20241014002345383

按值查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L){
	for(int i=0; i<MaxSize; i++){
		L.data[i]=i;
		L.length=7;
	}
}

int LocateElem(SqList L, int e){
	for(int i=0; i<L.length; i++){
		if(L.data[i]==e){
			return i;
		}
	}
	return 0;
}

int main(){
	SqList L;
	InitList(L);
	int elem=LocateElem(L, 4);
	printf("find the elem in data[%d]",elem);
	return 0;	
}

执行结果如下

image-20241014235304529

链表

单链表

表的定义

不带头结点类型

定义LNode结构体并且使用别名LNode, *LinkList，其实就是为了区别表示的意思是结点还是指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdlib.h>
typedef struct LNode{        
	int data;				//数据域 
	struct LNode *next;     //指针域
}LNode, *LinkList;          

bool InitList(LinkList &L){
	L=NULL;
	return true;
}

int main(){
	LinkList L;
	InitList(L);
   	return 0;
}
带头结点类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));   //分配头结点 
	if(L==NULL){                       //内存不够分配失败 
		return false;
	}
	L->next=NULL;
	return true;
}

int main(){
	LinkList L;
	InitList(L);
	return 0;
}

表的基本操作

插入元素
按位序插入

带头结点类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LinkList &L, int i, int e){
	if(i<1){
		return false;
	}  
	LNode *p;                  //指针p指向当前扫描结点
	int j=0;                   //当前p指向第几个结点 
	p=L;                       //指向头结点
	while(p!=NULL && j<i-1){   //循环找到第i-1个结点
		p=p->next;
		j++;
	} 
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

不带头结点类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LinkList &L, int i, int e){
	if(i<1){
		return false;
	}
	if(i==1){
		LNode *s=(LNode*)malloc(sizeof(LNode));
		s>data=e;
		s->next=L;
		L=s;                    //将头指针指向新结点
		return true;
	}
	LNode *p;                   //指针p指向当前扫描结点
	int j=0;                    //当前p指向第几个结点 
	p=L;                        //指向头结点
	while(p!=NULL && j<i-1){
		p=p->next;
		j++;
	} 
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
指定结点的后插操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool InsertNextNode(LNode *p, int e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL){
		return false;
	}
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true; 
}
指定结点的前插操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool InsertNextNode(LNode *p, int e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL){
		return false;
	}
	s->next=p->next;
	p->next=s;
    s->data=p->data;          //将p的data值复制到s
    p->data=e;                //将e的值覆盖到p的data
	return true; 
}
删除元素
按位序删除(带头结点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListDelete(LinkList &L, int i, int &e){
	if(i<1){
		return false;
	}
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++; 
	}
	if(p==NULL){
		return false;
	}
	if(p->next==NULL){       //第i-1个结点后无其他结点 
		return false;
	}
	LNode *q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return true;	
}
指定结点删除

算法思想就是先指定q指针指向删除结点的后一结点，继续将指定删除的结点与其后一结点的数据域交换，然后删除节点的指针域赋值为后一结点的指针域，最后释放指针q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool DeleteNode(LNode *p){
	if(p==NULL){
		return false;
	}
	LNode *q=p->next;
	p->data=p->next->data;
	p->next=q->next;
	free(q);
	return true;
}
查找结点
按位查找(带头结点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

//返回第i个结点指针
LNode *  GetElem(LinkList L, int i){
	if(i<0){
		return NULL;
	}
	LNode *p;  //指针p指向当前扫描结点 
	int j=0;   //当前p指向的结点 
	p=L;
	while(p!=NULL && j<i){
		p=p->next;
		j++;
	} 
	return p;
}
按值查找(带头结点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

LNode * LocateElem(LinkList L,int e){
	//头结点不存放数据，直接指向头结点下一结点 
	LNode *p=L->next;               
	while(p!=NULL && p->data!=e){
		p=p->next;
	}
	return p;
}
求表的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

int LengthList(LinkList L){
	int len=0;
	LNode *p;
	p=L;
	while(p->next!=NULL){
		p=p->next;
		len++;
	}
	return len;
}
表的建立
尾插法

算法思想是设置了头指针和尾指针，这样可以使时间复杂度O降低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

//正向建立单链表 
LinkList List_TailInsert(LinkList &L){   
	int x;
	L=(LinkList)malloc(sizeof(LNode));    //建立头结点 
	LNode *s,*r=L;                        //r为表尾指针 
	scanf("%d",&x);
	while(x!=9999){                       //输入9999退出循环
		s=(LNode*)malloc(sizeof(LNode));  //申请新结点 
		s->data=x;
		r->next=s;
		r=s;
		scanf("%d",&x); 
	}
	r->next=NULL;
	return L;
}

int main(){
	LinkList L;
	LinkList list=List_TailInsert(L);
	return 0;
}
头插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x=0;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	}
	return L;
}

双链表

表的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

bool InitDLinkList(DLinkList &L){
	L=(DNode*)malloc(sizeof(DNode));
	if(L==NULL){
		return false;
	}
	L->prior=NULL;
	L->next=NULL;
	return true;
}

int main(){
	DLinkList L;
	InitDLinkList(L);
	return 0;
}

表的基本操作

表的插入
后插入结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

bool InsertNextDNode(DNode *p, DNode *s){
	if(p==NULL || S==NULL){
		return false;
	}
	s->next=p->next;
	if(p->next!=NULL){    //如果p结点有后继节点 
		p->next->prior=s;  
	}
	s->prior=p;
	p->next=s;
	return true; 
}
表的删除
删除后继结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

bool DeleteNextDNode(DNode *p){
	if(p==NULL){
		return 0;
	}
	DNode *q=p->next;     //找到p的后继结点
	if(q==NULL){          //无后继结点 
		return false;
	}
	p->next=q->next;
	if(q->next!=NULL){    //q结点不是最后一个结点 
		q->next->prior=p;
	}
	free(q);
	return true;
}

栈

顺序栈

栈的定义

1
2
3
4
5
6
7
8
9
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int top;
}SqStack;

void InitStack(SqStack &S){
	S.top=-1;
}

进栈操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int top;
}SqStack;

bool Push(SqStack &S ,int x){
	if(S.top==MaxSize-1){   //栈满 
		return false;
	}
	S.top=S.top+1;          //栈顶指针加一 
	S.data[S.top]=x;
	return true;
}

出栈操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int top;
}SqStack;

bool Pop(SqStack &S, int &x){
	if(S.top==-1){     //栈空
		return false;
	}
	x=S.data[S.top];
	S.top=S.top-1;
	return true;
}

读取栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int top;
}SqStack;

bool GetTop(SqStack &S, int &x){
	if(S.top==-1){     //栈空
		return false;
	}
	x=S.data[S.top];
	return true;
}

链栈

栈的定义

1
2
3
4
typedef struct StackNode{
	int data;
	struct StackNode *next;
}StackNode,*LinkStack;

进栈操作

带头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct StackNode{
	int data;
	struct StackNode *next;
}StackNode,*LinkStack;

bool Push(LiStack *S, int x){
	StackNode *p=(StackNode*)malloc(sizeof(StackNode));
	if(p==NULL){        //内存分配失败 
		return false;
	}
	p->data=x;
	p->next=S->next;
	S=p;                //修改栈顶指针 
	return true;
}

出栈操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct StackNode{
	int data;
	struct StackNode *next;
}StackNode,*LinkStack;

bool Pop(LinkStack &S, int &x){
	if(S==NULL){
		return false;
	}
	StackNode *p=(StackNode*)malloc(sizeof(StackNode));
	x=S->data;
	p=S;          //暂时保存被删除的栈顶元素 
	S=S->next;
	free(p);	  //释放内存 
	return true;
}

队列

顺序队列（循环队列）

队列的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int front,rear;      //队头指针和队尾指针 
}SqQueue;

void InitQueue(SqQueue &Q){
	//初始时，队头队尾指针都指向0
	Q.front=Q.rear=0; 
} 

int main(){
	SqQueue Q;
	InitQueue(Q);
	return 0;
}

判断队列是否为空

1
2
3
4
5
6
7
bool QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front){
        return true;
    }else{
        return false;
    }
}

入队操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int front,rear;      //队头指针和队尾指针 
}SqQueue;

bool EnQueue(SqQueue &Q, int x){
	if((Q.rear+1)%MaxSize==Q.front){  //队列已满 
		return false; 
	}
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MaxSize;
	return true;
}

出队操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int front,rear;      //队头指针和队尾指针 
}SqQueue;

bool DeQueue(SqQueue &Q, int x){
	if(Q.rear==Q.front){  //队空报错 
		return false; 
	}
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true;
}

链式队列

队列的定义

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct LinkNode{
	int data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front,*rear;
}LinkQueue;

void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next=NULL;
}

判断队列是否为空

1
2
3
4
5
6
7
bool IsEmpty(LinkQueue Q){
	if(Q.front==Q.rear){
		return true;
	}else{
		return false;
	}
}

入队操作

1
2
3
4
5
6
7
void EnQueue(LinkQueue &Q, int x){
	LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
	s->data=x;
	s->next=NULL;
	Q.rear->next=s;
	Q.rear=s;       //修改尾指针 
}

出队操作

1
2
3
4
5
6
7
8
9
10
11
12
13
void DeQueue(LinkQueue &Q, int &x){
	if(Q.front==Q.rear){  //队空 
		return false;
	} 
	LinkNode *p=Q.front->next;
	x=p->data;
	Q.rear->next=p->next;
	if(Q.rear==p){
		Q.rear==Q.front;  //原队列只有一个结点，删除后变空 
	} 
	free(p);
	return true; 
}

串

顺序串

串的定义

静态数组

1
2
3
4
5
#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

动态数组(堆分配存储)

1
2
3
4
5
6
7
8
typedef struct{
    char *ch;
    int length;
}HString;

HString S;
S.ch=(char*)malloc(MAXLEN*sizeof(char));  //需要手动free
S.length;

求子串

返回第pos个字符起，长度为len的子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

bool SubString(SString &Sub, SString S, int pos, int len){
	//字串范围越界判断
	if(pos+len-1 > S.length){
		return false;
	} 
	for(int i=pos;i<pos+len;i++){
		Sub.ch[i-pos+1]=S.ch[i];
	}
	Sub.length=len;
	return true;
}

比较操作

1
2
3
4
5
6
7
8
int StrCompare(SString S, SString T){
	for(int i=0; i<S.length && i<T.length; i++){
		if(S.ch[i]!=T.ch[i]){
			return S.ch[i]-T.ch[i];
		}
	}
	return S.length-T.length;
}

定位操作

若主串S中存在与串T值相同的子串，返回在S串中第一次出现位置

1
2
3
4
5
6
7
8
9
10
11
12
13
int Index(SString S, SString T){
	int i=1, n=StrLength(S),m=StrLength(T);
	SString sub;    //用于暂存子串
	while(i<n-m+1){
		SubString(sub,S,i,m);
		if(StrCompare(sub,T)!=0){
			++i;
		}else{
			return i;
		}
	} 
	return 0;
}

链串

串的定义

1
2
3
4
typedef struct StringNode{
    char ch;   //结点可存放多个字符，如ch[4]
    struct StringNode *next;
}StringNode,*String;

树

二叉树

树的定义

顺序二叉树

1
2
3
4
5
6
7
8
9
10
#define MaxSize 100
struct TreeNode{
    int value;     //结点数据元素
    bool isEmpty;  //结点是否为空
}

TreeNode t[MaxSize];
for(int i=0; i<MaxSize; i++){
   t[i].isEmpty=true; 
}

链式二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdlib.h>
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
    //有需求找父节点可添加指针
    //struct BiTNode *parent;
}BiTNode,*BiTree;

//定义一棵空树
BiTree root=NULL;

//插入根结点
root=(BiTree*)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;

遍历

先序遍历

1
2
3
4
5
6
7
void PreOrder(BiTree T){
	if(T!=NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

中序遍历

1
2
3
4
5
6
7
void InOrder(BiTree T){
	if(T!=NULL){
		PreOrder(T->lchild);
        visit(T);
		PreOrder(T->rchild);
	}
}

后序遍历

1
2
3
4
5
6
7
void InOrder(BiTree T){
	if(T!=NULL){
		PreOrder(T->lchild);
		PreOrder(T->rchild);
        visit(T);
	}
}

层次遍历

算法思想：

  1. 初始化一个辅助队列
  2. 根节点入队
  3. 若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾（如果有的话）
  4. 重复3步骤，直至队列为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LevelOrder(BiTree T){
	LinkQueue Q;
	InitQueue(Q);     
	BiTree p;		 
	EnQueue(Q,T);   //将根结点入队
	while(!IsEmpty(Q)){ 
		DeQueue(Q, p);
		visit(p);
		if(p->lchild!=NULL){
			EnQueue(Q,p->lchild);
		} 
		if(p->rchild!=NULL){
			EnQueue(Q,p->rchild);
		}
	}
}

求树的深度

1
2
3
4
5
6
7
8
9
int treeDepth(BiTree T){
	if(T==NULL){
		return 0;
	}else{
		int l=treeDepth(T->lchild);
		int r=treeDepth(T->rchild);
		return l>r ? l+1 : r+1;
	}
}