二叉树的建立、遍历规则、以及节点计算

二叉树的建立、遍历规则、以及节点计算

二叉树故名思意就是只有两个度的树，这里讨论其最基本的用法及逻辑。

树的创立

定义一颗二叉树首先要有一个度里的数据data，以及左右孩子，我们可以用结构体定义以方便其理解。

结构体定义：

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

我们给左右孩子分别定位Left和Right，这样我们就可以使用T->Left和T->Right等方式进行调用，利于理解。

树的构建：

binTree creatBintree()
{
	int a;
	binTree b;
	scanf("%d", &a);
	if (0 == a)	//如果输入0，则停止创建
		b = NULL;
	else
	{
		b = (binTree)malloc(sizeof(struct binNode));
		b->element = a;
		b->leftChild = creatBintree();
		b->rightChild = creatBintree();
		
	}
	return b;
}

树的遍历

当我们构建起了一个树后我们怎么对树进行遍历读取呢？可以用前、中、后序遍历，打比方我们用前序遍历就是通过（根、左、右）对树进行读取，也就是首先将最上面的节点作为root，然后将所有左边和右边的节点看作孩子，然后再将此时左孩子最上面的节点作为root进一步（根、左、右）读取，以此类推进行遍历。我们可以用递归的方式来实现代码。

前序遍历

void PreorderPrintLeaves( BinTree BT )
{
    if(BT==NULL) return;
    if(BT->Left==NULL && BT->Right==NULL){
        printf(" %c",BT->Data); //输出结果
    }
    PreorderPrintLeaves(BT->Left);
    PreorderPrintLeaves(BT->Right);
}

中序遍历

void PreorderPrintLeaves( BinTree BT )
{
    if(BT==NULL) return;
    PreorderPrintLeaves(BT->Left);
    if(BT->Left==NULL && BT->Right==NULL){
        printf(" %c",BT->Data);
    }    
    PreorderPrintLeaves(BT->Right);
}

后序遍历

void PreorderPrintLeaves( BinTree BT )
{
    if(BT==NULL) return;
    PreorderPrintLeaves(BT->Left);  
    PreorderPrintLeaves(BT->Right);
    if(BT->Left==NULL && BT->Right==NULL){
        printf(" %c",BT->Data);
    }  
}

节点的计算

节点的计算需要通过左右子树的孩子判断来对其进行加法运算，我们可以用T->lchild!=NULL来表示没有左孩子，同理可以右孩子也是T->rchild!=NULL，这样就可以区分度为1、2或叶子节点。

计算节点数

int NodeCount ( BiTree T)
{
    if(T==NULL) return 0;
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1; //全部一次性+1
}

计算度为1的节点数

int NodeCount ( BiTree T){
    if(T==NULL) return 0;
    if(( T->lchild!=NULL && T->rchild==NULL) || ( T->lchild==NULL && T->rchild!=NULL))
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1; //这里次数+1
    return NodeCount (T->lchild)+NodeCount (T->rchild); //直接return，次数不变
}

计算度为2的节点数

int NodeCount ( BiTree T){
    if(T==NULL) return 0;
    if( T->lchild!=NULL && T->rchild!=NULL)
        return 1+NodeCount (T->lchild)+NodeCount (T->rchild);
    return NodeCount (T->lchild)+NodeCount (T->rchild);
}

计算叶子节点个数

int LeafCount ( BiTree T){
    if(T == NULL) return 0;
    if(T->lchild==NULL && T->rchild==NULL) return 1;
    return LeafCount(T->lchild)+LeafCount(T->rchild);
}

树高计算

我们可以定义两个整型m，n分别来表示左右两边的树高度，用递归的方式实现向下计算。

int GetHeight( BinTree BT ){
     int m, n;
     if (BT == NULL)
         return 0;
     else{
         m = GetHeight(BT->Left);
         n = GetHeight(BT->Right);
         if (m > n)
             return (m + 1);
        else
             return (n + 1);
     }
 }