二叉树的建立

  二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆

1.二叉树的性质

(1) 在非空二叉树中，第i层的结点总数不超过 2^i-1 , i>=1；
(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N₀，而度数为2的结点总数为N₂，则N₀=N₂+1；
(4) 具有n个结点的完全二叉树的深度为[log2ⁿ+1]（注：[ ]表示向下取整）
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果i>1，则其父结点的编号为i/2；
如果2i<=N，则其左孩子（即左子树的根结点）的编号为2i；若2i>N，则无左孩子；
如果2i+1<=N，则其右孩子的结点编号为2i+1；若2I+1>N，则无右孩子。
(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i [2]

1.二叉树的建立

1.1 二叉树的数据结构（二叉链表）表示

#define END  '#' 
typedef char  ElemType;
typedef struct BtNode
{
	BtNode *leftchild;       //左孩子
	BtNode *rightchild;      //右孩子
	ElemType data;           //数据域
}BtNode,*BinaryTree;
1
2
3
4
5
6
7
8

1.2二叉树的建立
1.2.1特殊字符串
  以字符串“ABC##DE##F##G#H##”为例，采用中序遍历的方式建立一颗二树，具体图示如下：

//以中序遍历的方式建立一颗二叉树
BtNode * CreateTree(ElemType *&str)   //str是一个指针类型的引用，
//相当于给指针起了一个别名
{
	BtNode *s = NULL;
	if(NULL != str && *str != END)
	{
		s = Buynode();
		s->data = *str;
		s->leftchild = CreateTree(++str);
		s->rightchild = CreateTree(++str);
	}
	return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

  函数 CreateTree(ElemType *&str) 的参数为啥是那个样子，可以参考博客
  https://mp.csdn.net/mdeditor/96904688#
1.2.2数组
  以数组ar[]={31,23,12,66,-1,5,17,70,62,-1,-1,-1,88,-1,55}为例，利用性质5建立二叉树，具体图示如下：

 #define END -1
    BtNode * CreateAr(ElemType *ar,int i,int n)
    {
    	BtNode *s = NULL;
    	if(i < n && ar[i] != END)
    	{
    		s = Buynode();
    		s->data = ar[i];
    		s->leftchild = CreateAr(ar,i*2+1,n);
    		s->rightchild = CreateAr(ar,i*2+2,n);
    	}
    	return s;
    }
    
    BtNode * CreateTreeAr(ElemType *ar,int n)
    {
    	if(NULL == ar || n < 1)
    		return NULL;
    	else
    		return CreateAr(ar,0,n);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.2.3二叉树还原成数组
  以1.2.2中的数组ar为例，在创建好二叉树的基础上，再将其转换为数组br,具体代码和运行结果如下所示：

void LinkMakeAr(BtNode *ptr,ElemType *buff,int i)
{
	if(ptr != NULL)
	{
		buff[i] = ptr->data;
		LinkMakeAr(ptr->leftchild,buff,i*2+1);
		LinkMakeAr(ptr->rightchild,buff,i*2+2);
	}
}

void LinkCreateAr(BtNode *root,ElemType *buff,int n)
{
	if(root == NULL || buff == NULL)
		return;
	for(int i = 0;i<n;++i)    //初始化数组
	{
		buff[i] = END;
	}
	LinkMakeAr(root,buff,0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.2.4二叉排序树
  以数组ar[]={12,23,34,45,56,67,78,89,95,100,110}为例，建立二叉排序树，利用二叉排序树中序遍历有序的特性，将其进行打印，结果如下：

BtNode * CreateBin(ElemType *ar,int left,int right)
{
	BtNode *s = NULL;
	if(left <= right)
	{
		int mid = (right - left + 1)/2 + left;
		s = Buynode();
		s->data = ar[mid];
		s->leftchild = CreateBin(ar,left,mid-1);
		s->rightchild = CreateBin(ar,mid+1,right);
	}
	return s;
}

//二叉排序树
BtNode * CreateBinary(ElemType *ar,int n)
{
	if(NULL == ar || n < 1)
		return NULL;
	else
		return CreateBin(ar,0,n-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22