数据结构系列　二叉树的遍历（顺序存储）

电玩女神 2023-06-28 08:50 19阅读 0赞

[https://blog.csdn.net/lin20044140410/article/details/89436835][https_blog.csdn.net_lin20044140410_article_details_89436835] 二叉树链式存储

数据结构-树

树是一种一对多的数据结构，是n(n>=0)个结点的有限集。N=0时为空树。在任意一棵非空树中：1，有且只有一个特定的称为根root的结点，2，当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1,T2,,,,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

一些概念：

1.  结点拥有的子树数称为阶段的度，度为0的结点称为叶结点Leaf，度不为0的结点称为分支结点。树的度是树内个结点的度的最大值。
2.  结点的层次，从根开始，根为第一层，根的孩子为第二层，树中结点的最大层次称为树的深度，或者高度。

二叉树

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

二叉树的特点：

1.  每个结点最多两棵子树，
2.  左子树、右子树是有顺序的，次序不能颠倒，
3.  即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

特殊的二叉树

斜树，所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树。斜树，其实就是线性表结构。

满二叉树，在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树特点：

1.  叶子只能出现在最下一层，
2.  非叶子结点的度一定是2
3.  在同样深度的二叉树中，满二叉树的结点个数最多，叶子最多。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

满二叉树一定是一棵完全二叉树，但是完全二叉树不一定是满的。

完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70][]

上图是一棵完全二叉树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70 1][]

图中树1，树2，树3因为编号不连续，都不是完全二叉树，

完全二叉树特点：

1.  叶子结点只能出现在最下两层。
2.  最下层叶子结点一定集中在左部连续位置。
3.  倒数第二层，如有叶子结点，一定都在右部连续位置。
4.  如果结点度为1，则该节点只有左孩子，不存在只有右子树的情况。
5.  同样结点数的二叉树，完全二叉树深度最小。

判断一棵二叉树是不是完全二叉树，就是给每个结点按照满二叉树的结构逐层编号，如果编号出现空挡，就不是完全二叉树。

二叉树的性质

1.  在二叉树的第i层，至多有2(i-1) (i>=1)
2.  深度是k的二叉树，最多有2k -1 个结点 k>=1.

以上两点都可以通过数据归纳法来得出结论。

1.  任意一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则n0 = n2 +1，
2.  具有n个结点的完全二叉树的深度为log*2n*![20200108133539804.png][] \+1
3.  如果对一棵有n个结点的完全二叉树（深度为log*2n*![2020010813354595.png][] \+1）的结点，按层序编号（从第1层到第log*2n*![20200108133545101.png][] \+1 层，每层从左到右），对于任一结点i(1<=I <=n)：

如果i = 1，结点i就是二叉树的根，无双亲，如果i>1,则其双亲是结点 i/2 (向下取整)。

如果2i >n，则结点i无左孩子，结点i为叶子结点；否则其左孩子是结点2i。

如果2i + 1 > n，则结点i无右孩子，否则其右孩子是结点2i + 1。

依据以上性质，来定义二叉树的存储结构，先说顺序存储。

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，结点的存储位置，就是数组的下标，相应位置不存在的结点设置为null。这种存储结构，适用于完全二叉树，因为对于极端的右斜树，它有k个结点，却要分配2k -1个存储空间，这是对存储空间的浪费。

二叉树的链式存储结构，每个结点最多两个孩子，所以这种存储结构，一个数据域，两个指针域，两个指针域存放指向左孩子和右孩子的指针，称这样的存储结构为二叉链表。

二叉树的遍历

对二叉树的遍历，就是把树中的结点变成某种意义的线性序列。

遍历算法就是递归。

