[已解决]求指教

小鱼fans

二叉树的凹凸式打印是什么意思，不要源代码，它的执行过程是什么

最佳答案

月排行榜 / 总排行榜

云客联盟

2013-11-18 22:06:58

二叉树是一种特殊的树，规矩的树，特殊在于每一个结点至多有两个子节点，是很多高级数据结构的基础。
定义：
typedef char ElemType;

typedef struct BTreeNode
{
        ElemType value;
        struct BTreeNode *lChild;
        struct BTreeNode *rChild;
}BTreeNode,*BTree;

二叉树的核心也是遍历，遍历大体上分两种：深度优先和广度优先，落实到二叉树也就是先序遍历、中序遍历、后序遍历以及层序遍历，最后一个算广度。

//初始化一个结点
BTree initNode(ElemType e)
{
        BTree pnew = (BTree)malloc(sizeof(BTreeNode));
        pnew->value = e;
        pnew->lChild = NULL;
        pnew->rChild = NULL;
        return pnew;
}

//释放二叉树：采用后续遍历的方式比较容易
void destroyBTree(BTree *T)
{
        if(NULL == *T)
                return ;
        destroyBTree(&(*T)->lChild);
        destroyBTree(&(*T)->rChild);
        free(*T);
        *T = NULL;        //野指针，注意赋空
}

//先序遍历
void PreOrderTraverse(BTree T)
{
        if(NULL == T)
                return ;
        else
        {
                printf("%c",T->value);
                PreOrderTraverse(T->lChild);
                PreOrderTraverse(T->rChild);
        }
}

//中序遍历
void InOrderTraverse(BTree T)
{
        if(NULL == T)
                return ;
        else
        {
                InOrderTraverse(T->lChild);
                printf("%c",T->value);
                InOrderTraverse(T->rChild);
        }
}

//后序遍历
void PostOrderTraverse(BTree T)
{
        if(NULL == T)
                return ;
        else
        {
                PostOrderTraverse(T->lChild);
                PostOrderTraverse(T->rChild);
                printf("%c",T->value);
        }
}

//求二叉树的深度
int TreeHeight(BTree T)
{
        int leftlen = 0;
        int rightlen = 0;
        int currMaxLen = 0;
        int len = 0;
       
        if(NULL == T)
                return 0;
        else
        {
                leftlen = TreeHeight(T->lChild);
                rightlen = TreeHeight(T->rChild);
                //获取左右子树高度的最大值
                leftlen > rightlen ? currMaxLen = leftlen : currMaxLen = rightlen;
                //与之前记录的最大值相比
                if(len < currMaxLen)
                        len = currMaxLen;
        }
        return len + 1;
}

//求二叉树中全部结点的个数
int count(BTree T)
{
        int leftCount = 0;
        int rightCount = 0;
        if(NULL == T)
                return 0;
        if(T)
        {
                leftCount = count(T->lChild);
                rightCount = count(T->rChild);
        }
        return leftCount + rightCount + 1;
}

//树的查找
//通过全局变量将查找到的结点带出来
BTree result = NULL;
void locateElem(BTree T,ElemType e)
{
        if(NULL == T)
                return ;
       
        //如果找到，把它赋给全局变量
        if(T->value == e)
        {
                result = T;
        }
       
        if(T != NULL)
        {
                locateElem(T->lChild,e);
                locateElem(T->rChild,e);
        }
}

BTree findLeftChild(BTree T,ElemType e)
{
        //必须清空全局变量
        result = NULL;
        locateElem(T,e);
        if(NULL == result)
                return NULL;
        else
                return result->lChild;
}

BTree findRightChild(BTree T, ElemType e)
{
        result = NULL;
        locateElem(T,e);
        if(NULL = result)
                return NULL;
        else
                return result->rChild;
}

