数据结构——树和二叉树

树

树的定义

• 树（Tree）是n（n≥0）个结点的有限集，它或为空树（n = 0）；或为非空树，对于非空树T：
  • 有且仅有一个称之为根的结点；
  • 除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
• 树是n个结点的有限集
  
• 树的其他表示方式
  

树的概念

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

树的基本术语

• 根：即根结点(没有前驱)
• 叶子：即终端结点(没有后继)
• 节点：即树的数据元素
• 节点的度：一个节点含有的子树的个数称为该节点的度；
• 树的度：一棵树中，最大的节点的度称为树的度；
• 叶节点或终端节点：度为零的节点；
• 分支节点：即度不为0的结点（也称为内部结点）
• 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次；
• 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
• 节点的祖先：从根到该节点所经分支上的所有节点；
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林：由m（m>=0）棵互不相交的树的集合称为森林；

树的种类

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为*树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
• 二叉树：每个节点最多含有两个子树的树称为二叉树；
• 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均
  已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
• 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
• 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉
  树）；
• 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
• B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

常见应用场景

• xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
• 路由协议就是使用了树的算法
• mysql数据库索引
• 文件系统的目录结构
• 所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构

二叉树

• 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
  • 有且仅有一个称之为根的结点；
  • 除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
• 基本特点
  • 结点的度小于等于2
  • 有序树（子树有序，不能颠倒）
    

二叉树的性质

• 在二叉树的第i层上至多有2^(i-1)个结点
• 深度为k的二叉树至多有2^(k-1)个结点
• 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1 （即n0=n2+1）
• 具有n个结点的完全二叉树的深度必为[log2n]＋1
• 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。

二叉树节点表示

• 案例ly01.py

二叉树遍历

• 深度优先，一般用递归
  • 先序(Preorder)
  • 中序(Inorder)
  • 后序(Postorder)
• 广度优先，一般用队列

---

满二叉树

• 满二叉树_百度百科
• 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
• 国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
  • 满足等比数列公式，具有如下性质
    • 满二叉树的结点数一定是奇数个
    • 第i层上的结点数为：2^i-1
    • 层数为k的满二叉树的叶子结点个数（最后一层）: 2^k-1
• 国外（国际）定义：a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.（如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)）
  • 度为0或者2，不存在度为1的结点

满二叉树和完全二叉树的区别

满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。

---

C++代码实现

#include<iostream>
#include<queue>
using namespace std;

#define OVERFLOW -2 
#define OK 1
#define NULL 0
#define ERROR -1

#define MAXSIZE 100

typedef int Status;

typedef char TelemType;

/*------------------二叉树顺序存储----------------*/
/*
适于存满二叉树和完全二叉树
*/
// typedef TelemType SqBiTree[MAXSIZE];

// SqBiTree bt;  // 包含100存放TelemType类型数据的数组

/*-----------------二叉树链式存储------------------*/

/*
二叉链表
*/
typedef struct BiTNode {
	TelemType data;  // 结点数据域
	struct BiTNode* lchild, * rchild;  // 左右子树指针 
	int flag;  // 后序遍历标志位
}BiTNode, * BiTree;

typedef BiTree SElemType;

typedef struct {
	BiTNode* link;
	int tag;  // 后序遍历标志位
}BElemType;


// 顺序栈结构体
typedef struct {
	SElemType* base;
	SElemType* top;
	int stacksize;
}SqStack;

// 顺序栈初始化
Status InitStack(SqStack& S) {
	S.base = new SElemType[MAXSIZE];
	if (!S.base) return OVERFLOW;
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}

// 判断顺序栈是否为空
bool StackEmpty(SqStack S) {
	if (S.top == S.base) return true;
	else return false;
}

// 判断是否为满栈
bool StackFull(SqStack S) {
	if (S.top - S.base >= S.stacksize)
		return true;
	else return false;
}

// 入栈
Status Push(SqStack& S, BiTree e) {
	if (StackFull(S))  // 满栈 
		return ERROR;
	*S.top++ = e;
	// *S.top = e;
	// S.top ++;
	return OK;
}

// 出栈
Status Pop(SqStack& S, BiTree& e) {
	if (StackEmpty(S))  // 栈空
		return ERROR;
	e = *--S.top;
	// S.top --;
	// e = *S.top;
	return OK;
}

