二叉树的实际应用

操作系统的文件系统，在操作系统源程序中，树和森林被用来构造文件系统，比如tree指令，可以以树型结构展示出文件结构，比如C编译器源代码中，二叉树以中序遍历形式存放C语言表达式，比如C语言运算符的优先级问题等，又比如哈夫曼二叉树用于JPEG编解码系统（压缩与解锁过程）等等。

二叉树的定义

二叉树是结点的有限集合，这个集合或为空集，或者由一个称为根的结点和两颗不相交的分别叫做这个根的分别叫做这个根的左子树和右子树组成。

二叉树的形态有：

空二叉树
只有一个结点的二叉树
有根结点和非空左子树的二叉树
有根结点和非空右子树的二叉树
左右非空的有根结点的二叉树

二叉树的特性：

二叉树的根节点没有前去结点，除根节点外都已且只有一个前驱结点
每个结点可以有零到两个后继结点

其他定义：

父节点：结点的前驱
子节点：结点的后继
兄弟：具有同一父节点（前驱）的结点
祖先、子孙：简单的说父结点的父结点就是祖先，子孙同理
路径：从一个结点到另一个结点的就叫做路径
层数：根结点的层数为0，其余结点的层数等于父节点的层数加1
结点的度数：结点的后缀个数，每个结点度数最大为2
高度：结点的最大层数称为二叉树的高度
树叶：左右子树均为空的结点称作树叶
满二叉树：二叉树的任意结点或树叶，或有两颗非空的子树，称为满二叉树
完全二叉树：只有最下面的两层结点读书都小于2，其余各层结点读书都等于2，并且最下面一层的结点都集中再该层最左边的若干位置上。
扩充二叉树：对二叉树进行扩充，扩充为结点都为度数为2的分支结点，其中，新增加的结点称为外部结点，原有的结点称为内部结点。外部路径长度就为根到每个外部结点的路径长度之和。

二叉树的性质

一般二叉树：

在非空二叉树的第i层上，至多有2^i 个结点（i≥0）

第一层2^0 ,第二层2^1,以此类推

高度为k的二叉树中最多有2^(k+1)-1个结点

高度为0，结点1个，高度为1，结点2^{(1+1)-1=3个结点，高度为2，系欸但2}(2+1)-1=7个结点，这就是一个等差数列求和。

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

完全二叉树

具有n个结点的完全二叉树的高度k为[log2n]

......

二叉树的周游

二叉树的周游是一种按照某种方式系统的访问二叉树中所有结点的过程，使每个结点都被访问一次且只被访问一次。

深度优先周游

以符号D、L、R分别表示根节点、左子树、右子树

二叉树的周游有：DLR(先根次序/先序/前序) LDR（后根次序/后续） LRD（中根次序/中序/对称次序） DRL RDL RLD

![image.png](二叉树（c++）+9805844c-ad2d-4e69-a268-0a78a5901286/image 1.png)

先根次序

若二叉树不为空，先访问根，然后按先根次序周游左子树，最后周游右子树。

A,B,D,C,E,G,F,H,I

后根次序

若二叉树不为空，则先按后跟次序周游左子树，然后按后根次序周游右子树，最后访问根

D,B,G,E,H,I,F,C,A

中根次序

若二叉树不为空，则先按对称序周游左子树，然后访问根，在按对称序周游右子树

D,B,A,E,G,C,H,F,I

不同的周游方式，前驱后继不同

广度优先周游

若二叉树的高度为h，则从0到h逐层：从左到右逐个访问存在的结点

A,B,C,D,E,F,G,H,I

代码实现

![image.png](二叉树（c++）+9805844c-ad2d-4e69-a268-0a78a5901286/image 2.png)

![image.png](二叉树（c++）+9805844c-ad2d-4e69-a268-0a78a5901286/image 3.png)

#include<iostream>

using namespace std;

typedef char DataType;

struct node
{
  DataType info ; 
  struct node *lchild , *rchild ; 
};

typedef struct node *BiTree ;
BiTree createBiTree(void)
{
  char ch ;
  BiTree  root ;
  cin>>ch ;
  if(ch == '#') root = NULL;
  else{
        root = new struct node ;
        root->info = ch ;
        root->lchild = createBiTree() ;
        root->rchild = createBiTree();
  }
  return root ;
}

void visit(BiTree T)
{
  cout<<T->info ;
}


// 先根序遍历
void preOrder(BiTree T) {
	if(T != NULL) {
		cout << T->info << " ";
		preOrder(T->lchild);
  		preOrder(T->rchild);
	}
  	
}

// 中根序遍历
void inOrder(BiTree T) {
	if(T != NULL) {
		inOrder(T->lchild);
		cout << T->info << " ";
		inOrder(T->rchild);
	}
}

// 后根序遍历
void postOrder(BiTree T) {
  if(T != NULL) {
  	postOrder(T->lchild);
  	postOrder(T->rchild);
  	cout << T->info << " ";
  }
}


int countFullNode(BiTree T)
{
    int cnt = 0;
    if(!T) return 0;
    else if (T->lchild != NULL && T->rchild != NULL) cnt++;
    return cnt + countFullNode(T->lchild) +countFullNode(T->rchild); 
}

// 树叶结点计数
int coutLeafNode(BiTree T) {
  int cnt = 0;
  if(!T) return 0;
  else if (T->lchild == NULL && T->rchild == NULL) cnt++;
  return cnt + coutLeafNode(T->lchild) + coutLeafNode(T->rchild);
}


int main(void)
{
  BiTree root = createBiTree();
  visit(root);
  cout<<endl;
  cout<<countFullNode(root);
  printf("\n叶结点的个数为：%d",coutLeafNode(root));
  printf("\n先根序遍历为：");
  preOrder(root);
  printf("\n中序遍历为：");
  inOrder(root);
  printf("\n后根序遍历为：");
  postOrder(root);
  printf("\n层次遍历为：");
  levalOrder(root);
}

JZTXT

二叉树（c++）