c++ 数据结构（树）

短命女 2023-06-12 11:28 10阅读 0赞

## 树的一些基本定义 ##

*  树的结点——包含数据结构及若干指向其子树的分支
 *  结点的度——结点拥有的子树
 *  终端结点（叶子）——度为0的结点
 *  非终端结点（分支结点）——度不为0的结点
 *  树的度——树内各结点的度的最大值
 *  孩子——结点的子树
 *  兄弟——同一个双亲的孩子互相之间互称兄弟
 *  祖先——从根到该结点所经分支上的所有结点
 *  层次——从根开始定义起，根为第一层，根的孩子为第二层
 *  深度——树中结点的最大层次
 *  有序树——树中结点的各子数看成从左往右是有次序的
 *  森林——互不相交的树的集合
 *  二叉树——每个结点至多只有两个子树，并且，二叉树的子树有**左右之分**，其次序不能任意颠倒。
 *  满二叉树——一颗深度为k且有2的k次方-1个结点的二叉树
 *  完全二叉树——深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点**一一对应**时，称之为完全二叉树

## 二叉树的定义 ##

二叉树的性质：  
**1.在二叉树的第i层上至多有2的i-1次方个结点**  
**2.深度为k的二叉树至多有2的k次方-1个节点**  
**3.对任何一颗二叉树T，如果其终端结点数n0,度为2的结点数为n2,则n0=n2+1**

## 二叉树的存储结构 ##

*  顺式存储
 *  链式存储  
    这里我们主要介绍链式存储结构

**其数据结构定义如下：**

typedef struct TreeNode{
        
    	ELemType data;
    	struct TreeNode *lchild,*rchild;			//分别代表左子树和右子树
    }TreeNode,*BinTree;

**二叉树的初始化和创建：**

Status InitTree(BinTree &B){
        
    	B = NULL;
    }

Status CreateTree(BinTree &B){
        
    	scanf("%c",&ch);
    	if(ch == ' ')
    		return 0;
    	else
    	{
        
    		B = (ElemType *)malloc(sizeof(ElemType));
    		if(!B)
    			return 0;
    		CreateTree(B->lchild);
    		CreateTree(B->rchild);
    	}
    }

**二叉树的遍历可用递归表示：**  
**先序遍历：**

Status PreOrderTraverse(BinTree &B)
    {
        
    	if(B)
    	{
        
    		PreOrderTraverse(B->lchild);
    		printf("%c",B->data);
    		PreOrderTraverse(B->rchild);
    	}
    }

**中序遍历与后序遍历只需调整递归的函数与printf的位置即可**