C：二叉树

最近在面试，所以在整理一波数据结构，都忘记了.... 这篇是C语言的二叉树，还是我大学时候写的，目前翻出来看看，顺便敲一下，记一下。

二叉树的节点：

typedef struct BT
{
	char data;
	struct BT *lchild;
	struct Bt *rchild;
}BT;

二叉树的建立：

BT *Creattree()//建立二叉树
{
	BT *t;
	char x;
	scanf("%c",&x);
	getchar();
	if(x=='0')
		t=NULL;
	else
	{
		t=(BT *)malloc(sizeof(BT));
		t->data=x;
		printf("\n\t\t请输入%c结点的左子树结点：",t->data);
		t->lchild=Creattree();
		printf("\n\t\t请输入%c结点的右子树结点：",t->data);
		t->rchild=Creattree();
	}
	return t;
}

二叉树的先序遍历（根-左-右）：

void Preorder(BT *T)//先序遍历
{
    if(T)
    {
        printf("%3c",T->data);
        Preorder(T->lchild);
        Preorder(T->rchild);
    }
}

二叉树的中序遍历（左-根-右）：

void Inorder(BT *T)//中序
{
    if(T)
    {
        Inorder(T->lchild);
        printf("%3c",T->data);
        Inorder(T->rchild);
    }
}

非递归：
void Inorderse(BT *T)//按非递归中序遍历二叉树
{
    int i=0;//栈的初始化
    BT *p,*s[maxlen];//保存每个结点的指针的栈
    p=T;
    do
    {
        while(p!=NULL)
        {
            s[i++]=p;//结点的指针入栈
            p=p->lchild;//进入左子树
        }//左子树为空，退出
        if(i>0)//如果栈不空
        {
            p=s[--i];//结点的指针出栈
            printf("%3c",p->data);//访问出栈的结点
            p=p->rchild;
        }
    }while(i>0 || p!=NULL);//右子树为空同时栈为空时，结束循环
}

二叉树的后序遍历（左-右-根）：

void Postorder(BT *T)//后序
{
    if(T)
    {
        Postorder(T->lchild);
        Postorder(T->rchild);
        printf("%3c",T->data);
    }
}

二叉树的层次遍历：

void Levelorder(BT *T)//层次
{
    int i,j;
    BT *q[maxlen],*p;//q指针数组模拟队列，用来存放结点地址
    p=T;
    if(p!=NULL)//若二叉树非空，根结点地址入队
    {
        i=1;
        q[i]=p;
        j=2;
    }//i指向对头，j指向队尾
    while(i!=j)//访问队首结点的数据域
    {
        p=q[i];
        printf("%3c",p->data);
        if(p->lchild!=NULL)//将出队结点的左孩子的地址入队
        {
            q[j]=p->lchild;
            j++;
        }
        if(p->rchild!=NULL)//将出队结点的右孩子的地址入队
        {
            q[j]=p->rchild;
            j++;
        }
        i++;
    }
}

二叉树叶子总数：

void Leafnum(BT *T)//叶子总数
{
    if(T)//树不空
    {
        if(T->lchild==NULL && T->rchild==NULL)//若左右子树都为空
            count++;//叶子数加1
        Leafnum(T->lchild);//递归统计T左子树叶子节点数
        Leafnum(T->rchild);//递归统计T右子树叶子结点数
    }
}

二叉树的翻转（左右节点交换）：

BT *invertTree(BT *root)
{
    if(root == NULL)
        return NULL;
    swap(root->left,root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

二叉树的翻转的补充：

//递归
void MirroRecursively(BinaryTreeNode *pNode)  
{  
    if(NULL == pNode)  
        return;  
    if(NULL == pNode->Left && NULL == pNode->Right)  
        return;  
      
    BinaryTreeNode *pTemp = pNode->Left;  
    pNode->Left = pNode->Right;  
    pNode->Right = pTemp;  
      
    if(pNode->Left)  
        MirroRecursively(pNode->Left);  
    if(pNode->Right)  
        MirroRecursively(pNode->Right);  
}
非递归：
void MirrorNonRecurively(BinaryTreeNode *pNode)  
{  
    if(NULL == pNode)  
        return;  
  
    stack<BinaryTreeNode *> stackTreeNode;  
    stackTreeNode.push(pNode);  
  
    while(stackTreeNode.size())  
    {  
        BinaryTreeNode *pNode = stackTreeNode.top();  
        stackTreeNode.pop();  
  
        if(NULL != pNode->Left || NULL != pNode->Right)  
        {  
            BinaryTreeNode *pTemp = pNode->Left;  
            pNode->Left = pNode->Right;  
            pNode->Right = pTemp;  
        }  
          
        if(NULL != pNode->Left)  
            stackTreeNode.push(pNode->Left);  
  
        if(NULL != pNode->Right)  
            stackTreeNode.push(pNode->Right);  
    }  
}

本文由 Ryan 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2019/09/04 17:48