数据结构二叉树的建立与遍历

落日映苍穹つ 2022-09-19 01:44 175阅读 0赞

1.结点拥有的子树数称为结点的度(degree)，度为0的结点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点，树的度是树内各结点的度的最大值。 2.树中结点的最大层次称为树的深度或高度。 3.二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。 4.斜树：所有的结点都只有左子树的二叉树叫左斜树所有的结点都是只有右子树的二叉树叫右斜树。 5.满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样的二叉树称为满二叉树。
    性质：
        叶子结点只能出现在最下一层。
        非叶子结点的度一定是2
        在同等深度的二叉树中，满二叉树的结点个数最多，叶子数最多。 6.完全二叉树：对一棵具有n个结点的二叉树按层次编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵树称为完全二叉树。
    性质：
       叶子结点只能出现在最下两层
       最下层的叶子一定集中在左部连续位置
       倒数二层，若有叶子结点，一定都在右部连续位置
       如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
       同样结点数的二叉树，完全二叉树的深度最小。 7.二叉树的性质
      在二叉树的第i层上至多有2^(i-1)结点。
      深度为k的二叉树至多有2^k-1个结点
      对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则 n0 = n2 + 1.
      假设度为1的结点数为n1，则有总数为 n = n0 + n1 + n2;再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n = B + 1。由于这些分支是由度为1或2的结点射出的，所以又有B = n1 + 2n2，于是有n0 + n1 + n2 = n1 + 2n2 + 1 --> n0 = n2 + 1
      具有n个结点的完全二叉树的深度为[log2n] + 1 ([log2n]表示不大于x的最大整数).
      如果对一棵有n个结点的完全二叉树的结点按层序编号，对任一结点i有
          如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。
          如果2i>n，则结点i无左孩子；否则其左孩子是结点2i。
          如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1.

#include <stdio.h>
    #include <stdlib.h>
    
    #define OK            1
    #define ERROR         0
    #define OVERFLOW     -2
    
    typedef char TElemType;
    
    typedef struct BiNode
    {
    	TElemType data;
    	struct BiNode *lchild,*rchild;
    }BiNode, *BiTree;
    
    void Create_BiTree(BiTree &T)
    {
    	TElemType ch;
    	scanf("%c",&ch);
    	if (ch == '#')
    	{
    		T = NULL;
    	}
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiNode));
    		if (!T)
    		{
    			exit(OVERFLOW);
    		}
    		T->data = ch;
    		Create_BiTree(T->lchild);
    		Create_BiTree(T->rchild);
    	}
    }
    
    
    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);//访问根结点
    }
    
    int main()
    {
    	BiTree T;
    	Create_BiTree(T);
    	PreOrderTraverse(T);
    	printf("\n");
    	InOrderTraverse(T);
    	printf("\n");
    	PostOrderTraverse(T);
    	printf("\n");
    
    	return 0;
    }