linux 递归创建线程 [linux]二叉树的建立及其递归遍历（C语言实现)

#二叉树的特点：

每一个节点最多有两棵子树，所以二叉树中不存在度大于2的节点，注意，是最多有两棵，没有也是可以的 左子树和右子树是有顺序的，次序不能颠倒，这点可以在哈夫曼编码中体现， 顺序不同编码方式不同

-即使树中某个节点中只有一个子树的花，也要区分它是左子树还是右子树

二叉树一般有五种形态 1.空二叉树 2.只有一个根节点 3.根结点只有左子树 4.根节点只有右子树

#二叉树的性质 1：在二叉树的第i层上最多有2^i-1个节点 2：深度为K的二叉树之多有2^k-1个节点

这里的深度K意思就是有K层的二叉树 3：对于任何一棵二叉树T，如果其终端节点有No个，度为2的节点数有N2，则No=N2+1 4: 具有n个节点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数)

#1.二叉树的存储结构(二叉链表)

//二叉树的存储结构，一个数据域，2个指针域

typedef struct BiTNode

{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

#2.首先要建立一个二叉树，建立二叉树必须要了解二叉树的遍历方法。，我在这里展示的是二叉树的递归建立方式

//我在这里实现的是，二叉树的前序遍历方式创建，如果要使用中序或者后序的方式建立二叉树，只需将生成结点和构造左右子树的顺序改变即可

void CreateBiTree(BiTree *T)

{

char ch;

scanf("%c",&ch);

if(ch=='#')

*T=NULL;

else

{

*T=(BiTree )malloc(sizeof(BiTNode));

if(!*T)

exit(-1);

(*T)->data=ch;

CreateBiTree(&(*T)->lchild);

CreateBiTree(&(*T)->rchild);

}

}

#3.二叉树的遍历方式(递归建立)

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);

}

#mac环境代码实现(完整代码)

#include

#include

typedef struct BiTNode

{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

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);

}

void CreateBiTree(BiTree *T)

{

char ch;

scanf("%c",&ch);

if(ch=='#')

*T=NULL;

else

{

*T=(BiTree )malloc(sizeof(BiTNode));

if(!*T)

exit(-1);

(*T)->data=ch;

CreateBiTree(&(*T)->lchild);

CreateBiTree(&(*T)->rchild);

}

}

void pri(){

printf("\n");

}

int main()

{

BiTree T;

printf("输入树(#代表空节点 AB#C##D##):");

CreateBiTree(&T);

printf("前序遍历的结果是:");

PreOrderTraverse (T);

printf("\n中序遍历的结果是:");

InOrderTraverse(T);

printf("\n后序遍历的结果是:");

PostOrderTraverse(T);

pri();

return 0;

}