数据结构二叉树笔记（1）

二叉树定义二叉树，有序树，无序树的区别一个三结点的有序树，无序数，二叉树的排列1.无序树2.有序树3.二叉树二叉树的路径和路径长度二叉树的性质树的存储结构1.顺序存储结构2.链式存储结构（1）双亲-孩子表示法（2）孩子-兄弟表示法（3）三叉链表表示法树，森林，二叉树的转换

在学习树这种非线性数据结构的时候，二叉树都是第一个要了解的概念。

二叉树英文名Binary Tree，简称BT。

二叉树定义

二叉树BT是有限个结点的集合。其特点是当集合非空时，其中一个结点拿来当根节点，其他结点最多只能被分成两个互不相交的子树。

子树有左右顺序之分，即当一个结点只有一个子树的时候，二叉树也要规定是左子树还是右子树。当有两个子树的时候，那就自然要分是左还是右。

上面的定义简单来说，就是一个双亲最多只能有两个孩子，并且孩子一定分左右，不管是独生子女还是二胎。（一般是先生成的是左，后生成的是右。）

二叉树的基本概念和满二叉，完全二叉这里不再赘述。

二叉树，有序树，无序树的区别

无序树

顾名思义，就是孩子不分顺序。树中任何一个结点（除叶子结点leaf）的孩子结点不分高低，人人平等。

有序树

同样顾名思义，就是孩子分顺序。树中任何一个结点（除叶子结点leaf）的孩子结点存在顺序关系。这里的顺序关系比较笼统，一般默认的就是先后顺序。比如最先生成的结点地位最大或者最小，孩子结点之间的顺序代表着他们之间的关系，也代表着他们以后要进行的增删改查的先后顺序。

二叉树

比较奇葩。首先二叉树肯定是有序树，因为二叉树的结点子树是分顺序的。但是二叉树跟有序树也有区别，区别就在当只有一颗子树的时候，有序树不分这个子树的顺序，但是二叉树仍要分它是左子树还是右子树。所以一个拥有3个结点的二叉树，会拥有五种状态：

空树只有一个根结点一个根节点+左子树一个根节点+右子树一个根节点+左子树+右子树（当然如果左右子树的值互换这又是不一样的二叉树，因为二叉树是有序的。）

一个三结点的有序树，无序数，二叉树的排列

1.无序树

无序树比较简单，因为子树不分顺序，那么就分两种情况：

一个双亲，两个孩子。

因为孩子无序，但双亲要轮流当，所以3种。

直链式结构，一个爷爷，一个爸爸，一个孩子。

这就是(3A2)=6种情况

所以一共9种。

2.有序树

有序树因为因为孩子结点分顺序，交换一下位置就是两种不同的情况。同样两种情况：

一个双亲，两个孩子。

双亲轮流当，每个双亲下面孩子分两种，一共6种。

直链式结构，一个爷爷，一个爸爸，一个孩子。

同上情况，6种。

所以一共是12种。

3.二叉树

二叉树情况更复杂，因为就连单个孩子结点的时候也要分左右两种情况。同样两种情况：

一个双亲，两个孩子。

同上有序树，一共6种。

直链式结构，一个爷爷，一个爸爸，一个孩子。

这里比较麻烦，首先固定谁当爷爷，谁当爸爸，谁当孩子。在这种情况下，根节点不动，下面两个孩子结点一共是2*2=4种情况。

上述情况4种，一共有6种爷爷爸爸孩子的情况（3A2=6）,那么一共就是4*6=24种。

所以一共是30种。

拓展：当有n个结点的时候，二叉树有多少种基本形态？

答案:

这里主要采用了递归的思想，先固定根节点，然后根据左右子树的不同情况就可以把f(n)降为f(n-1),f(n-2),f(n-3),…,f(0)的组合。以下是简短举例：

f(0)=1，f(1)=1

f(2)=f(1)f(0)+f(0)f(1)

f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)

.

.

f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)

二叉树的路径和路径长度

对于任意两个结点Ki和Kj,若树中存在一个节点序列Ki,Ki1,Ki2,…,Kin,Kj,使得序列中除ki外的任意一个节点都是其在序列中的前一个节点的后继，则称该节点序列为由Ki到Kj的一条路径，用路径所通过的节点序列（Ki,Ki1,Ki2,…,Kin,Kj）表示这条路径。

路径的长度等于路径所通过的边的数目。

二叉树的性质

二叉树结点数等于二叉树的总度数加1。

非空二叉树上叶子结点数等于双分支结点数加1。

证明：设二叉树度为0的结点数为 a0，度为1的结点数为 a1,度为2的结点数为 a2

所以树的总度数 a = a0 x 0 + a1 x 1 + a2 x 2 = a1 + 2a2；

又因为树的总结点数为 a0 + a1 + a2;根据性质1

a1 + 2a2 = a0 + a1 + a2

得 a0 = a2 + 1.

