data structure——树与二叉树

看一下知识点：

  • 树的存储结构
  • 二叉树的存储结构
  • 二叉树的性质
  • 树与二叉树的转换
  • 森林与二叉树的转换
  • 二叉树的遍历算法
  • 非递归的二叉树的遍历算法
  • 树的遍历算法
  • 森林的遍历算法
  • 线索二叉树，结构，遍历算法
  • 赫夫曼树和编码
  • 二叉树的确定
  • 二叉树的估计
  • 二叉树表达式

树的存储结构

  • 顺序存储结构
    即定义一个数组来存储，如：int tree[maxsize];。用数组下标来表示树中的结点，数组元素中的内容表示该结点的双亲结点。所以又称为双亲存储结构。

  • 链式存储结构
    主要有孩子存储结构和孩子兄弟存储结构两种。

二叉树的定义
满足条件：
1，每个结点最多只有两棵子树
2,子树有左右顺序之分。

二叉树的存储结构

  • 顺序存储结构（适用于完全二叉树）完全二叉树的顺序存储结构 图中右边的规则只是适合完全二叉树，（如果用来储存一般的二叉树会浪费大量的存储空间）且是从0开始编号的。
  • 链式存储结构（又名二叉链表存储结构）
    1
    2
    3
    4
    5
    6
    typedef struct BTNode
    {
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    如下图：二叉链表1
  • 树的孩子兄弟存储结构
    可以用于树等结构，可以将树变为二叉树，然后再用链式存储，其实也是链式存储，和上面那个是一样的意思。树的孩子兄弟储存结构

满二叉树
在一棵二叉树中，所有所有的分支结点都有左右孩子，并且所有的叶子结点都集中在二叉树的最后一层。

完全二叉树
求完全二叉树的高度(h)（完全二叉树与结点个数有关系）
看规律：
高为1 共有 2^1-1 个结点
高为2 共有 2^2-1 个结点
高为3 共有 2^3-1 个结点
… …

高为h 共有 2^h-1 个结点

所以也可以知道高度为h的完全二叉树的结点的个数n在这个范围内
2^(h-1)-1< n <=2^h-1
2^(h-1)<= n <2^h 处理方法2：2^(h-1)+1<= n+1 <2^h+1
h-1<=log2n <h (比h-1只大了一个不大于1的小数，所以可以取整)
h-1=下取整log2n <h
所以
h=下取整log2n+1

如果使用处理方法2：那么，可以接着化简：
h-1 < log2(n+1) <= h (比h小了一个不大于1的小数)
上取整：h=上取整log2(n+1)

二叉树的性质
1，总分支数=总结点数-1（所有树结构都满足这个性质） 1

2，叶子结点数n0,单分支结点数n1，双分支结点数n2。
则总结点数=n0+n1+n2 2
总分支数=n1+2n2 （因为叶子结点无分支，单分支结点1个分支，双分支结点2个分支） 3

3，由1和2和3联立方程组，解得：n0=n2+1即得：叶子节点数=双分支结点数+1。

4，空分支数=总结点数+1

树与二叉树的相互转化
把每一个结点的兄弟结点相互连接起来，然后删除父结点与孩子结点的连线，只保留一条，默认的是保留最左边（视觉上的最左的那个）的一个连线。
二叉树转换为树的话，过程相反即可。

树与二叉树的转换

森林与二叉树的相互转换

首先按照将树转换成二叉树的方法，将森林中的每棵树转换为二叉树，然后，将每一个二叉树的根结点的右边的分支连接起来即可。

森林与二叉树的转换 森林与二叉树的转换

二叉树的遍历算法
二叉树的深度优先遍历的算法用到递归这个概念，所以先看一下递归函数，递归有直接递归和间接递归，这里只讲直接递归

1
2
3
4
void r()
{
	r();
}

简单一点讲，递归就是这个函数自己调用自己。在自己中调用自己的时候系统会做一个保护现场的操作，在调用玩自己后，系统又会做一个恢复现场的操作，这样就可以实现原路返回了，且，第一个调用自己的时候，在返回时是最后一个恢复现场的，这里明显有一个先进后出的感觉，这就是使用了“系统栈”，非递归就是使用自己定义的一个栈来进行遍历。

1.深度优先遍历

  • 先序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void preorder(BTNode *p)
    {
    	if(p!=NULL)
    	{
    		Visit(p);
    		preorder(p->lchild);
    		preorder(p->rchild);
    	}
    }
  • 中序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void inorder(BTNode *p)
    {
    	if(p!=NULL)
    	{
    		inorder(p->lchid);
    		Visit(p);
    		inorder(p->rchild);
    	}
    }
  • 后序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void postorder(BTNode *p)
    {
     	if(!p=NULL)
     	{
     		postorder(p->lchid);
     		postorder(p->rchild);
     		Visit(p);
     	}
    }
    例题：写一个算法求一棵二叉树的深度，二叉树以二叉链表为存储方式。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int getDepth(BTNode *p)
    {
    	int LD,RD;
    	if(p=NULL)
    		return 0;
    	else
    	{
    		LD=getDepth(p->lchid);
    		RD=getDepth(p->rchild);
    		return (LD>RD?LD:RD)+1; 
    	}
    }
    采用后序遍历方式，先算出左子树的深度LD再算出右子树的深度RD,最后max{LD,RD}+1，加一是因为还有一个根节点。
    其中LD>RD?LD:RD是一个三目运算符，LD如果大于RD就返回LD,如果不大于就返回RD。

例题：在一棵以二叉链表为存储结构的二叉树中，查找data域值等于key的结点是否存在（找到任何一个满足要求的结点即可），如果存在，则将q指向该结点，否则q赋值为NULL，假设data为int型。

1
2
3
4
5
6
7
8
9
10
11
12
13
int search(BTNode *p,BTNode *&q,int key)
{
	if(p!=NULL)
	{
		if(p->data==key)
			q=p;
		else
		{
			search(p->lchild,q,key);
			search(p->rchild,q,key);
		}
	}
}

此算法可以进行修改，因为只需要找到一个满足条件的结点就好，所以当在左子树中找到这个结点了之后就可以直接退出了，如果没有找到，才需要再在右子树中去寻找，这就是所谓的“剪枝操作”，所以代码修改如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search(BTNode *p,BTNode *&q,int key)
{
	if(p!=NULL)
	{
		if(p->data==key)
			q=p;
		else
		{
			search(p->lchild,q,key);
			if(q==NULL)
				search(p->rchild,q,key);
			
		}
	}
}

例题：假设二叉树采用二叉链表存储结构存储，编写一个程序，输出先序遍历序列中第k个结点的值，假设k不大于总的结点数（结点data域类型为char型）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int n=0;
void trave(BTNode *p,int k)
{
	if(p!=NULL)
	{
		++n;
		if(k==n)
		{
			cout<<p->data<<endl;
			return;
		}
		trave(p->lchild,k);
		trave(p->rchild,k);

	}
}

若是中序或者后序遍历的话，代码如下：

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(BTNode *p,int k)  //中序
{
	if(p!=NULL)
	{
		trave(p->lchild,k);
		++n;
		if(k==n)
		{
			cout<<p->data<<endl;
			return;
		}
		trave(p->rchild,k);
	}
}

void trave(BTNode *p,int k)  //后序
{
	if(p!=NULL)
	{
		trave(p->lchild,k);
		trave(p->rchild,k);
		++n;
		if(k==n)
		{
			cout<<p->data<<endl;
			return;
		}

	}
}

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
void level(BTNode *p)
{
	int front,rear;
	BTNode *que[maxsize]；  //定义一个循环列表，来记录要访问的一个层次上的结点
	front=rear=0;
	BTNode *q;  //遍历指针
	if(p!=NULL)
	{
		rear=(rear+1)%maxsize； //入队
		que[rear]=p;  //根节点入队
		while(front!=rear)  //队列不空的时候循环
		{
			front=(front+1)%maxsize;  //出队
			q=que[front];  //队头结点出队
			Visit(q);  //访问队头结点
			if(q->lchild!=NULL)  //如果左子树不空,
			{
				rear=(rear+1)%maxsize;
				que[rear]=q->lchild;  //则左子树的根结点就入队
			}
			if(q->rchild!=NULL)  //右子树如果不空，
			{
				rear=(rear+1)%maxsize;
				que[rear]=q->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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
typedef struct
{
	BTNode *p;  //结点指针
	int lno;  //结点的层次号
}St;

int maxNode(BTNode *b)
{
	St que[maxsize];
	int front,rear;
	int Lno,i,j,n,max;
	front=rear=0;
	BTNode *q;
	if(b!=NULL)
	{
		++rear;
		que[rear].p=b;
		que[rear].lno=1;
		while(front!=rear)
		{
			++front;
			q=que[front].p;
			Lno=que[front].lno;
			if(q->lchild!=NULL)
			{
				que[rear].p=q->lchild;
				que[rear].lno=Lno+1;
			}
			if(q->rchild!=NULL)
			{
				++rear;
				que[rear].p=q->rchild;
				que[rear].lno=Lno+1;
			}
		}
		max=0;  //循环比较Lno，找出最大值，即为最大层数
		for(i=1;i<=Lno;++i)
		{
			n=0;
			for(j=1;j<=rear;++j)
				if(que[j].lno==i)
					++n;
				if(max<n)
					max=n;
		}
		return max;
	}
	else return 0;
}

树的遍历算法：
树只有先序遍历和后序遍历算法，没有中序遍历算法。
如果将一棵树转换成二叉树后，那么对应对这个二叉树进行先序遍历就想当于对树进行先序遍历；对这个二叉树树进行中序遍历就相当于对这个树进行后序遍历。

  • 树的先序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void preOrder(TNode* p,TNode tree[])
    {
    	if(p!=NULL)
    	{
    		visit(p);
    		Branch* q;
    		q=p->first;
    		while(q!=NULL)
    		{
    			preOrder(&tree[q->cIdx],tree);
    			q=q->next;
    		}
    	}
    }
  • 树的后序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void preOrder(TNode* p,TNode tree[])
    {
    	if(p!=NULL)
    	{
    		
    		Branch* q;
    		q=p->first;
    		while(q!=NULL)
    		{
    			preOrder(&tree[q->cIdx],tree);
    			q=q->next;
    		}
    		visit(p);
    	}
    }
  • 树的层次遍历
    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 level(TNode *tn,TNode tree[])
    {
    	int front,rear;
    	TNode *que[maxSize];
    	front=rear=0;
    	TNode *p;
    	if(tn!=NULL)
    	{
    		rear=(rear+1)%maxSize;
    		que[rear]=tn;
    		while(front!=rear)
    		{
    			front=(front+1)%maxSize;
    			p=que[front];
    			visit(p);
    			Branch* q=p->first;
    			while(q!=NULL)
    			{
    				rear=(rear+1)%maxSize;
    				que[rear]=&tree[q->cIdx];
    				q=q->next;
    			}
    		}
    	}
    }

森林的遍历算法：
森林也只有先序遍历和后序遍历。
如果将一森林转换成二叉树后，那么对应对这个二叉树进行先序遍历就想当于对森林进行先序遍历；对这个二叉树进行中序遍历就相当于对这个森林进行后序遍历。

二叉树的遍历算法的改进：

  • 先序遍历的非递归算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void preorderNonrecursion(BTNode *bt) //传入一个二叉树结点类型的指针
    {
    	if(bt!=NULL)
    	{
    		BTNode *Stack[maxsize];  //建立了一个辅助栈
    		int top=-1;
    		BTNode *p;  //遍历指针
    		Stack[++top]=bt;
    		while(top!=-1)
    		{
    			p=Stack[top--];  //先出栈
    			Visit(p);
    			if(p->rchild!=NULL)  //如果右孩子存在就入栈
    				Stack[++p]=p->rchild;
    			if(p->lchild!=NULL)  //如果左孩子存在就入栈
    				Stack[++top]=p->lchild;
    		}
    	}
    }
  • 中序遍历的非递归算法

中序遍历的规则是：根结点入栈，栈顶结点的左孩子存在就入栈， 一直向左走，一直走到不能向左走了，即栈顶结点的左孩子不存在，则出栈并输出栈顶结点。然后向右走一步，如果栈顶结点的右孩子存在就入栈，再从这个右孩子向左一直走，走到不能向左走为止。不能走了就出栈，看其右孩子是否有，有的话就向右走一步，。。。就这样一直重复。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void inorderNoncursion(BTNode *bt)
{
	if(bt!=NULL)
	{
		BTNode *Stack[maxsize];
		int top=-1;
		BTNode *p=NULL;		
		p=bt; //p指向根结点
		while(top!=-1||p!=NULL)
		{
			while(p!=NULL)
			{
				Stack[++top]=p;
				p=p->lchild;
			}
			if(top!=-1)
			{
				p=Stack[top--];
				Visit(p);
				p=p->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
    void postorderNoncursion(BTNode *bt)
     {
     	if(bt!=NULL)
     	{
     		BTNode *Stack1[maxsize];  //定义一个辅助遍历的栈
     		int top1=-1;
     		BTNode *Stack2[maxsize];  //定义一个用来逆序的栈
     		int top2=-1;
     		BTNode *p=NULL;  //遍历指针
     		Stack1[++top1]=bt;  //根结点入栈Stack1
     		while(top1!=-1)
     		{
     			p=Stack1[top1--];  //出栈S1
     			Stack2[++top2]=p;  //上一步出栈出来的元素入栈到S2
     			if(p->lchild!=NULL)
     				Stack1[++top1]=p->lchild;  //左孩子先入栈
     			if(p->rchild!=NULL)
     				Stack1[++top1]=p->rchild;  //右孩子入栈
     		}
     		while(top2!=-1)
     		{
     			p=Stack2[top2--]; //出栈,
     			Visit(p); //后打印
     		}
     	}
     }

二叉树的估计

二叉树的表达式


本文章主要整理于《数据结构高分笔记》和《率辉数据结构辅导专栏》微信号:辉解读。