数据结构-二叉树遍历总结

忘是亡心i 2022-06-10 04:52 126阅读 0赞

## 二叉树结构 ##

二叉树是一种特殊的树，每个父结点**最多**只能有两个子结点。  
![这里写图片描述][format_png]  
在树中，按照结点的“继承”关系可以分为父结点和子结点；  
按照结点的位置关系可以分为根结点，中间结点和叶结点。  
其中叶结点没有子结点。  
我们用结点中的数字代表结点，那么在上图中：10为根结点；6、14为中间结点；4、8、12、16为叶节点。

## 二叉树存储结构 ##

二叉树结构可以使用链式和顺序两种方式实现，其中比较常用的链式存储结构：

**链式结构**

typedef char TElemType; 
    typedef struct BiTNode  /* 结点结构 */
    {
       TElemType data;		/* 结点数据 */
       struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
    }BiTNode,*BiTree;

也可以写成这样，更清晰一些：

typedef char TElemType;   
    typedef struct BiTNode{  
        TElemType data;  
        struct BiTNode* lchild;  
        struct BiTNode* rchild;  
    }BiTNode;    
    typedef BiTNode* BiTree;

**顺序结构**

#define LENGTH 100  
    typedef char datatype;  
    typedef struct node{  
        datatype data;  
        int lchild,rchild;  
        int parent;  
    }Node;  
      
    Node tree[LENGTH];  
    int length;  
    int root;

本质上是一个结构体数组。

## 二叉树遍历 ##

在二叉树中最重要的操作大概就是遍历，如链表这样的数据结构，遍历的方式是唯一的，因为我们只知道链表的头结点，遍历到一个结点时也只知道下一个结点（**单链表**），但是在树中却有多种遍历方式，通常有：

*  前序遍历：根结点—>左子结点—>右子结点，10、6、4、8、14、12、16；
 *  中序遍历：左子结点—>根结点—>右子结点，4、6、8、10、12、14、16；
 *  后序遍历：左子结点—>右子结点—>根结点，4、8、6、12、16、14、10；
 *  层序遍历：第一层—>第二层—>第n层，10、6、14、4、8、12、16；

## 代码实现 ##

遍历操作可以使用循环和递归的方式实现，其中递归可以使代码变的很简洁易懂，同样树的结构越复杂，递归的层数就会越深，但是总体上递归的方法更常用。

**前序遍历：**

void PreOrderTraverse(BiTree T)
    { 
    	if(T==NULL)
    		return;
    	printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    	PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
    	PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
    }

**中序遍历：**

void InOrderTraverse(BiTree T)
    { 
    	if(T==NULL)
    		return;
    	InOrderTraverse(T->lchild); /* 中序遍历左子树 */
    	printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    	InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
    }

**后序遍历：**

void PostOrderTraverse(BiTree T)
    {
    	if(T==NULL)
    		return;
    	PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */
    	PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */
    	printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    }

以上三种遍历方式很相似，只是递归的输出位置不同，从而决定了遍历的顺序，我们拿前序遍历举个例子：  
![这里写图片描述][format_png 1]  
还是上面这个图，此时函数的输入为树的根结点，这是一个BiTree 类型的变量，前面定义了它是一个指针，打印10，此时没有进入递归，深度为0：  
![这里写图片描述][format_png 2]  
执行`PreOrderTraverse(T->lchild)`递归两次后打印6、4，此时打印6的那次递归深度是1，打印4的递归深度是2：  
![这里写图片描述][format_png 3]  
此时执行`PreOrderTraverse(T->lchild)`，但是4没有左子结点，进入一下第3层递归又退出回到第2层，执行`PreOrderTraverse(T->rchild)`但是4没有右子结点，进入一下第3层递归又退出回到第2层，此时结点4已经执行完了，返回第1层（结点6），执行`PreOrderTraverse(T->rchild)`，打印8：  
![这里写图片描述][format_png 4]  
递归又到了第2层，显然又要退回到第1层，但是到了第1层发现第1层也执行完了，退回到第0层（结点10），执行`PreOrderTraverse(T->rchild)`，打印14，于是后面就一样了，直到打印了16之后，从第2层开始退出，退到第0层之后发现第0层也执行完了：  
![这里写图片描述][format_png 5]

最后，树的层序遍历与上面三种遍历方式不同，而且也不仅仅能用在二叉树，这个在本博客中先不涉及，后面补上。

## 其他操作 ##

二叉树除了遍历外，还有一些其他的基本操作：

构建空二叉树：

typedef int Status;	
    Status InitBiTree(BiTree *T)
    { 
    	*T=NULL;
    	return OK;
    }

销毁二叉树：

void DestroyBiTree(BiTree *T)
    { 
    	if(*T) 
    	{
    		if((*T)->lchild) /* 有左孩子 */
    			DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
    		if((*T)->rchild) /* 有右孩子 */
    			DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
    		free(*T); /* 释放根结点 */
    		*T=NULL; /* 空指针赋0 */
    	}
    }

创建二叉树：

void CreateBiTree(BiTree *T)
    { 
    	TElemType ch;
    
    	ch=str[index++];
    
    	if(ch=='#') 
    		*T=NULL;
    	else
    	{
    		*T=(BiTree)malloc(sizeof(BiTNode));
    		if(!*T)
    			exit(OVERFLOW);
    		(*T)->data=ch; /* 生成根结点 */
    		CreateBiTree(&(*T)->lchild); /* 构造左子树 */
    		CreateBiTree(&(*T)->rchild); /* 构造右子树 */
    	}
    }

判断二叉树是否存在：

Status BiTreeEmpty(BiTree T)
    { 
    	if(T)
    		return FALSE;
    	else
    		return TRUE;
    }

返回二叉树深度：

int BiTreeDepth(BiTree T)
    {
    	int i,j;
    	if(!T)
    		return 0;
    	if(T->lchild)
    		i=BiTreeDepth(T->lchild);
    	else
    		i=0;
    	if(T->rchild)
    		j=BiTreeDepth(T->rchild);
    	else
    		j=0;
    	return i>j?i+1:j+1;
    }

[format_png]: /images/20220610/28b002a5fd244c3ba2086f6962075a38.png
[format_png 1]: /images/20220610/415bf4cafcf54b6ab692371645238b0c.png
[format_png 2]: /images/20220610/7453de24962d4d83a900bbe0db1971ba.png
[format_png 3]: /images/20220610/1b8f99285fd14c3d935839f8883bb3fa.png
[format_png 4]: /images/20220610/de27665aac95498b8c35077c0b17d07f.png
[format_png 5]: /images/20220610/b65701fe2e1a4bd1a5996861923c5b67.png