二叉树 —— 创建二叉树 先序遍历 、中序遍历、后序遍历（递归方式、非递归方式）

#include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef char DataType; #define MaxSize 100 typedef struct Node {DataType data;struct Node *lchild;struct Node *rchild; }*BiTree,BitNode; void InitBitTree(BiTree *T);/*树的初始化*/ void CreaBitTree(BiTree *T);/*按照先序输入字符序列递归创建二叉树*/ void PreOrderTraverse(BiTree T);/*二叉树的先序遍历的递归函数声明*/ void InOrderTraverse(BiTree T);/*二叉树的中序遍历的递归函数声明*/ void PostOrderTraverse(BiTree T);/*二叉树的后序遍历的递归函数声明*/ void PreOrderTraverse2(BiTree T);/*二叉树的先序遍历的非递归函数声明*/ void InOrderTraverse2(BiTree T);/*二叉树的中序遍历的非递归函数声明*/ void PostOrderTraverse2(BiTree T);/*二叉树的后序遍历的非递归函数声明*/ void main() {BiTree T,root;InitBitTree(&T);printf("根据输入二叉树的先序序列创建二叉树('#'表示结束):\n");CreaBitTree(&T);printf("二叉树的先序遍历：\n");printf("递归方式：\t");PreOrderTraverse(T);printf("\n");printf("非递归方式：\t");PreOrderTraverse2(T);printf("\n");printf("二叉树的中序遍历：\n");printf("递归方式：\t");InOrderTraverse(T);printf("\n");printf("非递归方式：\t");InOrderTraverse2(T);printf("\n");printf("二叉树的后序遍历：\n");printf("递归方式：\t");PostOrderTraverse(T);printf("\n");printf("非递归方式：\t");PostOrderTraverse2(T);printf("\n");} void InitBitTree(BiTree *T) {*T = NULL; } void CreaBitTree(BiTree *T) {DataType ch;scanf(" %c",&ch);if(ch == '#')*T = NULL;else{*T = (BiTree)malloc(sizeof(BitNode));//生成根节点if(!(*T))exit(-1);(*T)->data = ch;CreaBitTree(&((*T)->lchild));//构造左子树CreaBitTree(&((*T)->rchild));//构造右子树} } void PreOrderTraverse(BiTree T) {if(T)//如果二叉树不为空{printf("%2c",T->data);//访问根节点PreOrderTraverse(T->lchild);//先序遍历左子树PreOrderTraverse(T->rchild);//先序遍历右子树} } void InOrderTraverse(BiTree T) {if(T)//如果二叉树不为空{InOrderTraverse(T->lchild);//中序遍历左子树printf("%2c",T->data);//访问根节点InOrderTraverse(T->rchild);//中序遍历右子树} } void PostOrderTraverse(BiTree T) {if(T){PostOrderTraverse(T->lchild);//后序遍历左子树PostOrderTraverse(T->rchild);//后序遍历右子树printf("%2c",T->data);//访问根节点} } void PreOrderTraverse2(BiTree T) {BiTree stack[MaxSize]; //定义一个栈 用于存放结点的指针int top;//定义栈顶指针BitNode *p; //定义一个节点的指针top = 0; //初始化栈p = T;while(p != NULL || top>0){while(p != NULL) //如果p不是空，访问根节点，遍历左子树{printf("%2c",p->data); //访问根节点stack[top++] = p; //将p入栈p = p->lchild; //遍历左子树}if(top > 0) //如果栈不为空{p = stack[--top]; //栈顶元素出栈p = p->rchild; //遍历右子树}}} void InOrderTraverse2(BiTree T) {BiTree stack[MaxSize];int top;BitNode *p;top = 0;p = T;while(p != NULL || top > 0){while(p != NULL){stack[top++] = p;p = p->lchild;}if(top > 0){p = stack[--top];printf("%2c",p->data);p = p->rchild;}} } void PostOrderTraverse2(BiTree T) {BiTree stack[MaxSize];int top;BitNode *p,*q;top = 0;p = T,q = NULL;while(p != NULL || top > 0){while(p != NULL){stack[top++] = p;p = p->lchild;}if(top > 0){p = stack[top-1];//取栈顶元素if(p->rchild == NULL || p->rchild ==q) //如果p没有右孩子结点，或者右孩子结点已经访问过{printf("%2c",p->data); //访问根节点q = p;p = NULL;top--;}elsep = p->rchild;}}} ~ ~

 

[root@J01051386 Test_20180418]# ./a.out
根据输入二叉树的先序序列创建二叉树('#'表示结束):
e#
r#
G#
#
二叉树的先序遍历：
递归方式：     e r G
非递归方式：     e r G
二叉树的中序遍历：
递归方式：     e r G
非递归方式：     e r G
二叉树的后序遍历：
递归方式：     G r e
非递归方式：     G r e

---

//创建一个存储整数的二叉树 //首先 创建一个跟节点 所有节点的创建方式都相同 //这个函数返回指向新建Node对象的指针，要为新的二叉树创建根节点，可以使用这个函数 struct Node *createnode(long value) {struct Node *pNode = (struct Node *)malloc(sizeof(struct Node));pNode->item = value; //set the valuepNode->count = 1;pNode->pLeft = pNode->pRight = NULL;return pNode; } long newvalue; printf("Enter the node value:"); //从键盘上读取存储值后 scanf("%ld",newvalue); //调用函数 在堆上创建一个新的节点 不要忘记使用完毕以后释放节点内存 struct Node *pRoot = createnode(newvalue); //二叉树是应用递归的一个领域，插入节点的过程涉及到以相同的方式查看一系列节点，这里使用递归的一个强烈的暗示。 //用下面的函数在树中添加一个已有的节点 add a new node to a tree struct Node *addnod(long value,struct Node* pNode) {if(pNode == NULL)return createnode(value);//把根节点作为第二个变元传送时//如果value等于当前节点的值，就不需要创建新节点，只递增当前节点中的计数器，并返回该节点if(value == pNode->item){++pNode -> count;return pNode;}//如果value小于当前节点的值，就需要查看左子节点，如果左节点的指针是NULL，就创建一个包含value的新节点，使之成为左子节点。如果左节点存在，就递归调用addnod()函数，把指向左子节点的指针作为第二个变元。if(value < pNode->item){if(pNode->left == NULL){pNode->pLeft = createnode(value);return pNode->pLeft;}else{return addnode(value,pNode->pLeft);}}else{if(pNode->pRight == NULL){pNode->pRight = createnode(value);return pNode->pRight}else{return addnode(value,pNode->pRight);}} }//无论调用递归函数时执行了什么，该函数都返回一个插入值的节点的指针，这可能时一个新节点，也可以是一个其值已经存在于树中的节点 do {printf("Enter the node value:");scanf(" %ld",&newvalue);if(pRoot == NULL)pRoot = createnode(newvalue);elseaddnode(newvalue,pRoot);printf("\nDo you want to enter another(y or n)");scanf(" %c",&answer); }while(totlwer(answer) == 'y');

总结

以上是生活随笔为你收集整理的二叉树 —— 创建二叉树 先序遍历 、中序遍历、后序遍历（递归方式、非递归方式）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。