1.  前序遍历，若二叉树为null，则空操作返回，否则先访问根结点，然后前序遍历左子树，在前序遍历右子树。
2.  中序遍历，若树为null，则空操作返回，否则从根结点开始，中序遍历左子树，然后访问根结点，最后中序遍历右子树。
3.  后序遍历，若树为null，则空操作返回，否则从左到右，先叶子后结点的方式，先遍历访问左子树，再同样从左到右，先叶子后结点的方式，遍历右子树，最后访问根结点。
4.  层序遍历，若树为null，则空操作返回，否则从树的第一层根结点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

从遍历操作可以得出，

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；

已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；

这两种情况都可以确定根结点，并且可以确定左子树或者右子树。

但是，已知前序和后序序列，是不能确定一棵二叉树的，因为虽然根结点可以确定，但是无法确定那个结点是左子树，那个结点是右子树。

二叉树顺序存储代码实现：

#ifndef DATA_STRUCTURE_BINARY_TREE_CLASS_H
    #define DATA_STRUCTURE_BINARY_TREE_CLASS_H 
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 100 //存储空间初始分配量
    #define MAX_TREE_SIZE 100 //二叉树最大结点树
    
    typedef int Status; //表示函数结果的状态码
    typedef int TElemType; //树节点的数据类型，暂定int
    typedef TElemType SqBiTree[MAX_TREE_SIZE]; //顺序存储结构数组
    
    typedef struct {
        int level;//节点的层
        int order;//本层的序号，按满二叉树计算
    }Position;
    
    TElemType Nil = 0; //表示空元素
    
    #endif

