二叉树（C语言版）_二叉树c语言

1. 树概念及结构

1.1树概念

树是由 n(n>= 0)个结点组成的有限集合。如果 n = 0，称为空树; 如果 n >0，则

1）有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱;
2）除根以外的其它结点划分为 m(m = 0)个互不相交的有限集合 T,T1,.., Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。

 以下内容引用自 (数据结构)

1.节点的度:一个节点含有的子树的个数称为该节点的康
2.树的度:一棵树中，最大的节点的度称为树的度;
3.叶节点或终端节点:度为零的节点;
4.非终端节点或分支节点: 度不为零的节点;4
5.父亲节点或父节点:若一个节点含有子节点，则这个节点称为其子节点的父节点:

6孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
7.兄弟节点: 具有相同父节点的节点互称为兄弟节点;
8节点的层次: 从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推

9.深度: 对于任意节点 n,n 的深度为从根到 n 的唯一路径长，根的深度为 0:
10.高度: 对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0:

11.堂兄弟节点:父节点在同一层的节点互为堂兄弟;
12.节点的祖先: 从根到该节点所经分支上的所有节点;
13.子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。
14.森林: 由 m (m>=0) 棵互不相交的树的集合称为森林;

2. 二叉树概念及结构

2.1概念

        一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
二叉树的特点：

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

 2.2二叉树的性质

       1）若二叉树的层次从 0 开始，则在二叉树的第 i 层最多有 2 个结点。(i>= 0) [证明用数学归纳法

       2）高度为 k 的二又树最多有2k+1-1个结点。(k >= -1) [证明用求等比级数前 k 项和的公式]

       3）对任何一棵二叉树，如果其叶结点个数为 n0，度为2的非叶结点个数为 n2,则有 n0=n2+1

2.3特殊的二叉树

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

2）完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

 

 

2.4二叉树的存储结构

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

2.4.1顺序存储

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

 2.4.2链式存储

       二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

 

 

 

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

4.1二叉树链式结构的遍历

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

示例一：

如上图所示：

前序遍历：A B C D E

中序遍历：C B D A E

后序遍历：C D B E A

示例二

 

 实现代码：

// 二叉树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
 
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
 
typedef struct BTNode //BinaryTreeNode
{
	struct BTNode* leftchild;
	struct BTNode* rightchild;
	ElemType data;
}BTNode, * BinaryTree;
 
BTNode* Buynode(ElemType val, BTNode* Larg = nullptr, BTNode* Rarg = nullptr)
{
	BTNode* s = (BTNode*)malloc(sizeof(BTNode));
	if (nullptr == s) exit(EXIT_FAILURE);
	s->data = val;
	s->leftchild = Larg;
	s->rightchild = Rarg;
	return s;
}
void Freenode(BTNode* p)
{
	free(p);
}
void PreOrder(BTNode* ptr)
{
	if (ptr != nullptr)
	{
		printf("%c ", ptr->data);
		PreOrder(ptr->leftchild);
		PreOrder(ptr->rightchild);
	}
}
void InOrder(BTNode* ptr)
{
	if (ptr != nullptr)
	{
		InOrder(ptr->leftchild);
		printf("%c ", ptr->data);
		InOrder(ptr->rightchild);
	}
}
 
void PastOrder(BTNode* ptr)
{
	if (ptr != nullptr)
	{
		PastOrder(ptr->leftchild);
		PastOrder(ptr->rightchild);
		printf("%c ", ptr->data);
	}
}
BTNode* CreateBinaryTree()
{
	ElemType ch;
	BTNode* s = nullptr;
	scanf_s("%c", &ch);
	if (ch != '#')
	{
		s = Buynode(ch);
		s->leftchild = CreateBinaryTree();
		s->rightchild = CreateBinaryTree();
	}
	return s;
}
 
BTNode* CreateBTree(const char* cp)
{
	BTNode* s = nullptr;
	if (nullptr != cp && *cp != '#')
	{
		s = Buynode(*cp);
		s->leftchild = CreateBTree(++cp);
		s->rightchild = CreateBTree(++cp);
 
	}
	return s;
}
 
int main()
{
	const char* cp = "ABC##CE##F##G#H##";
	BinaryTree root = nullptr;
 
	//root = CreateBinaryTree();
	root = CreateBTree(cp);
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PastOrder(root);
	printf("\n");
	return 0;
}