用C语言编程实现如下功能:建立二叉树,二叉树的递归遍历和非递归遍历,二叉树的高度,结点查找等运算。
时间: 2024-03-01 20:23:56 浏览: 29
好的,您想要实现的是二叉树的基本运算,这个问题需要用到C语言中的数据结构和算法知识。以下是简单的实现方案:
1. 建立二叉树:
可以采用递归的方式实现建立二叉树,先输入二叉树的根节点值,然后递归地输入左右子树:
```
typedef struct treeNode{
int data;
struct treeNode *left;
struct treeNode *right;
}TreeNode;
TreeNode* CreateBiTree(){
TreeNode *T;
int ch;
scanf("%d",&ch);
if(ch==-1){
T=NULL;
}else{
T=(TreeNode *)malloc(sizeof(TreeNode));
T->data=ch;
T->left=CreateBiTree();
T->right=CreateBiTree();
}
return T;
}
```
2. 二叉树递归遍历:
二叉树递归遍历包括先序遍历、中序遍历和后序遍历,分别使用递归实现:
```
void PreOrder(TreeNode* root){
if(root){
printf("%d ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}
}
void InOrder(TreeNode* root){
if(root){
InOrder(root->left);
printf("%d ",root->data);
InOrder(root->right);
}
}
void PostOrder(TreeNode* root){
if(root){
PostOrder(root->left);
PostOrder(root->right);
printf("%d ",root->data);
}
}
```
3. 二叉树非递归遍历:
二叉树非递归遍历需要借助栈存放遍历过程中的节点,以下是二叉树中序遍历的非递归实现:
```
void InOrderNonRecursive(TreeNode *root){
stack<TreeNode *> s;
TreeNode *p=root;
while(!s.empty() || p){
if(p){
s.push(p);
p=p->left;
}else{
p=s.top();
s.pop();
printf("%d ",p->data);
p=p->right;
}
}
}
```
4. 二叉树高度:
二叉树的高度可以采用递归的方式实现:
```
int Height(TreeNode* root){
if(root==NULL) return 0;
int left_height=Height(root->left);
int right_height=Height(root->right);
return max(left_height,right_height)+1;
}
```
5. 结点查找:
二叉树结点查找可以采用递归的方式实现,对于当前结点,如果等于待查找的值,返回true,否则递归到左右子树中查找:
```
bool Search(TreeNode* root,int val){
if(root==NULL) return false;
if(root->data==val) return true;
return Search(root->left,val) || Search(root->right,val);
}
```
以上就是基本的二叉树运算实现方案,您可以根据需求进行修改和完善。