树和二叉树

树的概念

  • 树：一个有限集，可以为空，非空时有且只有一个根结点，其余结点可以分为多个不相交的有限集（子树）
  • 结点的度：结点的子树个数
  • 树的度：树的所有结点中最大的度数
  • 叶子结点：度为0的结点
  • 父结点：有子树的结点是其子树的根节点的父结点
  • 子结点/孩子结点：若A结点是B结点的父结点，则称B结点是A结点的子结点
  • 兄弟结点：具有同一个父结点的各结点彼此是兄弟结点
  • 路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，…，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度
  • 祖先结点：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点
  • 子孙结点：某一结点的子树中的所有结点是这个结点的子孙
  • 结点的层次：规定根结点在1层，其他任一结点的层数是其父结点的层数加1
  • 树的深度：树中所有结点中的最大层次是这棵树的深度

二叉树

二叉树概念

二叉树：一个有穷的结点集合。这个集合可以为空；若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。二叉树的子树有左右顺序之分。

二叉树的五种基本形态：

斜二叉树：只有左子节点或只有右子节点的二叉树，度为1，只有左子节点或右子节点

满二叉树/ 完美二叉树：除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树

完全二叉树：有n个结点的二叉树，对树中结点从上至下、从左到右顺序进行编号，编号为i（1≤i≤n）结点与满二叉树中编号为i结点在二叉树中的位置相同（能和满二叉树完全重叠，编号相同）

按从上至下、从左到右顺序存储n个结点的完全二叉树的结点父子关系：（顺序存储）

  • 根结点的序号为1
  • 非根结点（序号i>1）的父结点的序号是：i / 2
  • 结点（序号为i）的左孩子结点的序号是：2 * i，若2*i > n，则没有左孩子
  • 结点（序号为i）的右孩子结点的序号是：2 * i + 1，若2*i+1 > n，则没有右孩子

普遍规律：

一个二叉树第i层的最大结点数为：2i-1，i≥1

深度为k的二叉树有最大结点总数为：2k-1，k≥1

对任何非空二叉树T，叶结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，则二叉树的总边数：N=2*n2+n1，总结点数：N′=n0+n1+n2，总叶子结点数：n0=n2+1

二叉树的三种遍历：

1

2

3

二叉树操作

创建/初始化

由于树的顺序表结构分配的空间通常只适用于完全二叉树，会造成普通二叉树的空间浪费，所以二叉树一般使用链式结构存储

typedef struct BTnode{
	Elemtype data;				//二叉树的数据域
	struct BTnode *left;		//二叉树的左指针，指向左子树
	struct BTnode *Right;		//二叉树的右指针，指向右子树
}*BTree;

由于二叉树用递归算法较快，涉及到的先序、中序、后序三种输入方式时，只需要调整根节点的输入顺序即可

void  Create(BTree &T)			//传入要操作的结点T
{
    Elemtype a;
    cin>>a;
    if(a=='#')
    {
        T=NULL;					//当输入为“#”时，判断二叉树创建完毕，结束递归
    }					 
    else
    {  
        T=new BTnode;			//创建一个新的二叉树结点
        T->data=a;				//设置数据域为输入值
        Create(T->left);		//递归创建T的左子树
        Create(T->right);  		//递归创建T的右子树
    }  
}

遍历

在创建的时候，相当于也就遍历了一次二叉树，故而除却赋值之外的结构都十分相似,而且由于二叉树已经建立，可以通过二叉树的结点指针是否为空判断遍历是否结束

void Traverse(BTree T)			//传入需要往下位置遍历的根节点
{
	if(T)						//如果T为空，则结束遍历
	{
		Traverse(T->left);		//递归遍历T的左子树
		cout<<T->data;			//输出T结点的数据
		Traverse(T->right);		//递归遍历T的右子树
	}
}

计算深度

二叉树深度为左右子树中深度较大者加1，故而需要递归求取左右子树的深度，再比较后加1

int depth(BTree T)					//传入需要往下求取深度的根节点
{
    int m,n;
    if(T=NULL) return 0;			//当递归到叶子结点时，结束递归
    else
    {
        m=depth(T->left);			//将左子树的深度存入m
        n=depth(T->right);			//将右子树的深度存入n
        if(m>n) return (m+1);		//如果左子树深度大于右子树则返回m+1
        else return (n+1);			//反之，返回n+1
    }    
}

线索二叉树

创建

线索二叉树将二叉树中空置的左右指针域利用起来，存储沿某种顺序遍历二叉树后继结点的地址，比二叉树多设置左右标志，当标志为1（true）时，表示有对应的子节点（左标志为1，左指针域存储左孩子的地址），否则对应指针域则存储某种顺序遍历二叉树时的下一个结点的地址

其中，左指针域为线索时，指向前驱，右指针域为线索时指向后继

typedef struct DBTnode
{
	elemtype data;
    struct DBTnode *left,*right;
    bool ltag,rtag;
}*DBTree;

二叉树中序线索化

DBTnode *p;							//p为全局变量，是指向线索二叉树结点的指针

void Dchild(DBTree T)				//以T为根的子树中序线索化的函数
{
	if(T)							//当T不为空时
	{
		Dchild(T->left);			//将左子树递归线索化
		if(!T->left)				//如果左指针域为空
		{
			T->ltag=false;			//则左标志为false，表示左指针域为线索指针域
			T->left=p;				//左指针域作为线索指针域，指向其前驱p
		}
		else T->ltag=true;			//否则左标志为true，表示左指针域指向左孩子
		if(!p->right)				//如果p的右指针域为空
		{
			p->rtag=false;			//则右标志为false，表示右指针域为线索指针域
			p->right=p1;			//右指针域作为线索指针域，指向其前驱p
		}
		else p->rtag=true;			//否则右标志为true，表示右指针域指向右孩子
		p=T;						//p指向子树的根节点处
		Dchild(p->right);			//将右子树递归线索化
	}
}

void DOchild(DBTree &T,DBTree D)	//带头结点的二叉树中序线索化的函数
{
	T=new DBTnode;					//创建头结点
    T->Ltag=true;					//若树非空，则头结点的左孩子为树根，左标志为true
    T->rtag=false;					//头结点没有右孩子，右标志为false
    T->right=T;						//初始化时，头结点的右指针域指向自己
    if(!T) T->left=T;				//若树空，则头结点的左指针也指向自己
    else 							
    {
    	T->left=D;					//否则，头结点的左指针域指向原二叉树的根节点D
        p=T;						//p指向原二叉树根节点D的前驱
        Dchild(D);					//递归线索化二叉树D
        p->right=T;					//递归线索化后，p指向中序遍历的最后一个结点，右指针域指向头结点
        p->rtag=false;				//p指向结点的右标志为false，表示没有右孩子
        T->right=p;					//将头结点的右指针域指向p
    }
}

遍历中序线索二叉树(非递归)

void OTraverse(DBTree T)
{
	p=T->left;						//p指向头结点的左孩子，即二叉树的根节点
    while(p!=T)						//当树空或遍历结束时，将有p==T，结束循环
    {
        while(p->ltag==true) 		//当左标志为false时，即直到没有左孩子时结束循环
            p=p->left;				//p沿左子树向下遍历
        cout<<p->data;				//输出左子树为空的结点的值
        while(p->rtag==false&&p->right!=T)		//当右标志为true，即有右孩子且p的后继不是头结点
        {
            p=p->right;				//p沿右子树向下遍历
            cout<<p->data;			//沿右子树访问后继结点
        }
        p=p->right;					//转向p的右子树
    }
}