数据结构入门——06树

1.树

树（Tree）非线性数据结构，它是n（n≥0）个节点的有限集合，它满足两个条件 ：

有且仅有一个特定的称为根（Root）的节点；

其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
因此，树是递归定义的。

树的表示方法 ：树形表示法、目录表示法。

• 一个节点的子树的个数称为该节点的度数。
• 一棵树的度数是指该树中节点的最大度数。
• 度数为零的节点称为树叶或终端节点。
• 度数不为零的节点称为分支节点。
• 除根节点外的分支节点称为内部节点。

森林

• 若树中每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的，则该树称为有序树。
• m（m≥0）棵互不相交的树的集合称为森林。
• 树去掉根节点就成为森林，森林加上一个新的根节点就成为树。

 2.树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，
如：双亲表示法，孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子
兄弟表示法。

2.1兄弟表示法

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};

2.2双亲表示法

3.二叉树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子
树和右子树的二叉树组成。

二叉树特点

1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

3.1特殊的二叉树

3.1.1满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

3.1.2完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。最后一层是连续的，前面的k-1层为满的。 满二叉树是一种特殊的完全二叉树。完全二叉树度为1 的，最多有一个。

3.2二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.(等比数列求和1+2+2^2+...+2^h)
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1.
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=LogN.

3.3二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

3.3.1顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树
会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

 在数组中:   父亲下标为i,左孩子下标为2*i+1,右孩子下标为2*i+2.

                    孩子下标为i,父亲下标为(i-1)/2.(不论是左还是右，下标都为整数)

3.3.2链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的
方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩
子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。

// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* pLeft; // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode比特就业课
{struct BinTreeNode* pParent; // 指向当前节点的双亲struct BinTreeNode* pLeft; // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}；

4.二叉树链式结构的实现

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访
问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行
其它运算之基础。

4.1二叉树链式结构的遍历

• 前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名，为深度优先。

1.  NLR：前序遍历(Preorder Traversal 亦称先序遍历)——根->左子树->右子树。
2.  LNR：中序遍历(Inorder Traversal)——左子树->根->右子树。
3. LRN：后序遍历(Postorder Traversal)——左子树->右子树->根。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

• 层序遍历：设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。为广度优先。

typedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;BTNode* BuyBTNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){printf("malloc fail\n");exit(-1);}node->data = x;node->left = node->right = NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyBTNode(1);BTNode* node2 = BuyBTNode(2);BTNode* node3 = BuyBTNode(3);BTNode* node4 = BuyBTNode(4);BTNode* node5 = BuyBTNode(5);BTNode* node6 = BuyBTNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

上述代码创建一个二叉树，如下图所示

4.1.1前序遍历(A->B->D->NULL->C->F->G)

void PrevOrder(BTNode* root) {if (root == NULL) {printf("NULL ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

4.1.2中序遍历（D->B->NULL->A->F->C->G） 

void InOrder(BTNode* root) {if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

4.1.3后序遍历 (D->NULL->B->F->G->C->A)

void PosOrder(BTNode* root) {if (root == NULL){printf("NULL ");return;}PosOrder(root->left);PosOrder(root->right);printf("%d ", root->data);
}

4.1.4二叉树的结点个数

int BTreeSize(BTNode* root) {return root == NULL ? 0 :BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

4.1.5第k层的节点的个数，k >= 1

int BTreeKLevelSize(BTNode* root, int k)
{assert(k >= 1);if (root == NULL)return 0;if (k == 1)return 1;return BTreeKLevelSize(root->left, k - 1)+ BTreeKLevelSize(root->right, k - 1);
}

4.1.6求二叉树的深度

int BTreeDepth(BTNode* root)
{if (root == NULL)return 0;int leftDepth = BTreeDepth(root->left);int rightDepth = BTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

4.1.7二叉树查找值为x的结点

BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret1 = BTreeFind(root->left, x);if (ret1)return ret1;//return BTreeFind(root->right, x);BTNode* ret2 = BTreeFind(root->right, x);if (ret2)return ret2;return NULL;
}

4.1.8二叉树销毁

void BTreeDestory(BTNode* root)
{if (root == NULL){return;}BTreeDestory(root->left);BTreeDestory(root->right);free(root);
}

4.1.9层序遍历(需要队列进行入队和出队)

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestory(&q);
}

4.1.10判断二叉树是否是完全二叉树

// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 空后面出到非空，那么说明不是完全二叉树if (front){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}