数据结构笔记总结（树）

数据结构笔记总结（树） 树 定义

树是n个结点的有限集

n=0时称为空树

注：个人感觉这个定义啥也没说，所以要判断一个东西是不是树，应该用下面的特点进行判断

特点

有且仅有一个特定的称为根的结点

当n>1时，其余结点可分为m（m>0）个 互不相交的有限集，其中的每一个集合本身又是一颗树，并且称为根的子树

个人翻译：长得像这样的就是书，记得一定只有一个根结点，如果E和I之间再连一根线，就相交了。也就不是树了

基本术语

结点拥有的子树数称为结点的度

度为0的结点称为叶节点或终端结点

个人翻译：该结点下面没有其他结点了，这个结点就是终端结点

度不为0的结点就是非终端节点或分支节点

除根节点以外的分支结点称为内部结点

树的度就是内部结点中度的最大值

结点之间的关系

结点的子树的根称为该结点的孩子，该节点称为孩子的双亲。

个人翻译：与某个结点相连的结点中，在这个结点上面的就是该结点的双亲，在这个结点下面的就是这个结点的孩子

同一个双亲的孩子互相之间互称兄弟

结点的祖先是从根到该节点所经分支上的所有节点

以某节点为根的子树中的任一结点都称为该节点的子孙

树的层次

有序树

如果将树中的结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树

森林

森林时m颗互不相交的树的集合

二叉树（重点） 定义

二叉树是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成

个人翻译：除了空集这个比较特殊的二叉树，如果看到一颗树它的所有结点的子节点最多只有两个，那这个树就是二叉树

特点

1. 每个结点最多只能有两棵子树
2. 左子树和右子树是有顺序的，次序不能任意颠倒
3. 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

特殊二叉树 满二叉树

定义：只含度为0和2的结点且度为0的结点只出现在最后一层的二叉树称为满二叉树

完全二叉树

定义：对任意一颗满二叉树，从它的最后一层的最右结点起，按从下到上、从右到左的次序去掉若干个结点后所得到的二叉树称为完全二叉树

特性

1.在二叉树的第i层上至多有个结点

2.深度为k的二叉树至多有个结点

3.对任何一颗二叉树T，如果其叶子结点点数为，度（即子结点数)为 2 的结点数为，则

4.具有n个结点的完全二叉树的深度

注：表示不大于x的最大整数

5.如果对一棵树有n个结点的完全二叉树（其深度为)的结点按层次编号，从左到右，对任一结点i有

a.如果i=1，则该结点为根结点，无双亲，若i>1，则其双亲为i/2

b.如果2i>n，则节点i无左孩子（结点i为叶子节点），否则其左孩子为2i

c.如果结点2i+1>n，则节点i无右孩子，否则其右结点为2i+1

二叉树的遍历

二叉树遍历均有两种比较实用的算法：一种为递归算法，一种则是非递归的算法

先序遍历

如果二叉树为空，则进行空 *** 作，否则进行以下 *** 作：

1.访问根节点

2.先序遍历左子树

3.先序遍历右子树

递归算法：

void PreOrderTraversal(BinTree *BT)
{
	if(BT)
	{
		printf("%d",BT->Data);
		PreOrderTraversal(BT->Left);
		PreOrderTraversal(BT->Right);
	}
}

思路：运用递归的思想，如果左子树不为空就一直访问左子树，直到左子树为空，左子树为空则会回到上一次递归，访问右子树，以右子树为根结点继续优先访问左子树，直到左子树为空，又跳出本次递归，然后一层一层的解递归，就能最终将整颗二叉树访问完毕。

非递归算法：

void PreOrderTraversal(BinTree *BT)
{
	if (!BT)
		return;
	BinTree *P = BT;
	stackst;
	while (P != NULL || !st.empty())
	{
		while (P)
		{
			st.push(P);
			cout << P->Value << endl;
			P = P->Left;
		}
		if (!st.empty())
		{
			P = st.top();
			st.pop();
			P = P->Right;
		}

	}
}

思路：非递归算法需要用到之前所学到的线性表的栈，整体思路则是将根结点放入栈中，访问左节点，将左节点放入栈中，只要左节点不为空则一直访问左节点，并将它放入栈中，当左节点为空则访问这个节点的右结点，并将该节点放入栈中，然后继续访问右结点的左节点，然后将右结点放入栈中，直到访问到叶子节点，则取出栈头元素，访问其右结点

