您好，想要实现一个二叉树，需要用到结构体来存储每个节点的信息，并使用指针来存储每个节点的左右子节点的地址。具体的实现方法可以参考下面的代码示例：
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val
struct TreeNode *left
struct TreeNode *right
}
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode))
node->val = val
node->left = NULL
node->right = NULL
return node
}
void insertNode(struct TreeNode* root, int val) {
if (root == NULL) {
return
}
if (val <root->val) {
if (root->left == NULL) {
root->left = createNode(val)
} else {
insertNode(root->left, val)
}
} else {
if (root->right == NULL) {
root->right = createNode(val)
} else {
insertNode(root->right, val)
}
}
}
void printTree(struct TreeNode* root) {
if (root == NULL) {
return
}
printf("%d\n", root->val)
printTree(root->left)
printTree(root->right)
}
int main() {
struct TreeNode* root = createNode(5)
insertNode(root, 3)
insertNode(root, 2)
insertNode(root, 4)
insertNode(root, 7)
insertNode(root, 6)
insertNode(root, 8)
printTree(root)
return 0
}
在这段代码中，我们定义了一个结构体 TreeNode 来表示二叉树的每个节点，结构体中包含了一个节点的数值 val，以及指向左子节点和右子节点的指针 left 和 right。
/*二叉树的基本运算与实现*/#include <stdio.h>
#include <malloc.h>
#define MAXNODE 256
typedef int datatype
typedef struct BiTNode
{
datatype data
struct BiTNode *lchild,*rchild
}BiTNode,*BiTree
typedef struct
{
BiTree link
int flag
}stacktypevoid menu()
int Initiate(BiTree *bt,datatype x)
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
BiTree DeleteL(BiTree bt,BiTree parent)
BiTree DeleteR(BiTree bt,BiTree parent)
void PreOrder(BiTree bt)
void InOrder(BiTree bt)
void PostOrder(BiTree bt)
void LevelOrder(BiTree bt)
BiTree Find(BiTree parent,datatype a)
void NRPreOrder(BiTree bt)
void NRInOrder(BiTree bt)
void NRPostOrder(BiTree bt)void main()
{
int n,m=1
BiTree t/*clrscr()*/
while(m)
{
menu()
scanf("%d",&n)
switch(n)
{
case 1:{/*初始化*/
int flag
datatype x
printf("please input head point x:\n")
scanf("%d",&x)
flag=Initiate(&t,x)
if(flag==1)
printf("\nInitiate success!")
else
printf("\nInitiate fail!")
break
}
case 2:{/*建树*/
break
}
case 3:{/*插入结点x作为a的左孩子*/
datatype a,x/*x作为a的左孩子*/
BiTree parent=t
printf("please input a and x:\n")
scanf("%d%d",&a,&x)
parent=Find(parent,a)
parent=InsertL(t,x,parent)
if(parent!=NULL)
t=parent
break
}
case 4:{/*插入结点x作为a的右孩子*/
datatype a,x/*x作为a的右孩子*/
BiTree parent=t
printf("please input a and x:\n")
scanf("%d%d",&a,&x)
parent=Find(parent,a)
parent=InsertR(t,x,parent)
if(parent!=NULL)
t=parent
break
}
case 5:{/*删除结点a的左孩子*/
datatype a
BiTree parent=t
printf("please input a:\n")
scanf("%d",&a)
parent=Find(parent,a)
parent=DeleteL(t,parent)
if(parent!=NULL)
t=parent
break
}
case 6:{/*删除结点a的左孩子*/
datatype a
BiTree parent=t
printf("please input a:\n")
scanf("%d",&a)
parent=Find(parent,a)
parent=DeleteR(t,parent)
if(parent!=NULL)
t=parent
break
}
PreOrder(t)
break
}
case 8:{/*递归中序遍历*/
InOrder(t)
break
}
case 9:{/*递归后序遍历*/
PostOrder(t)
break
}
case 10:{/*层次遍历*/
LevelOrder(t)
break
}
case 11:{/*先序遍历的非递归实现*/
NRPreOrder(t)
break
}
case 12:{/*中序遍历的非递归实现*/
NRInOrder(t)
break
}
case 13:{/*后序遍历的非递归实现*/
NRPostOrder(t)
break
}
case 0:m=0
}
}
}
void menu()
{
/*clrscr()*/
printf("\n")
printf("\t\t1.initiate\n\n")
printf("\t\t2.create thread\n\n")
printf("\t\t3.insert Left\n\n")
printf("\t\t4.insert Right\n\n")
printf("\t\t5.delete Left\n\n")
printf("\t\t6.delete Right\n\n")
printf("\t\t7.preorder\n\n")
printf("\t\t8.inorder\n\n")
printf("\t\t9.postorder\n\n")
printf("\t\t10.levelorder\n\n")
printf("\t\t11.nrpreorder\n\n")
printf("\t\t12.nrinorder\n\n")
printf("\t\t13.nrpostorder\n\n")
printf("\t\t0.exit\n\n")
printf("\n\n\n\tplease select:")
}
int Initiate(BiTree *bt,datatype x)
{
if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return 0
(*bt)->data=x
(*bt)->lchild=NULL
(*bt)->rchild=NULL
return 1
}
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
{
BiTree p
if(parent==NULL)
{
printf("\nerror!\n")
return NULL
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL
p->data=x
p->lchild=NULL
p->rchild=NULL
if(parent->lchild==NULL)
parent->lchild=p
else
{
p->lchild=parent->lchild
parent->lchild=p
}
return bt
}
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
{
BiTree p
if(parent==NULL)
{
printf("\nerror!\n")
return NULL
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL
p->data=x
p->lchild=NULL
p->rchild=NULL
if(parent->rchild==NULL)
parent->rchild=p
else
{
p->rchild=parent->rchild
parent->rchild=p
}
return bt
}
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p
if(parent==NULL||parent->lchild==NULL)
{
printf("\ndelete error!")
return NULL
}
p=parent->lchild
parent->lchild=NULL
free(p)
return bt
}
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p
if(parent==NULL||parent->rchild==NULL)
{
printf("\ndelete error!")
return NULL
}
p=parent->rchild
parent->rchild=NULL
free(p)
return bt
}
void PreOrder(BiTree bt)
{
if(bt==NULL)
return
printf("%5d",bt->data)
PreOrder(bt->lchild)
PreOrder(bt->rchild)
}
void InOrder(BiTree bt)
{
if(bt==NULL)
return
InOrder(bt->lchild)
printf("%5d",bt->data)
InOrder(bt->rchild)
}
void PostOrder(BiTree bt)
{
if(bt==NULL)
return
PostOrder(bt->lchild)
PostOrder(bt->rchild)
printf("%5d",bt->data)
}
void LevelOrder(BiTree bt)
{
BiTree Queue[MAXNODE]
int front,rear
if(bt==NULL)
{
return
}
front = -1
rear = 0
Queue[rear] = bt
while(front!=rear)
{
front++
printf("%5d",Queue[front]->data)
if(Queue[front]->lchild!=NULL)
{
rear++
Queue[rear]=Queue[front]->lchild
}
if(Queue[front]->rchild!=NULL)
{
rear++
Queue[rear]=Queue[front]->rchild
}
}//end while
}
BiTree Find(BiTree parent,datatype a)
{
BiTree p
if(parent==NULL)
p=NULL
else if(parent->data==a)
p=parent
else
{
p=Find(parent->lchild,a)
if(p==NULL)
p=Find(parent->rchild,a)
}
return p
}
void NRPreOrder(BiTree bt)
{
BiTree stack[MAXNODE],p
int top
if(bt==NULL)
{
printf("Tree is empty!\n")
return
}
top=-1
p=bt
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
printf("%5d",p->data)
if(top==MAXNODE-1)
{
printf("Stack overflow!\n")
return
} /* end if */
else
{
top++
stack[top]=p
} /* end if-else */
p=p->lchild
} /* end while p */
p=stack[top]
top--
p=p->rchild
} /* end while p &&top */
}
void NRInOrder(BiTree bt)
{
BiTree stack[MAXNODE],p
int top
if(bt==NULL)
{
printf("Tree is empty!\n")
return
}
top=-1
p=bt
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
if(top==MAXNODE-1)
{
printf("Stack overflow!\n")
return
} /* end if */
else
{
top++
stack[top]=p
} /* end if-else */
p=p->lchild
} /* end while p */
p=stack[top]
top--
printf("%5d",p->data)
p=p->rchild
} /* end while p &&top */
}
void NRPostOrder(BiTree bt)
{
stacktype stack[MAXNODE]
BiTree p
int top,sign
if(bt==NULL)
{
printf("Tree is empty!\n")
return
}
top=-1
p=bt
while((p!=NULL)||(top!=-1))
{
if(p!=NULL) /*结点第一次入栈*/
{
top++
stack[top].link=p
stack[top].flag=1/*标记第一次入栈*/
p=p->lchild
} /* end if */
else
{
p=stack[top].link
sign=stack[top].flag
top--
if(sign==1) /*结点第二次入栈*/
{
top++
stack[top].link=p
stack[top].flag=2/*标记第二次入栈*/
p=p->rchild
} /* end if */
else
{
printf("%5d",p->data)
p=NULL
} /* end if-else */
} /* end if-else */
} /* end while */
}