/*
# 遍历规则
- 若二叉树为空树，则空操作
- DLR-先序遍历，先根再左再右
- LDR-中序遍历，先左再根再右
- LRD-后序遍历，先左再右再根
*/


/*--------先序(根)遍历---------*/
// 递归算法
/*
若二叉树为空，则空操作
否则:
	访问根结点 (D)
	中序遍历左子树 (L)
	中序遍历右子树 (R)
*/
void PreOrder(BiTree T) {
	if (T) {
		cout << T->data;
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

// 非递归算法
void PreOrder_1(BiTree T) {
	SqStack S;
	InitStack(S);
	BiTree p = T;
	while (p || !StackEmpty(S)) {
		// p非空且栈非空
		if (p) {
			/*
			输出元素
			保存入栈
			p = p->lchild
			*/
			cout << p->data;
			Push(S, p);
			p = p->lchild;
		}
		else {
			/*
			出栈到p
			p = p->rchild
			*/
			Pop(S, p);
			p = p->rchild;
		}
	}
}


/*--------中序(根)遍历---------*/
// 递归算法
/*
若二叉树为空，则空操作
否则:
	中序遍历左子树 (L)
	访问根结点 (D)
	中序遍历右子树 (R)
*/
void InOrder(BiTree T) {
	if (T) {
		InOrder(T->lchild);
		cout << T->data;
		InOrder(T->rchild);
	}
}

// 非递归算法
void InOrder_1(BiTree T) {
	BiTree p = T;
	SqStack S;
	InitStack(S);
	while (p || !StackEmpty(S)) {
		if (p) {
			/*
			保存--入栈
			p = p->lchild
			*/
			Push(S, p);
			p = p->lchild;
		}
		else {
			/*
			出栈到p
			输出p->data
			p = p->rchild
			*/
			Pop(S, p);
			cout << p->data;
			p = p->rchild;
		}
	}
}




/*
/*--------后序(根)遍历---------*/
// 递归算法
/*
若二叉树为空，则空操作
否则:
	中序遍历左子树 (L)
	中序遍历右子树 (R)
	访问根结点 (D)
*/
void PostOrder(BiTree T) {
	if (T) {
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		cout << T->data;
	}
}

// 非递归算法
void PostOrder_1(BiTree T) {
	/*
	此函数应将数据类型改为"结点+标志位"，即上面代码中BElemType类型
	但由于修改类型后，需重新改写栈相关函数，故将标志位作为结构体BiTNode参数
	*/
	BiTree p = T;
	SqStack S;
	// BElemType w;
	InitStack(S);
	while (p || !StackEmpty(S)) {
		if (p) {
			/*
			保存--入栈 flag = 1（结构体 p,flag）
			p = p->lchild
			*/
			// w.link = p;
			// Push(S,w);
			Push(S, p);
			p->flag = 1;
			// w.tag = 1;
			p = p->lchild;
		}
		else {
			/*
			出栈到p
			switch(flag){
				case '1':
					入栈 flag = 2
					p = p->rchild
				case '2'
					输出 p->data
					p = NULL
			}
			保存--入栈
			p = p->rchild;
			*/
			// Pop(S, w);
			Pop(S, p);
			// p = w.link;
			switch (p->flag) {
			case 1:
				p->flag = 2;
				// w.tag = 2;
				Push(S, p);
				p = p->rchild;
				break;
			case 2:
				cout << p->data;
				// 强制置空
				p = NULL;
				break;
			}
		}
	}
}


// 求二叉树叶子结点的个数
int CountLeaf(BiTree T) {
	// 先序遍历
	// 此处必须为static类型，递归会调用自身，只赋一次值
	static int count = 0;
	if (T) {
		if (!T->lchild && !T->rchild)
			count++;
		CountLeaf(T->lchild);
		CountLeaf(T->rchild);
	}
	return count;
}

// 求二叉树深度
/*
1. 求左二叉树深度
2. 求右二叉树深度
3. 取最大值加1
*/
int Depth(BiTree T) {
	// 后序遍历
	int dl, dr, d;
	if (!T)
		d = 0;
	else {
		dl = Depth(T->lchild);
		dr = Depth(T->rchild);
		d = 1 + (dl > dr ? dl : dr);
	}
	return d;
}

// 复制二叉树
BiTree Copy(BiTree T) {
	BiTree t, newl, newr;
	if (!T) {
		t = NULL;
		return t;
	}
	else {
		if (!T->lchild)
			newl = NULL;
		else
			newl = Copy(T->lchild);
		if (!T->rchild)
			newr = NULL;
		else
			newr = Copy(T->rchild);
		t = new BiTNode;
		t->data = T->data;
		t->lchild = newl;
		t->rchild = newr;
	}
	return t;
}

// 先序创建二叉树
Status CreateBiTree(BiTree& T) {
	char ch;
	cin >> ch;
	if (ch == '#') T = NULL;
	else {
		if (!(T = new BiTNode)) exit(OVERFLOW);
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

int main() {
	// 测试
	BiTree T, t;
	int n;
	CreateBiTree(T);

	
	// 递归遍历
	cout << "先序遍历为：" << endl;
	PreOrder(T);
	cout << endl << "中序遍历为：" << endl;
	InOrder(T);
	cout << endl << "后序遍历为： " << endl;
	PostOrder(T);
	cout << endl;

	// 叶子结点个数测试
	cout << "叶子结点个数为: " << CountLeaf(T) << endl;

	// 求树深度测试
	cout << "树的深度为：" << Depth(T) << endl;

	// 复制测试
	t = Copy(T);
	cout << "t 的先序遍历为： " << endl;
	PreOrder(t);
	cout << endl;
	


	/*
	// 非递归遍历
	cout << "先序遍历为：" << endl;
	PreOrder_1(T);
	cout << endl;

	cout << "中序遍历为：" << endl;
	InOrder_1(T);
	cout << endl;

	cout << "后序遍历为：" << endl;
	PostOrder_1(T);
	cout << endl;
	*/

	return 0;
}

ab##c##
先序遍历为：
abc
中序遍历为：
bac
后序遍历为：
bca
叶子结点个数为: 2
树的深度为：2
t 的先序遍历为：
abc

---

python代码实现

'''案例ly01.py'''

class Node(object):
	'''节点类'''
	def __init__(self, elem=-1, lchild=None, rchild=None):
		self.elem = elem;
		self.lchild = lchild
		self.rchild = rchild

class Tree(object):
	'''树类'''
	def __init__(self, root=None):
		self.root = root

	def add(self, elem):
		'''为树添加节点'''
		node = Node(elem)
		# 如果树是空的，则对根节点赋值
		if self.root == None:
			self.root = node
		else:
			queue = []
			queue.append(self.root)
			# 对已有的节点进行层次遍历
			while queue:
				# 弹出队列的第一个元素
				cur = queue.pop(0)
				if cur.lchild == None:
					cur.lchild = node
					return
				elif cur.rchild == None:
					cur.rchild = node
					return
				else:
					# 如果左右子树都不为空，加入队列继续判断
					queue.append(cur.lchild)
					queue.append(cur.rchild)


	def preorder(self, root):
		'''递归实现先序遍历'''
		if root == None:
			return
		print(root.elem)
		self.preorder(root.lchild)
		self.preorder(root.rchild)

	def inorder(self, root):
		'''递归实现中序遍历'''
		if root == None:
			return
		self.inorder(root.lchild)
		print(root.elem)
		self.inorder(root.rchild)

	def postorder(self, root):
		'''递归实现后序遍历'''
		if root == None:
			return
		self.postorder(root.lchild)
		self.postorder(root.rchild)
		print(root.elem)

	def breadth_travel(self, root):
		'''利用队列实现树的层次遍历'''
		if root == None:
			return
		queue = []
		queue.append(root)
		while queue:
			node = queue.pop(0)
			print(node.elem)
			if node.lchild != None:
				queue.append(node.lchild)
			if node.rchild != None:
				queue.append(node.rchild)

if __name__ == '__main__':
	t = Tree()

	for i in range(10):
		t.add(i)

	t.preorder(t.root)
	print('*' * 20)
	t.inorder(t.root)
	print('*' * 20)
	t.postorder(t.root)
	print('*' * 20)
	t.breadth_travel(t.root)

0
1
3
7
8
4
9
2
5
6
********************
7
3
8
1
9
4
0
5
2
6
********************
7
8
3
9
4
1
5
6
2
0
********************
0
1
2
3
4
5
6
7
8
9
[Finished in 0.1s]