中序遍历

1.中序遍历所有左子树

2.访问根节点

3.中序遍历所有右子树

两种算法思路与先序遍历基本一致，此处不再赘述，只提供相应代码

递归算法：

void PreOrderTraversal(BinTree *BT)
{
	if(BT)
	{
		PreOrderTraversal(BT->Left);
		printf("%d",BT->Data);
		PreOrderTraversal(BT->Right);
	}
}

非递归算法：

void PreOrderTraversal(BinTree *BT)
{
	if (!BT)
		return;
	BinTree *P = BT;
	stackst;
	while (P != NULL || !st.empty())
	{
		while (P)//一直向左并将沿途节点压入栈
		{
			st.push(P);
			P = P->Left;
		}
		if (!st.empty())
		{
			P = st.top();
			cout << P->Value << endl; 
			st.pop();
			P = P->Right;//向右访问右子树
		}

	}
}

后序遍历

1.后序遍历左节点

2.后序遍历右结点

3.访问根节点

递归算法：

void PreOrderTraversal(BinTree *BT)
{
	if(BT)
	{
		PreOrderTraversal(BT->Left);
		PreOrderTraversal(BT->Right);
		printf("%d",BT->Data);
	}
}

非递归算法：

void PreOrderTraversal(BinTree *BT)
{
	if (!BT)
		return;
	BinTree *P = BT，*Flag = NULL;
	stackst;
	while (P != NULL || !st.empty())
	{
		if(P)//走到最左边
		{
			st.push(P);
			P = P->Left;
		}
		else
		{
			P = st.top();
			if(P->Right != NULL && P->Right != Flag)//右子树存在，并且未被访问
			{
				P = P->Right;
			}
			else
			{
				st.pop();
				cout << P->value << endl;
				Flag = P;
				P = NULL;
			}
		}

	}
}

层次遍历

二叉树的层次遍历就是按照二叉树的层次，从上到下，从左到右依次遍历，为了实现这种遍历方式则需要用到之前所学到的队列

void travLevel ( BinTreeNode* root ) 
{
   Queue*> Q;
   Q.enqueue ( root ); //根节点入队
   while ( !Q.empty() ) 
   { 
      BinTreeNode* x = Q.dequeue(); cout << x->data; //取出队首节点并访问之
      if ( x->LeftChild ) Q.enqueue ( x->LeftChild ); //左孩子入队
      if ( x->RightChild ) Q.enqueue ( x->RightChild ); //右孩子入队
   }
}

思路：首先将根节点放入队列，然后出队，访问根节点，将根节点的左孩子右孩子依次放入队列中，再依次从队列中取出各个结点，重复刚才的 *** 作，直到队列为空。

线索二叉树

由于二叉树中有些节点或是左节点为空，或是右结点为空，或是都为空，会导致二叉树对内存的浪费，于是提出了线索二叉树的概念。

定义

利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

事实上如果只是为了应付考试，只需要知道线索二叉树怎么画就行了

线索二叉树的画法 重要规则

如果一个结点的左孩子为空，则指向它的前驱结点。

如果一个结点右孩子为空，则指向它的后继。

举个例子

假设要画这个二叉树的中序二叉树

先写出它中序遍历的结果：DFBACE

然后画出每个结点的结构

注：结点名字左右两边的数字作为标志，该节点如果有左孩子，左标志为0，否则为1，右孩子亦然

接下来通过重要规则以及中序遍历结果连线就完事了

树，森林，二叉树转换

我自己是看的这篇文章，写的真不错啊（主要我懒得画图）

https://blog.csdn.net/leolinsheng/article/details/11745559?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164067380916780269818256%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=164067380916780269818256&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allbaidu_landing_v2~default-1-11745559.pc_search_insert_es_download&utm_term=%E6%A0%91+%E6%A3%AE%E6%9E%97+%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1018.2226.3001.4187

哈夫曼树以及哈夫曼编码

这位大佬通过举例子的方式讲的哈夫曼树以及哈夫曼编码，仔细看很容易看懂（懒得画图，开摆了）

https://www.cnblogs.com/kubixuesheng/p/4397798.html