二叉树的操作

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

二叉树的操作

一、二叉树的存储结构
- 1.顺序存储结构
- 2.二叉树的链式存储
二、二叉树的操作
- 二叉树的遍历
- - 二叉树的非递归遍历
  - 遍历二叉树的应用

一、二叉树的存储结构 1.顺序存储结构

完全二叉树最适合这种存储结构
n个结点的完全二叉树的结点父子关系，简单地由序列号决定：

非根结点（序号 i>1）的父结点的序号是i / 2;
结点（序号为 i）的左孩子结点的序号是2i；（若2i > n，则没有左孩子）
结点（序号为 i）的右孩子系欸但的序号为2i+1；（若2i+1 > n，则没有右孩子）
一般二叉树采取这种结构会造成空间浪费！！

2.二叉树的链式存储

结构：

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
}

二、二叉树的操作

二叉树的ADT

类型名称：BinTree
数据对象集：一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根结点和其左、右二叉子树组成。
操作集：对于所有 BT, BT1, BT2 ∈ BinTree, Item ∈ ElementType，重要的操作有：
1、Boolean IsEmpty( BinTree BT )：若BT为空返回TRUE; 否则返回FALSE；
2、void Traversal( BinTree BT )：二叉树的遍历，即按某一顺序访问二叉树中的每个结点仅一次；
3、BinTree CreatBinTree( )：创建一个二叉树。

二叉树的遍历

常见的遍历方式有：
1、void InOrderTraversal( BinTree BT )：根结点的访问次序在左、右子树之间；
2、void PreOrderTraversal( BinTree BT )：根结点的访问次序在左、右子树之前；
3、void PostOrderTraversal( BinTree BT )：根结点的访问次序在左、右子树之后。
4、void LevelOrderTraversal( BinTree BT )：按层从小到大、从左到右的次序遍历

void InorderTraversal( BinTree BT )
{
    if( BT ) {
        InorderTraversal( BT->Left );
        
        printf("%d ", BT->Data); 
        InorderTraversal( BT->Right );
    }
}

void PreorderTraversal( BinTree BT )
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}

void PostorderTraversal( BinTree BT )
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}

void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;

    if ( !BT ) return; 
    
    Q = CreatQueue(); 
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); 
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}

二叉树的非递归遍历

中序遍历的非递归算法：
遇到一个结点，就把它压栈，并去访问它的左子树；
当左子树遍历结束后，从栈顶弹出这个结点并访问它；
然后按其右指针再去中序遍历该结点的右子树。
先序遍历的非递归遍历算法：
遇到一个结点，就把它压栈并访问它，然后去遍历它的左子树；
当左子树遍历结束后，从栈顶弹出这个结点；
然后按其右指针再去中序遍历该结点的右子树。
后序遍历非递归遍历算法：
遇到一个结点，就把它（附带标志0以后）压栈，并去遍历它的左子树；
当左子树遍历结束后，检查栈顶元素的附带标志是否为0；
若标志为0，则把标志改成1，并按其右指针再去遍历该结点的右子树；
若标志为1，则从栈顶弹出这个结点并访问它。

void InOrderTravelsal(BinTree BT){
	BinTree T;
	Stack S = CreatStack(MaxSize);
	while(T||!IsEmpty(S)){
		while(T){
			Push(S,T);
			T = T->Left;
		}
		if(!IsEmpty(S)){
			T = Pop(S);
			printf("%5d",T->Data);
			T = T->Right;
		}
	}
}

遍历二叉树的应用

输出二叉树中的叶子结点

void PreOrderPrintLeaves(BinTree BT){
	if(BT){
		if(!BT->Left&&!BT->Right)
			printf("%d",BT->Data);
		PreOrderPrintLeaves(BT->Left);
		PreOrderPrintLeaves(BT->Right);
	}
}

求二叉树的深度

void PostOrderGetHeight(BinTree BT){
	int HL,HR,MaxH;
	if(BT){
		HL = PostOrderGetHeight(BT->Left);
		HR = PostOrderGetHeight(BT->Right);
		MaxH = HL > HR? HL : HR;//取较大的深度
		return (MaxH + 1);
	}
	else return 0;
}

由两种遍历序列确定二叉树（必须要有中序）
先序和中序：
先序遍历序列的第一个结点就是根结点；这个根结点能够在中序遍历序列中将其余结点分割成两个子序列，根结点前面部分是左子树上的结点，而根结点后面的部分是右子树上的结点。
根据这两个子序列，在先序序列中找到对应的左子序列和右子序列，它们分别对应左子树和右子树。然后对左子树和右子树分别递归使用相同的方法继续分解。

二叉树的操作

C/C++/C#相关栏目本月热门文章