//插入子树
//参数为：插入的某个数，插入结点的位置（0代表左子树，1代表右子树），插入为这个结点的左子树或者右子树，待插入的子树
bool insertSubTree(BTree T,ElemType e,int LR,BTree subT)
{
        //遍历树，找到插入的位置
        result = NULL;
        locateElem(T,e);
        //判断是否可以插入
        if(0 == LR && NULL == result->lChild)
        {
                result->lChild = subT;
                return true;
        }
        if(1 == LR && NULL == result->rChild)
        {
                result->rChild = subT;
                return true;
        }
        return false;
}

//删除子树
//参数为：需要被删除的树，删除的位置，删除它的左子树还是右子树
bool deleteSubTree(BTree T,ElemType e,int LR)
{
        //遍历树，找到待删结点位置
        result = NULL;
        locateElem(T,e);
        //判断是否可以删除
        if(0 == LR && NULL != result->lChild)
        {
                destroyBTree(&result->lChild)
                return true;
        }
       
        if(1 == LR && NULL != result->rChild)
        {
                destroyBTree(&result->rChild);
                return true;
        }
        return false;
}

//创建二叉树就用递归吧，别问我迭代，超烦
void Create(BTree &root)
{
        prinf("Enter the data \n");
        char temp;
        scanf("%c",&temp);
        if(temp == '#')                //#表示子树的结束
                root = NULL;
        else
        {
                root = (BTreeNode*)malloc(sizeof(BTreeNode));
                root->data = temp;
                Create(root->lChild);
                Create(root->rChild);
        }
}

程序使用的是递归实现，非递归我只说遍历部分，其他也差不多，遍历来说，如果采用深度搜索，可以考虑用一个具有栈性质的容器（可以是数组，链表，栈结构等等）来存入遍历结点的父节点的指针，比如最简单的先序遍历，先遍历结点，将结点压入栈中，指针索引指向其左子树，重复这个过程，一旦左子树为空，弹栈进入右子树，右子树本身又是一棵二叉树，这个过程就实现了，初学者可以用笔画画，就明白了。

至于广度搜索，其实更简单，用一个类似队列的结构来保存结点的左右子树，画一画，就一目了然了。

以上是从我师傅空间转来的，我没学过，不知道对你有没有用。最后还是发了，如果没有用，就当我是打酱油的。

跳转到最佳答案楼层

云客联盟

二叉树是一种特殊的树，规矩的树，特殊在于每一个结点至多有两个子节点，是很多高级数据结构的基础。
定义：
typedef char ElemType;

typedef struct BTreeNode
{
        ElemType value;
        struct BTreeNode *lChild;
        struct BTreeNode *rChild;
}BTreeNode,*BTree;

二叉树的核心也是遍历，遍历大体上分两种：深度优先和广度优先，落实到二叉树也就是先序遍历、中序遍历、后序遍历以及层序遍历，最后一个算广度。

//初始化一个结点
BTree initNode(ElemType e)
{
        BTree pnew = (BTree)malloc(sizeof(BTreeNode));
        pnew->value = e;
        pnew->lChild = NULL;
        pnew->rChild = NULL;
        return pnew;
}

//释放二叉树：采用后续遍历的方式比较容易
void destroyBTree(BTree *T)
{
        if(NULL == *T)
                return ;
        destroyBTree(&(*T)->lChild);
        destroyBTree(&(*T)->rChild);
        free(*T);
        *T = NULL;        //野指针，注意赋空
}

//先序遍历
void PreOrderTraverse(BTree T)
{
        if(NULL == T)
                return ;
        else
        {
                printf("%c",T->value);
                PreOrderTraverse(T->lChild);
                PreOrderTraverse(T->rChild);
        }
}

//中序遍历
void InOrderTraverse(BTree T)
{
        if(NULL == T)
                return ;
        else
        {
                InOrderTraverse(T->lChild);
                printf("%c",T->value);
                InOrderTraverse(T->rChild);
        }
}

//后序遍历
void PostOrderTraverse(BTree T)
{
        if(NULL == T)
                return ;
        else
        {
                PostOrderTraverse(T->lChild);
                PostOrderTraverse(T->rChild);
                printf("%c",T->value);
        }
}

