急求二叉树的创建和递归遍历程序代码C++

ps：该程序包含二叉树的建立，以及前序遍历、中序遍历、后续遍历。

如有不懂，我再详解

#include<stdioh>

#include<stdlibh>

typedef

struct

node

{

char

data;

struct

node

lchild,rchild;

}binary_tree,tree;

void

creat_tree(tree

&t)

{

char

ch;

ch=getchar();

//使用if((ch=getchar())=='#')

或者ch=getchar();都只能一下子输入所有字符，而用c语言的cin可以一个个输入。

if(ch=='#')

t=NULL;

//表示空子树

else

{

t=(binary_tree)malloc(sizeof

(binary_tree));

//

如果用c++语言

t=new

binary_tree;

if(!t)

exit(1);

//exit(1)表示异常退出这个1是返回给 *** 作系统的不过在DOS好像不需要这个返回值

;exit(0)表示正常退出

t->data=ch;

creat_tree(t->lchild);

creat_tree(t->rchild);

}

}

void

pre_travel(tree

&t)

//前序遍历：根结点->左子树->右子树

{

if(t)

{

printf("%c",t->data);

pre_travel(t->lchild);

pre_travel(t->rchild);

}

}

void

mid_travel(tree

&t)

//中序遍历：左子树->根结点->右子树

{

if(t)

{

mid_travel(t->lchild);

printf("%c",t->data);

mid_travel(t->rchild);

}

}

void

post_travel(tree

&t)

//后序遍历：左子树->右子树->根结点

{

if(t)

{

post_travel(t->lchild);

post_travel(t->rchild);

printf("%c",t->data);

}

}

void

main()

{

tree

t;

printf("输入二叉树的数据(#

代表

空子树)

比如:

fca##db###e#gh##p##\n");

creat_tree(t);

printf("前序遍历:\n");

pre_travel(t);

printf("\n");

printf("中序遍历:\n");

mid_travel(t);

printf("\n");

printf("后续遍历:\n");

post_travel(t);

printf("\n");

}

完整程序自己写吧，我提供个思路：

二叉树的节点包含三个指针：左指针，右指针，字符串链表的头指针；

构造一个通过两个字符串的头指针比较字符窜大小的函数；（先比较串长，再从头对位开始比较）；

构造一个插入函数（递归）

最后查找函数（递归）返回查找元素距根的距离；

typedef char DataType;//给char起个别名 DataType

//定义二叉树的数据结构

typedef struct node{

DataType data;//二叉树存储的数据

struct node lchild, rchild;//二叉树的左、右子树的指针

}BinTNode;

typedef BinTNode BinTree ; //自定义一个数据类型（二叉树的指针类型）

#include <stdioh>

#include <malloch>

//以前序遍历构建二叉树

void CreatBinTree(BinTree T)

{

char ch;//定义临时变量ch，用来接受数据

if ((ch=getchar())==' ')

T=NULL;//如果输入为空，则停止构建二叉树

else{T=(BinTNode )malloc(sizeof(BinTNode));//为二叉树分配内存空间

(T)->data=ch;//把输入的数据存入二叉树

CreatBinTree(&(T)->lchild);//构建左子树（递归）

CreatBinTree(&(T)->rchild);//构建左子树（递归）

}

}

//求二叉树的结点数

int Node(BinTree T)

{ int static nodes=0;//定义一个变量存储二叉树的结点数

if(T)//如果二叉树不为空（是结点），执行此语句

{

Node(T->lchild);//看左子树是不是个结点（递归）

nodes++;//结点数加1

Node(T->rchild);//看右子树是不是个结点（递归）

}

return nodes;//返回结点数

}

//求二叉树的叶子数

int Leaf(BinTree T)

{ int static leaves=0;//定义一个变量存储二叉树的叶子数

if(T)//如果二叉树不为空，执行此语句

{

Leaf(T->lchild);//看左子树是不是叶子（递归）

if(!(T->lchild||T->rchild))//如果二叉树T的左、右结点都为空，则执行此语句（即是叶子）

leaves++;//叶子数加1

Leaf(T->rchild);//看右子树是不是叶子（递归）

}

return leaves;//返回叶子数

}

#include <stdioh>

void main()

{ BinTree root;

CreatBinTree(&root);//构建二叉树

int nodes=Node(root);//求此二叉树的结点数

int leaves=Leaf(root);//求此二叉树的叶子数

printf("\nnodes=%d leaves=%d",nodes,leaves);

}

上面是我的理解，好久没有写过代码了，如有错误，请指出。

#include <stdioh>

#include <stdlibh>

typedef struct {

char data;

int weight;

} bitree_data_t;

typedef struct bitree

