logo
小吃货落樱
banner
数据结构的世界

BinaryTree

Scroll down

二叉树

顺序存储

1
2
3
4
5
6
7
8
9
//顺序存储的结构体
#pragma once
#define MAXSIZE 16
typedef int ElemType;

typedef struct tree{
	ElemType data[MAXSIZE];
	int size;
}Tree;

顺序存储基本操作

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#pragma once
#include"struct.h"

//函数声明

//初始化树
void initTree(Tree &T);

//创建树
void createTree(Tree &T);

//打印树
void printTree(Tree T);

//寻找树的左孩子
ElemType find_left_child(Tree T,int i);

//寻找树结点的右孩子
ElemType find_right_child(Tree T,int i);

//需找结点的双亲
ElemType find_parent(Tree T,int i);


//函数实现

//初始化树
void initTree(Tree &T)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		T.data[i]=0;
	}
	T.size=0;
}


//创建树
void createTree(Tree &T)
{
	ElemType x;
	scanf("%d",&x);
	int i=0;
	while(x!=999)
	{
		T.data[i++]=x;
		T.size++;
		scanf("%d",&x);
	}
}

//打印树
void printTree(Tree T)
{
	for(int i=0;i<T.size;i++)
	{
		ElemType x=T.data[i];
		printf("%d ",x);
	}
	printf("\n");

}

//寻找树的左孩子
ElemType find_left_child(Tree T,int i)
{
	int pos=2*i+1;
	if(pos>T.size-1)
	{
		return -999;
	}else{
		return T.data[pos];
	}

}

//寻找树结点的右孩子
ElemType find_right_child(Tree T,int i)
{
	int pos=2+2*i;
	if(pos>T.size-1)
	{
		return -999;
	}else{
		return T.data[pos];
	}
}

//需找结点的双亲
ElemType find_parent(Tree T,int i)
{
	if(i==0)
	{
		return -999;
	}else{
		return T.data[(i-1)/2];
	}
}

题目

已知二叉树按顺序存储方式存储，设计一个算法，求编号i和j两个结点的最近公共祖先结点的值

下面是用递归和非递归来编写的函数（此处顺序存储是从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
32
33
34
35
36
//已知二叉树按顺序存储方式存储，设计一个算法，求编号i和j两个结点的最近公共祖先结点的值
ElemType co_ancestor(Tree T,int i,int j)
{
	if(T.data[i]!=0&&T.data[j]!=0)
	{
		while(i!=j)
		{	//谁的辈分小，谁先找父亲
			if(i>j)
			{
				i=(i-1)/2;
			}else{
				j=(j-1)/2;
			}
		}
	return T.data[j];
	}else{
	return -999;
	}
}


ElemType co_ancestor2(Tree T,int i,int j)
{	
	if(i==j)
	{
		return T.data[i];
	}
	else if(i>j)
	{
		i=(i-1)/2;
		return co_ancestor(T,i,j);
	}else{
		j=(j-1)/2;
		return co_ancestor(T,i,j);
	}
}

链式存储

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#pragma once
typedef int ElemType;
//链式存储的结构体
typedef struct BiTNode {
	ElemType data;
	BiTNode *lchild;
	BiTNode *rchild;
}*BiTree,BiTNode;

//基本操作

//初始化二叉树
void initTree(BiTree &T);

//创建二叉树
void createTree(BiTree &T);

//前序遍历
void preOrder(BiTree T);

//中序遍历
void inOrder(BiTree T);

//后序遍历
void postOrder(BiTree T);


//初始化二叉树
void initTree(BiTree &T)
{
	T=NULL;
}

//创建二叉树
void createTree(BiTree &T)
{
	ElemType x;
	scanf("%d",&x);
	if(x==0)
	{
		return;
	}else{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=x;
		T->lchild=NULL;
		T->rchild=NULL;
		createTree(T->lchild);
		createTree(T->rchild);
	}//递归
}

//递归实现二叉树遍历

//前序遍历
void preOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}else{
		printf("%d ",T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}

}

//中序遍历
void inOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}else{
		inOrder(T->lchild);
		printf("%d ",T->data);
		inOrder(T->rchild);
	}
}

//后序遍历
void postOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}else{
		postOrder(T->lchild);
		postOrder(T->rchild);
		printf("%d ",T->data);
	}
}


二叉树遍历（非递归）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
//前序和中序都比较简单，后序较难

