二叉树的建立，删除，查找，插入，输出（数据结构）

秒速五厘米 2022-06-09 07:10 195阅读 0赞

#     #

# 1. 建立二叉树 #

void pre_crt(tree &bt)//按先序顺序输入二叉树中节点的值，生成
    {
    	char ch;
    	ch=getchar();//二叉树的单链表存储结构，bt为指向根节点的指针，,'$'表示空树 
     	if(ch!='$')
    	 {
    	 	bt=new node;//建根节点
    		bt->data=ch;
    		pre_crt(bt->lchild);
    		pre_crt(bt->rchild); 
    	 }
    	 else bt=NULL; 
    }

# 2. 删除节点 #

void dis(tree &bt)
    {
    	if(bt)
    	{
    		dis(bt->lchild);//删左子树
    		dis(bt->rchild);//删右子树
    		delete bt;//释放父节点 
    	}
    }

#     #

# 3. 在二叉排序树中插入一个数 #

**二叉排序树**又称“二叉查找树”、“二叉搜索树”。（左小右大）[http://www.cnblogs.com/zhuyf87/archive/2012/11/09/2763113.html][http_www.cnblogs.com_zhuyf87_archive_2012_11_09_2763113.html]

二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 它的左、右子树也分别为二叉排序树。

![2012110918051618.jpg][]

二叉排序树通常采用二叉链表作为存储结构。

void insert(tree &bt,int n)//插入一个节点到排序二叉树中 
    {
    	if(bt)
    	{
    		if(n<bt->data) insert(bt->lchild,n);
    		else if(n>bt->data) insert(bt->rchild,n); 
    	}
    	else
    	{
    		bt=new node;//新开一个空间
    		bt->data=n;
    		bt->lchild=bt->rchild=NULL; 
    	}
    }

# 4. 在二叉排序树中查找一个数 #

找到返回该节点，否则返回NULL

tree findn(tree bt,int n)
    {
    	if(bt)
    	{
    		if(n<bt->data) findn(bt->lchild,n);
    		else if(n>bt->data) findn(bt->rchild,n);
    		else return bt;
    	}
    	else return NULL;
    }

# 5. 用嵌套括号表示法输出一棵二叉树 #

void print(tree bt)
    {
    	if(bt)
    	{
    		cout<<bt->data;
    		if(bt->lchild||bt->rchild)
    		{
    			cout<<'(';
    			print(bt->lchild);
    			if(bt->rchild) cout<<',';
    			print(bt->rchild);
    			cout<<')';
    		}
    	}
    }

结论：已知先序序列和中序序列可以确定出二叉树；

已知中序序列和后序序列也可以确定出二叉树；

但，已知先序序列和后序序列却不可以确定出二叉树；

![20170830182721196][]

例如：已知结点的先序序列为ABCDEFG，中序序列为CBEDAFG。可以唯一构造出二叉树。过程见下图：

![20170830180640949][]

[http_www.cnblogs.com_zhuyf87_archive_2012_11_09_2763113.html]: http://www.cnblogs.com/zhuyf87/archive/2012/11/09/2763113.html
[2012110918051618.jpg]: /images/20220609/01cb8cb60d214e08beed148ec432b6e4.png
[20170830182721196]: /images/20220609/5455764e0522467b846347854c0536c6.png
[20170830180640949]: /images/20220609/dd95c9215ca247b593e5fdd0d723614c.png