{

bitree_data_t data;

struct bitree lchild, rchild;

}bitree_t;

typedef bitree_t data_t;

typedef struct linknode {

data_t data;

struct linknode next;

}linknode_t, linkstack_t, linklist_t;

//创建一个链表

//1 在内存总开辟头结点的空间malloc

//2 将头结点的next域置空NULL

//3 返回创建并设置好的链表的首地址

linklist_t create_linklist()

{

linknode_t node = (linknode_t )malloc(sizeof(linknode_t));

node->next = NULL;

return node;

}

//判断当前链表是否为空

int empty_linklist(linklist_t ll)

{

return ll->next == NULL;

}

//求链表中当前有效元素的个数

int length_linklist(linklist_t ll)

{

int length = 0;

while(ll->next != NULL)

{

ll = ll->next;

length++;

}

return length;

}

//获得下标为index位置的元素，成功返回0，失败返回-1

//1 判断index是否合法(部分判断)

//2 在保证ll->next 不为空的清空下，将ll的首地址向后移动index次

//3 判断ll->next 是否等于空，如果等于空，则返回-1，如果不为空，执行4

//4 当移动了index次之后，当前ll->next 的位置的节点就保存了我要获得的

//数据

//5 data = ll->next->data;

//6 返回0

int get_linklist(linklist_t ll, int index, data_t data)

{

int i;

if(index < 0)

return -1;

for(i = 0; ll->next != NULL && i < index; i++)

{

ll = ll->next;

}

if(ll->next == NULL)

return -1;

data = ll->next->data;

return 0;

}

//使用头插法插入一个元素

//1 创建一个节点node

//2 将要插入的数据保存到node

//3 执行插入 *** 作

//4 返回0

int insert_linklist(linklist_t ll, data_t data)

{

linknode_t node = (linknode_t )malloc(sizeof(linknode_t));

node->data = data;

node->next = ll->next;

ll->next = node;

return 0;

}

//删除链表中的一个节点:删除头结点的后一个位置(头删法)

//首先可以判断当前链表是否为空，如果为空返回-1

//如果不为空则删除头结点的下一个位置的节点

//最后返回0

int delete_linklist(linklist_t ll)

{

linknode_t node;

if(empty_linklist(ll))

return -1;

node = ll->next;

ll->next = node->next;

free(node);

return 0;

}

//清空链表

//循环删除链表的一个节点，然后判断删除函数的返回值是否为0

//如果为0，继续删除，如果为-1则停止循环

int clear_linklist(linklist_t ll)

{

while(delete_linklist(ll) == 0);

return 0;

}

//销毁链表

//1 调用清空 *** 作清空链表

//2 删除头结点

//3 返回0

int detory_linklist(linklist_t ll)

{

clear_linklist(ll);

free(ll);

return 0;

}

void preorder(bitree_t root)

{

if(root == NULL)

return ;

printf("[%c,%d]", root->datadata, root->dataweight);

preorder(root->lchild);

preorder(root->rchild);

return;

}

int insert_order_linklist(linklist_t ll, data_t data)

{

linknode_t node = (linknode_t )malloc(sizeof(linknode_t));

node->data = data;

while(ll->next != NULL && ll->next->data->dataweight < node->data->dataweight)

{

ll = ll->next;

}

node->next = ll->next;

ll->next = node;

return 0;

}

bitree_t huffman_bitree(linklist_t ll)

{

bitree_t node1, node2, root;

while(ll->next != NULL && ll->next->next != NULL)

{

get_linklist(ll, 0, &node1);

delete_linklist(ll);

get_linklist(ll, 0, &node2);

delete_linklist(ll);

root = (bitree_t )malloc(sizeof(bitree_t));

root->datadata = '#';

root->dataweight = node1->dataweight + node2->dataweight;

root->lchild = node1;

root->rchild = node2;

insert_order_linklist(ll, &root);

}

get_linklist(ll, 0, &root);

delete_linklist(ll);

return root;

}

int main(void)

{

bitree_data_t data;

bitree_t leaf;

linklist_t ll;

ll = create_linklist();

while(scanf("[%c,%d]", &datadata, &dataweight) == 2)

{

getchar();

leaf = (bitree_t )malloc(sizeof(bitree_t));

leaf->lchild = leaf->rchild = NULL;

leaf->data = data;

insert_order_linklist(ll, &leaf);

}

leaf = huffman_bitree(ll);

preorder(leaf);

putchar(10);

return 0;

}

以上就是关于急求二叉树的创建和递归遍历程序代码C++全部的内容，包括:急求二叉树的创建和递归遍历程序代码C++、C语言二叉树的建立完整程序谢谢！！！、二叉树的C语言程序求教等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！