//前序遍历
void preOrder(BiTree T)
{
	Stack S;
	initStack(S);
	BiTNode *pre=T;
	while(pre!=NULL||!isEmpty(S))
	{
		if(pre!=NULL)
		{
			printf("%d ",pre->data);
			push(S,pre);
			pre=pre->lchild;
		}else{
			BiTNode *top=pop(S);
			pre=top->rchild;
		}
	}

}

//中序遍历
void inOrder(BiTree T)
{
	Stack S;
	initStack(S);
	BiTNode*pre=T;
	while(pre||!isEmpty(S))
	{
		if(pre){
			push(S,pre);
			pre=pre->lchild;
		}else{
			BiTNode *top=pop(S);
			printf("%d ",top->data);
			if(top->rchild)
			{
				pre=top->rchild;
			}//可以直接优化为pre=top->rchild

		}
	}
	
}

层次遍历

结构体（队列+树）

我采用的是顺序队列

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
#pragma once
typedef int ElemType;
#define MAXSIZE 8

//二叉树
typedef struct BiTNode {
	ElemType data;
	BiTNode *lchild;
	BiTNode *rchild;
}*BiTree,BiTNode;

//队列
typedef BiTNode* Type;
typedef struct{
	Type data[MAXSIZE];
	int front;
	int rear;
	int size;
}SeQueue;

//栈
typedef struct Stack{
	Type data[MAXSIZE];
	int top;
	int length;
}SqStack;


基本操作

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
34
35
36
37
38
39
40
41
42
43
#pragma once
#include<stdio.h>
#include"struct.h"

//-------队列----------
//初始化队列
void initQueue(SeQueue &Q);

//判断队列是否为空
bool isEmpty(SeQueue Q);

//元素入队
bool enQueue(SeQueue &Q,Type x);

//出队
Type deQueue(SeQueue &Q);

//获取队头
Type getHead(SeQueue Q);

//获取队列长度
int getSize(SeQueue Q);

//--------------------树----------------------
//初始化二叉树
void initTree(BiTree &T);

//创建二叉树
void createTree(BiTree &T);

//前序遍历
void preOrder(BiTree T);

//中序遍历
void inOrder(BiTree T);

//后序遍历
void postOrder(BiTree T);

//层序遍历
void levekOrder(BiTree T);


队列

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include"basic.h"
#include"struct.h"

//初始化队列
void initQueue(SeQueue &Q)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		Q.data[i]=0;
	}
	Q.size=0;
	Q.front=0;
	Q.rear=0;
}

//判断队列是否为空
bool isEmpty(SeQueue Q)
{
	return Q.front==Q.rear;
	//return Q.size==0;

}

//元素入队
bool enQueue(SeQueue &Q,Type x)
{
	if(Q.rear>=MAXSIZE)//Q.rear>=MAXSIZE
	{
		return false;
	}
	Q.data[Q.rear++]=x;
	Q.size++;
	return true;
}

//出队
Type deQueue(SeQueue &Q)
{
	if(isEmpty(Q))
	{
		return NULL;
	}else{
		Q.size--;
		return Q.data[Q.front++];
	}

}

//获取队头
Type getHead(SeQueue Q)
{
	if(isEmpty(Q))
	{
		return NULL;
	}
	return Q.data[Q.front];
}

//获取队列长度
int getSize(SeQueue Q)
{
	return Q.size;
	//return Q.rear-Q.front
}


栈

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#pragma once
#include"basic.h"
#include<stdio.h>
#include<stdlib.h>
#include"struct.h"

//初始化栈
void initStack(SqStack &S)
{
		S.top=0;
		S.length=0;
}

//判断栈是否为空
bool isEmpty(SqStack S)
{
	return S.top==0?true:false;
}

//如果栈没有满，将x入栈
bool push(SqStack &S, Type x)
{
	if(S.length>MAXSIZE)//S.top>MAXSIZE
	{
		return false;
	}else{
		S.data[S.top]=x;
		S.top++;
	}
	S.length++;
	return true;
}

//如果不为空，则将栈顶元素出栈，并返回
Type pop(SqStack &S)
{
	if(isEmpty(S))
	{
		return NULL;
	}
	Type now=S.data[S.top-1];
	S.top--;
	S.length--;
	return now;
}


//销毁栈
void destroy(SqStack &S)
{
	for(int i=0;i<S.length;i++)
	{
		S.data[i]=0;
	}
	S.length=0;
	S.top=0;
}

//满栈
bool isFull(Stack S)
{
	return S.length>=MAXSIZE;
}

树

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>
#include"basic.h"
#include"struct.h"