#include "binaryTree.h"
    
    #include "iostream"
    #include "cstdlib"
    #include "cmath"
    using namespace std;
    Status visit(TElemType c) {
       cout << "node:" << c <<endl;
    }
    
    //构造空二叉树
    Status InitBiTree(SqBiTree T) {
    	int i;
    	for (i = 0; i< MAX_TREE_SIZE; i++) {
    		T[i] = Nil;//空值
    	}
    
    	return OK;
    }
    
    Status CreateBiTree(SqBiTree T) {
    	int i=0;
    	cout<< "按层序输入结点的值，整形数，0表示空结点，结点数 <=" <<
    		MAX_TREE_SIZE <<endl;
    	//对前10个结点赋值
    	while (i < 10) {
    		T[i] = i+1;
    		cout << "结点：" << i <<",值:"<<    T[i] << endl;
    		//对于非根结点，一定有双亲，如果没有就出错了
    		if (i != 0 && T[(i+1)/2 -1] == Nil && T[i] != Nil) {
    			cout << "无双亲的非根结点：" <<         T[i] << endl;
    			exit(ERROR);
    		}
    		i++;
    	}
    
    	//其余结点赋值空
    	while(i < MAX_TREE_SIZE) {
    		T[i] = Nil;
    		i++;
    	}	
    	return OK;
    }
    
    //判空树
    Status BiTreeEmpty(SqBiTree T) {
        //如果根结点为空，即空树
    	if (T[0] == Nil) {
    		return TRUE;
    	} else {
    		return FALSE;
    	}
    }
    
    //获取树的深度
    int BiTreeDepth(SqBiTree T) {
    	int i,j=-1;
    	for (i = MAX_TREE_SIZE-1; i>=0; i--) {
    		if (T[i] != Nil) {//找到最后一个不为空的结点
    			break;
    		}
    	}
    	//因为在找到最后一个非空结点后，for又做了一次i--，所以要在加回去
    	i++;
    	//根据前面的性质，深度为k二叉树，最多有2k（2的k次幂） -1 个结点，
    	//现在知道结点数，反推深度
    	do{
    	    j++;
    	}while (i>=powl(2,j));
    
    	return j;
    }
    
    //获取根结点
    Status Root(SqBiTree T, TElemType *e) {
    	if (BiTreeEmpty(T)) {
    		return ERROR;
    	} else {
    		*e = T[0];
    		return OK;
    	}
    }
    
    //获取指定位置的结点,参数e包含结点所在的层，及本层的序号。
    TElemType Value(SqBiTree T, Position e) {
    	return T[(int)powl(2, e.level -1) + e.order -2];
    }
    
    //给指定位置的结点赋值
    Status Assign(SqBiTree T, Position e, TElemType value) {
    	//获取数组的序号
    	int i = (int)powl(2, e.level -1) + e.order -2;
    	if (value != Nil && T[(i+1)/2-1] == Nil) {
    		//非根结点，无双亲
    		return ERROR;
    	} else if (value == Nil && (T[i*2+1] !=Nil || T[i*2+2] !=Nil)) {
    		//左孩子或者右孩子不为空，就不能给其双亲赋值空
    		return ERROR;
    	}
    	T[i] = value;
    	return OK;
    }
    
    //返回结点的双亲
    TElemType Parent(SqBiTree T, TElemType e) {
    	int i;
    	if (T[0] == Nil) {
    		return Nil;
    	}
    	for (i = 1; i<MAX_TREE_SIZE-1; i++) {
    		if (T[i] == e) {
    			return T[(i+1)/2-1];
    		}
    	}
    	return Nil;
    }
    
    //返回左孩子
    TElemType LeftChild(SqBiTree T, TElemType e) {
    	int i;
    	if (T[0] == Nil) {
    		return Nil;
    	}
    	for (i =0; i<= MAX_TREE_SIZE -1; i++) {
    		if (T[i] == e) {
    			return T[i*2 +1];
    		}
    	}
    	return Nil;
    }
    
    //返回右孩子
    TElemType RightChild(SqBiTree T, TElemType e) {
    	int i;
    	if (T[0] == Nil) {
    		return Nil;
    	}
    	for (i =0; i<= MAX_TREE_SIZE -1; i++) {
    		if (T[i] == e) {
    			return T[i*2 +2];
    		}
    	}
    	return Nil;
    }
    
    //前序遍历
    void PreTraverse(SqBiTree T, int e) {
    	visit(T[e]);
    	if (T[2*e +1] != Nil) {
    		PreTraverse(T, 2*e+1);
    	}
    	if (T[2*e +2] != Nil) {
    		PreTraverse(T, 2*e+2);
    	}
    }
    
    Status PreOrderTraverse(SqBiTree T) {
    	cout << "前序遍历。。。" << endl;
    	if (!BiTreeEmpty(T)) {
    		PreTraverse(T, 0);
    	}
    	return OK;
    }
    
    //中序遍历
    void InTraverse(SqBiTree T, int e) {
    	if (T[2*e +1] != Nil) {
    		InTraverse(T, 2*e+1);
    	}
    	visit(T[e]);
    	if (T[2*e +2] != Nil) {
    		InTraverse(T, 2*e+2);
    	}
    }
    
    Status InOrderTraverse(SqBiTree T) {
    	cout << "中序遍历。。。" << endl;
    	if (!BiTreeEmpty(T)) {
    		InTraverse(T, 0);
    	}
    	return OK;
    }
    
    //后序遍历
    void PostTraverse(SqBiTree T, int e) {
    	if (T[2*e +1] != Nil) {
    		PostTraverse(T, 2*e+1);
    	}
    	if (T[2*e +2] != Nil) {
    		PostTraverse(T, 2*e+2);
    	}
    	visit(T[e]);	
    }
    
    Status PostOrderTraverse(SqBiTree T) {
    	cout << "后序遍历。。。" << endl;
    	if (!BiTreeEmpty(T)) {
    		PostTraverse(T, 0);
    	}
    	return OK;
    }
    
    //层序遍历
    void LevelOrderTraverse(SqBiTree T) {
    	int i = MAX_TREE_SIZE -1;
    	cout << "层序遍历。。。" << endl;
    	while (T[i] == Nil) {
    		i--;//查找最后一个非空结点
    	}
    	cout << "最后一个非空结点(数组小标从0开始)：" << i << endl;
    	for (int j=0; j<=i; j++) {
    		if(T[j] != Nil) {
    			visit(T[j]);
    		}
    	}
    	cout << endl;
    }
    
    //按层输出结点
    void LevelOrderVisist(SqBiTree T) {
    	int j,k;
    	Position p;
    	TElemType e;
    	cout << "按层输出结点。。。" << endl;
    	for (j=1;j<=BiTreeDepth(T);j++) {
    		cout <<"第 "<<j <<"层：" <<endl;
    		for (k=1;k<=powl(2,j-1);k++) {
    			p.level = j;
    			p.order =k;
    			e= Value(T,p);
    			if (e != Nil) {
    				cout << k << ":" << e << endl;
    			}
    		}
    		cout <<endl;
    	}
    }
    
    int main() {
    	Status i;
    	Position p;
    	TElemType e;
    	SqBiTree T;
    	InitBiTree(T);
    	CreateBiTree(T);
    	cout << "新建的二叉树，深度：" << BiTreeDepth(T) << endl;
    
    	i = Root(T, &e);
    	cout << "二叉树的根：" << e << endl;
    	LevelOrderVisist(T);
    	LevelOrderTraverse(T);
    	PreOrderTraverse(T);
    	InOrderTraverse(T);
    	PostOrderTraverse(T);
    	
    	p.level = 3;
    	p.order = 2;
    	e = Value(T, p);
    	cout << "修改第3层第2个结点的值，原值："<< e << "新值为50." << endl;
    	e = 50;
    	Assign(T, p, e);
    	e = Value(T, p);
    	cout << "修改后的第3层第2个结点的值："<< e  << endl;
    	PreOrderTraverse(T);
    
    	return 0;
    }

