Tree 树

Tree-Code

树(Tree) 是n（n>0）个结点的有限集，它或为空树（n=0）;或为非空树，对于非空树T：

• 有且仅有一个称之为根(Root)的结点；
• 除根结点以外的其余结点可分为m（m>0）个互不相交的有限集T1，T2，…Tm，其中每一个集合本身又是一颗树，并且称为根的子树（SubTree）。

树的存储结构

双亲表示法

• 求结点的双亲十分方便，也很容易求输的根。但求结点的孩子时需要遍历整个结构。
• 索引到Parent的 时间复杂度为 O(1)*

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

#define MAX_TREE_SIZE 100
typedef int ElemType;
 
//双亲结点
typedef struct PTNode //定义树中的一个结点
{
	ElemType data;
	int parent;
}PTNode;
 
//树结构
typedef struct
{
	PTNode nodes[MAX_TREE_SIZE];
	int r;      //根的位置索引
	int n;     //树中结点的总数
}PTree;

孩子表示法

双亲孩子表示法

孩子兄弟表示法

左孩子右兄弟

Binary Tree 二叉树

二叉树( Binary Tree)是n (n≥0)个结点所构成的集合，它或为空树(n=0);或为非空树，对于非空树T

• (1)有且仅有一个称之为根的结点;
• (2)除根结点以外的其余结点分为两个互不相交的子集T1和T2,分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。

二叉树与树一样具有 递归性质，二叉树与树的区别主要有以下两点

• (1)二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点);

• (2)二叉树的子树有左右之分，其次序不能任意颠倒。

• 二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。

性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
性质2：深度为k的二叉树至多有2^k -1个结点(k>=1)
性质3：对任何一颗二叉树T,如果其终端结点数为n0，度为2的节点数为呢n2，则n0 = n2 + 1

• n=n0+n1+n2; 连接数总是等于总结点数n-1，并且等于 n1+2*n2
• n-1 = n1+2*n2
• n0+n1+n2 -1 = n1+n2+n2
• n0 = n2 +1

性质4：具有n个结点的完全二叉树的深度为 向下取整 k = 『logn』 +1
性质5：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

满二叉树

深度为 k 且含有n = 2^k -1个结点的二叉树；
满二叉树的深度 k 为 n = 2^k -1 –> 求log 取对数 求k

完全二叉树

对于深度为K的有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
对于倒数第二层的满二叉树的结点数 n = 2^(k-1) -1
所以完全二叉树的节点数的取值范围是： 2^(k-1) -1 < n <= 2^k -1

• 由于 n 是整数，n <= 2^k -1 可以看成 n < 2^k
• 同理 2^(k-1) -1 < n 可以看成 2^(k-1) <= n
• 所以 2^(k-1) <= n < 2^k
• 不等式两边同时取对数，得到 k-1 <= logn < k
• 由于k是深度，为整数，所以 向下取整 k = 『logn』 +1

二叉树的存储结构

• 满二叉树或完全二叉树可以用顺序存储结构 存储
• 但是一般二叉树或斜树太过浪费空间 用链表存储*

二叉链表

1
2
3
4
5
6

typedef struct BiTNode
{
	ElemType data;
	struct BitNode *lchild,*rchild;
	
}BiTNode,*BiTree;

三叉链表 多一个指向双亲结点的指针

二叉树的遍历

• 先序遍历，中序遍历，后序遍历 ->时间复杂度均为O(n)；

先序遍历二叉树的操作定义如下：

• 若二叉树为空，则空操作;否则
• (1)访问根结点;
• (2)先序遍历左子树;
• (3)先序遍历右子树。

1
2
3
4
5
6
7
8
9

void InOrderTraverse(BiTree T)
{
	if(T) //若二叉树非空
	{
		cout<<T->data;	//访问根结点
		InOrderTraverse(T -> lchild);//前序遍历左子树
		InOrderTraverse(T -> Rchild);//前序遍历右子树
	}	
}

中序遍历二叉树的操作定义如下：

• 若二叉树为空，则空操作;否则
• (1)中序遍历左子树;
• (2)访问根结点;
• (3)中序遍历右子树。

1
2
3
4
5
6
7
8
9

void InOrderTraverse(BiTree T)
{
	if(T) //若二叉树非空
	{
		InOrderTraverse(T -> lchild);//中序遍历左子树
		cout<<T->data;	//访问根结点
		InOrderTraverse(T -> Rchild);//中序遍历右子树
	}	
}

后序遍历二叉树的操作定义如下：

• 若二叉树为空，则空操作;否则
• (1)后序遍历左子树;
• (2)后序遍历右子树;
• (3)访问根结点。

1
2
3
4
5
6
7
8
9

void InOrderTraverse(BiTree T)
{
	if(T) //若二叉树非空
	{
		InOrderTraverse(T -> lchild);//后序遍历左子树
		InOrderTraverse(T -> Rchild);//后序遍历右子树
		cout<<T->data;	//访问根结点
	}	
}

前序遍历查找节点深度.cpp

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

#include <stdio.h>
#include <stdlib.h>
//AB_D__CE___

typedef char ElemType;
 
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, * BiTree; // BITNODE <--> STRUCT BITNODE


//创建一颗二叉树 
void CreateBiTree(BiTree &T)
{
	char c;
	
	scanf("%c",&c);
	if(' ' == c)
	{
		T =NULL;
	}
	else
	{
		T = (BiTNode *)malloc(sizeof(BiTNode));
		T->data = c;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
} 

//访问二叉树结点的具体操作 
void visit(char c,int level)
{
	printf("%c位于第%d层\n",c,level);
}

//前序遍历二叉树
void PreOrderTraverse(BiTree T,int level)
{
	if(T)
	{
		visit(T->data,level);
		PreOrderTraverse(T->lchild,level+1); 
		PreOrderTraverse(T->rchild,level+1); 
	}
} 

int main()
{
	int level = 1;
	BiTree T;
	 
	CreateBiTree(T);
	
	PreOrderTraverse(T,level); 
	
	return 0;
}

线索二叉树

• 遍历线索二叉树的时间复杂度为 O(n),空间负责度为O(1);->这是因为线索二叉树的遍历不需要使用栈来实现递归操作。

中序遍历

1
2
3
4
5
6

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild, *rchild;//左右孩子指针
	int LTag,RTag;	//左右标志
}BiTNode, * BiTree;

Tag 标志为0，表示左右孩子；标志为1，表示前驱后继

树与森林的遍历

树的先根遍历 ：ABEFCGDHIJ
树的后根遍历 ：EFBGCHIJDA

树、森林 和 二叉树 遍历关系

树、森林的 前 根遍历和 转换成二叉树 的 前 序遍历结果相同
树、森林的 后 根遍历和 转换成二叉树 的 中 序遍历结果相同

感谢阅读

• ← Previous Post
• Next Post →