非空二叉树上第 i 层上至多有2i-1个结点（i ⩾\geqslant⩾ 1）高度为h的二叉树至多有 2h-1个结点（i ⩾\geqslant⩾ 1）任何完全二叉树中度为 1 的结点只有 0 个或者 1 个。具有 n 个结点的完全二叉树的高度为 ⌈\lceil⌈log2(n+1)⌉\rceil⌉

证明：设完全二叉树的高度为 h ，由性质4得

2h-1-1 < n ⩽\leqslant⩽ 2h - 1 解得

h - 1 < log2(n + 1) ⩽\leqslant⩽ h 因为h是整数 即

h = ⌈\lceil⌈log2(n+1)⌉\rceil⌉

对二叉树进行层次遍历编号，可以找到二叉树双亲和孩子之间的坐标关系。由于起始值可以为 0 可以为 1，所以坐标关系也分为两种，这里不再赘述。

树的存储结构

1.顺序存储结构

下标代表编号，数组元素代表结点值。

一般用于完全二叉树以免空间浪费。

下面是核心代码实现：

void BTree(BT tree , int i){char ch;ch = getchar();fflush(stdin); //清空键盘缓存区if(ch == ' '){//当输入空格时结束节点输入tree[i] = '\0';return;}tree[i] = ch;//建立完节点提示输入左子树和右子树printf("请输入左子树：\n");CreatSeqTree(tree , 2 * i + 1);printf("请输入右子树：\n");CreatSeqTree(tree , 2 * (i + 1));}

2.链式存储结构

（1）双亲-孩子表示法

利于查找孩子，不利于查找双亲。

具体结构实现：

typedef struct CTNode{int data;struct CTNode * next;}*ChildPtr;typedef struct {T data;//结点的数据类型ChildPtr first;//孩子链表的头指针}CTBox;typedef struct{CTBox nodes[Tree_Size];//存储结点的数组int n,r;//结点数量和树根的位置}CTree;

利于查找双亲，不利于查找孩子。

具体结构实现：

typedef struct PTNode{T data;//树中结点的数据类型int parent;//结点的父结点在数组中的位置下标}PTNode;typedef struct {PTNode nodes[tree_size];//存放树中所有结点int r,n;//根的位置下标和结点数}PTree;

可以实现两者的结合：

（2）孩子-兄弟表示法

左指针指向自己的第一个孩子，右指针指向自己的下一个兄弟。

利用这种结构可以实现把 n 叉树转化为二叉树。

具体结构实现：

typedef struct CSNode{T data;struct CSNode * firstchild,*nextsibling;}CSNode,*CSTree; //这里采用了头指针的操作，也可以采用头结点的操作。

（3）三叉链表表示法

结点结构为：

template<class T>struct Node{T data; //数据域，存放该结点的信息Node<T> *lchild; //左指针域，存放指向左孩子的指针，当左孩子不存在时为空Node<T> *rchild; //右指针域，存放指向右孩子的指针，当右孩子不存在时为空Node<T> *parent; //父指针域，存放指向父节点的指针，当父节点不存在时为空};

先序递归构造三叉链表二叉树：

(中序递归和后序递归直接把递归函数之间的执行顺序调换即可)

void CreateBTree(BT *t){/*按先序次序输入二叉树中结点的值*//* 构造三叉链表表示的二叉树T */char ch;cin>>ch;if(ch==NULL) /* 空 */*t=NULL;else{t=new Node(ch); /* 动态生成根结点*/CreateBiTree(&(t->lchild)); /* 构造左子树 */if(t->lchild) /* 有左孩子 */t->lchild->parent=t; /* 给左孩子的双亲域赋值 */CreateBiTree(&(t->rchild)); /* 构造右子树 */if(t->rchild) /* 有右孩子 */t->rchild->parent=t; /* 给右孩子的双亲域赋值 */}}

先序非递归构造三叉链表二叉树（利用栈）：

#include <iostream>#include <string.h>#include "LinkStack.h"using namespace std;/* .....中间函数省略.....*/ThreeBTree* CreatBTree(BT *t,ThreeBTree *root){if(t==NULL) return NULL;Node *St[MaxSize] ,*p, *q;root = new Node(t.data);St.push(root); //压栈while(!St.IsEmpty()) //栈不为空{p = St.pop(); //将栈顶元素弹出，用p存储if(!(t.rightChild)){q = new Node(t.rightChild.data); //构造结点St.push(q); //新结点进栈p.rightChild = q; //p 的右孩子指向 qq.parent = p;//q 的双亲指向 p}if(!(t.leftChild)){q = new Node(t.leftChild.data); //同上St.push(q);p.leftChild = q;q.parent = p;}cout<<endl;}}

树，森林，二叉树的转换

1.思路

就是对于任一个节点：

左指针指向它的第一个孩子右指针指向它的兄弟/旁边的树

树转化成二叉树：

因为森林每颗树的根节点一定没有右孩子，所以可以把不同树的根节点当成兄弟处理。

森林转化成二叉树：

二叉树转树和森林就是上面过程的逆过程。

即对于任意一个节点:

左子树转换为它的子树如果是根节点,右子树转换为另一颗树,如果不是，右子树转换为该节点的兄弟树转化成的二叉树没有右子树，森林转化成的二叉树有右子树。