/\*\*output/

$ g++ -g BinaryTree.cpp -o BiTree  
$ ./BiTree

按层序输入结点的值，整形数，0表示空结点，结点数 <=100
    结点：0,值:1
    结点：1,值:2
    结点：2,值:3
    结点：3,值:4
    结点：4,值:5
    结点：5,值:6
    结点：6,值:7
    结点：7,值:8
    结点：8,值:9
    结点：9,值:10
    新建的二叉树，深度：4
    二叉树的根：1
    按层输出结点。。。
    第 1层：
    1:1
    
    第 2层：
    1:2
    2:3
    
    第 3层：
    1:4
    2:5
    3:6
    4:7
    
    第 4层：
    1:8
    2:9
    3:10
    
    层序遍历。。。
    最后一个非空结点(数组小标从0开始)：9
    node:1
    node:2
    node:3
    node:4
    node:5
    node:6
    node:7
    node:8
    node:9
    node:10
    
    前序遍历。。。
    node:1
    node:2
    node:4
    node:8
    node:9
    node:5
    node:10
    node:3
    node:6
    node:7
    中序遍历。。。
    node:8
    node:4
    node:9
    node:2
    node:10
    node:5
    node:1
    node:6
    node:3
    node:7
    后序遍历。。。
    node:8
    node:9
    node:4
    node:10
    node:5
    node:2
    node:6
    node:7
    node:3
    node:1
    修改第3层第2个结点的值，原值：5新值为50.
    修改后的第3层第2个结点的值：50
    前序遍历。。。
    node:1
    node:2
    node:4
    node:8
    node:9
    node:50
    node:10
    node:3
    node:6
    node:7

[https_blog.csdn.net_lin20044140410_article_details_89436835]: https://blog.csdn.net/lin20044140410/article/details/89436835
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020010813345028.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200108133514471.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw,size_16,color_FFFFFF,t_70
[20200108133539804.png]: https://img-blog.csdnimg.cn/20200108133539804.png
[2020010813354595.png]: https://img-blog.csdnimg.cn/2020010813354595.png
[20200108133545101.png]: https://img-blog.csdnimg.cn/20200108133545101.png