//初始化二叉树
void initTree(BiTree &T)
{
	T=NULL;
}

//创建二叉树
void createTree(BiTree &T)
{
	ElemType x;
	scanf("%d",&x);
	if(x==0)
	{
		return;
	}else{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=x;
		T->lchild=NULL;
		T->rchild=NULL;
		createTree(T->lchild);
		createTree(T->rchild);
	}//递归
}

层序遍历

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
void levekOrder(BiTree T)
{
	SeQueue Q;
	initQueue(Q);
	BiTNode* pre=T;
	if(pre)
	{
		enQueue(Q,pre);
		while(!isEmpty(Q))
		{
			BiTNode *head=deQueue(Q);
			printf("%d ",head->data);
			if(head->lchild)
			{
				enQueue(Q,head->lchild);
			}
			if(head->rchild)
			{
				enQueue(Q,head->rchild);
			}
		}

	}

}

题目

1. 给出树自下至上，自右至左的遍历算法
1
1. 给出树自下至上，自右至左的遍历算法

只需要将原来自上至下，自左至右的层序遍历的结果放入栈中，出栈即可得到

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
void level_order(BiTree T)
{
	SeQueue Q;
	Stack S;
	initStack(S);
	initQueue(Q);
	BiTNode *pre=T;
	if(pre)
	{
		enQueue(Q,pre);
		while(!isEmpty(Q))
		{
			BiTNode *head=deQueue(Q);
			push(S,head);
			if(head->lchild)
			{
				enQueue(Q,head->lchild);
			}
			if(head->rchild)
			{
				enQueue(Q,head->rchild);
			}
		}
	}
	while(!isEmptyS(S))
	{
		Type x=pop(S);
		printf("%d ",x->data);
	}
}

测试样例及结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"basic.h"

int main()
{
	BiTree T;
	initTree(T);
	createTree(T);
	level_order(T);
	system("pause");
	return 0;
}

10 20 40 0 60 0 0 50 0 0 30 0 0
60 50 40 30 20 10 请按任意键继续. . .
2.求二叉树的高度
1
2.假设采用二叉树存储，设计一个非递归算法求二叉树的高度

思路：利用层次遍历，每遍历完一层高度加一，利用队列，每次可以只进队一层

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
//2.假设二叉树采用二叉链表来存储，求二叉树的高度
int  tree_height(BiTree T)
{
	if(T==NULL)
	{
		return 0;
	}
	SeQueue Q;
	initQueue(Q);
	BiTNode *pre=T;
	int height=0;//用来记录层数
	enQueue(Q,pre);
	while(!isEmpty(Q))
		{
			int size=Q.size;//每次循环都会初始化
			for(int i=0;i<size;i++)//注意每轮都只会出队一个，但是会入队多个
			{
				BiTNode*head=deQueue(Q);
				if(head->lchild){
					enQueue(Q,head->lchild);
				}
				if(head->rchild){
					enQueue(Q,head->rchild);
				}
			}
			height++;//每遍历完一层高度就加一
		}
		return height;
}

现在没法画图，我目前就口述吧

本二叉树的创建方式是前序遍历创建的： 10 20 40 0 60 0 0 50 0 0 30 0 0

二叉树高度就为4

虽然本体没有要求递归，但是依旧可以用递归实现本算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//2.递归
int  tree_height1(BiTree T)
{
	if(T==NULL)
	{
		return 0;
	}
	if(T->lchild==NULL&&T->rchild==NULL)
	{
		return 1;
	}
	int lheight=tree_height1(T->lchild);
	int rheight=tree_height1(T->rchild);
	return lheight>rheight?lheight+1:rheight+1;
}

老爷，养我呜呜呜

其他文章
cover
ERROR
  • 24/07/05
  • 21:16
  • 数据结构C语言版
cover
链表
  • 24/07/05
  • 00:46
  • 数据结构C语言版
网站标题

网站运行时间：0天

最后更新时间：00:00:00

目录导航 置顶
  1. 1. 二叉树
    1. 1.1. 顺序存储
      1. 1.1.1. 题目
    2. 1.2. 链式存储
      1. 1.2.1. 二叉树遍历（非递归）
    3. 1.3. 层次遍历
      1. 1.3.1. 结构体（队列+树）
      2. 1.3.2. 基本操作
      3. 1.3.3. 队列
      4. 1.3.4. 栈
      5. 1.3.5. 树
    4. 1.4. 层序遍历
    5. 1.5. 题目
请输入关键词进行搜索
  • to close