//求二叉树的深度
int TreeHeight(BTree T)
{
        int leftlen = 0;
        int rightlen = 0;
        int currMaxLen = 0;
        int len = 0;
       
        if(NULL == T)
                return 0;
        else
        {
                leftlen = TreeHeight(T->lChild);
                rightlen = TreeHeight(T->rChild);
                //获取左右子树高度的最大值
                leftlen > rightlen ? currMaxLen = leftlen : currMaxLen = rightlen;
                //与之前记录的最大值相比
                if(len < currMaxLen)
                        len = currMaxLen;
        }
        return len + 1;
}

//求二叉树中全部结点的个数
int count(BTree T)
{
        int leftCount = 0;
        int rightCount = 0;
        if(NULL == T)
                return 0;
        if(T)
        {
                leftCount = count(T->lChild);
                rightCount = count(T->rChild);
        }
        return leftCount + rightCount + 1;
}

//树的查找
//通过全局变量将查找到的结点带出来
BTree result = NULL;
void locateElem(BTree T,ElemType e)
{
        if(NULL == T)
                return ;
       
        //如果找到，把它赋给全局变量
        if(T->value == e)
        {
                result = T;
        }
       
        if(T != NULL)
        {
                locateElem(T->lChild,e);
                locateElem(T->rChild,e);
        }
}

BTree findLeftChild(BTree T,ElemType e)
{
        //必须清空全局变量
        result = NULL;
        locateElem(T,e);
        if(NULL == result)
                return NULL;
        else
                return result->lChild;
}

BTree findRightChild(BTree T, ElemType e)
{
        result = NULL;
        locateElem(T,e);
        if(NULL = result)
                return NULL;
        else
                return result->rChild;
}

//插入子树
//参数为：插入的某个数，插入结点的位置（0代表左子树，1代表右子树），插入为这个结点的左子树或者右子树，待插入的子树
bool insertSubTree(BTree T,ElemType e,int LR,BTree subT)
{
        //遍历树，找到插入的位置
        result = NULL;
        locateElem(T,e);
        //判断是否可以插入
        if(0 == LR && NULL == result->lChild)
        {
                result->lChild = subT;
                return true;
        }
        if(1 == LR && NULL == result->rChild)
        {
                result->rChild = subT;
                return true;
        }
        return false;
}

//删除子树
//参数为：需要被删除的树，删除的位置，删除它的左子树还是右子树
bool deleteSubTree(BTree T,ElemType e,int LR)
{
        //遍历树，找到待删结点位置
        result = NULL;
        locateElem(T,e);
        //判断是否可以删除
        if(0 == LR && NULL != result->lChild)
        {
                destroyBTree(&result->lChild)
                return true;
        }
       
        if(1 == LR && NULL != result->rChild)
        {
                destroyBTree(&result->rChild);
                return true;
        }
        return false;
}

//创建二叉树就用递归吧，别问我迭代，超烦
void Create(BTree &root)
{
        prinf("Enter the data \n");
        char temp;
        scanf("%c",&temp);
        if(temp == '#')                //#表示子树的结束
                root = NULL;
        else
        {
                root = (BTreeNode*)malloc(sizeof(BTreeNode));
                root->data = temp;
                Create(root->lChild);
                Create(root->rChild);
        }
}

程序使用的是递归实现，非递归我只说遍历部分，其他也差不多，遍历来说，如果采用深度搜索，可以考虑用一个具有栈性质的容器（可以是数组，链表，栈结构等等）来存入遍历结点的父节点的指针，比如最简单的先序遍历，先遍历结点，将结点压入栈中，指针索引指向其左子树，重复这个过程，一旦左子树为空，弹栈进入右子树，右子树本身又是一棵二叉树，这个过程就实现了，初学者可以用笔画画，就明白了。

至于广度搜索，其实更简单，用一个类似队列的结构来保存结点的左右子树，画一画，就一目了然了。

以上是从我师傅空间转来的，我没学过，不知道对你有没有用。最后还是发了，如果没有用，就当我是打酱油的。

怡静

谢谢楼主！