C/C++知识点之c语言代码实现二叉树

本文主要向大家介绍了C/C++知识点之c语言代码实现二叉树，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

c语言代码实现二叉树

#include<stdlib.h> //二叉树的节点定义 typedefstructTreeNode { charch;//数据域 structTreeNode*lchild;//左孩子 structTreeNode*rchild;//右孩子 }BTNode,*PBTNode;

//先序构造二叉树 voidcreateBTree(PBTNode*root) { charch; ch=getchar(); if(ch=='#') *root=NULL; else{ *root=(PBTNode)malloc(sizeof(BTNode)); (*root)->ch=ch; (*root)->lchild=NULL; (*root)->rchild=NULL; createBTree(&(*root)->lchild); createBTree(&(*root)->rchild); } }

//先序遍历二叉树 voidpreOrder(PBTNoderoot) { if(root==NULL) return; printf("%-3c",root->ch); preOrder(root->lchild); preOrder(root->rchild); }

//中序遍历二叉树 voidinOrder(PBTNoderoot) { if(root==NULL) return; preOrder(root->lchild); printf("%-3c",root->ch); preOrder(root->rchild); }

//后序遍历二叉树 voidpostOrder(PBTNoderoot) { if(root==NULL) return; preOrder(root->lchild); preOrder(root->rchild); printf("%-3c",root->ch); }

//输出叶子结点 voiddisplyLeaf(PBTNoderoot) { if(root==NULL) return; if(root->lchild==NULL&&root->rchild==NULL) printf("%-3c",root->ch); else{ displyLeaf(root->lchild); displyLeaf(root->rchild); } }

//左结点插入 voidinseartLeftNode(PBTNoderoot,charch) { PBTNodep,newNode; if(root==NULL) return; p=root->lchild; newNode=(PBTNode)malloc(sizeof(BTNode)); newNode->ch=ch; newNode->rchild=NULL; newNode->lchild=p; root->lchild=newNode; }

//右结点插入 voidinseartRightNode(PBTNoderoot,charch) { PBTNodep,newNode; if(root==NULL) return; p=root->rchild; newNode=(PBTNode)malloc(sizeof(BTNode)); newNode->ch=ch; newNode->lchild=NULL; newNode->rchild=p; root->rchild=newNode; }

//销毁一颗二叉树 voidclear(PBTNode*root) { PBTNodepl,pr; if(*root==NULL) return; pl=(*root)->lchild; pr=(*root)->rchild; (*root)->lchild=NULL; (*root)->rchild=NULL; free((*root)); *root=NULL; clear(&pl); clear(&pr); }

//删除左子树 voiddeleteLeftTree(PBTNoderoot) { if(root==NULL) return; clear(&root->lchild); root->lchild=NULL; }

//删除右子树 voiddeleteRightTree(PBTNoderoot) { if(root==NULL) return; clear(&root->rchild); root->rchild=NULL; }

//查找结点 PBTNodesearch(PBTNoderoot,charch) { PBTNodep; if(root==NULL) returnNULL; if(root->ch==ch) returnroot; else{ if((p=search(root->lchild,ch))!=NULL) returnp; else returnsearch(root->rchild,ch); } }

//求二叉树的高度 intBTreeHeight(PBTNoderoot) { intlchildHeight,rchildHeight; if(root==NULL) return0; lchildHeight=BTreeHeight(root->lchild); rchildHeight=BTreeHeight(root->rchild); return(lchildHeight>rchildHeight)?(1+lchildHeight):(1+rchildHeight); }

//求叶子结点的个数 intcountLeaf(PBTNoderoot) { if(root==NULL) return0; if(root->lchild==NULL&&root->rchild==NULL) return1; else{ returncountLeaf(root->lchild)+countLeaf(root->rchild); } }

//求所有结点的个数 intcountAll(PBTNoderoot) { if(root==NULL) return0; returncountAll(root->lchild)+countAll(root->rchild)+1; }

//复制二叉树 PBTNodecopyBTree(PBTNoderoot) { PBTNodep,lchild,rchild; if(root==NULL) returnNULL; lchild=copyBTree(root->lchild); rchild=copyBTree(root->rchild); p=(PBTNode)malloc(sizeof(BTNode)); p->ch=root->ch; p->lchild=lchild; p->rchild=rchild; returnp; }

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！