构造二叉树及其基本操作

港控/mmm° 2021-07-16 19:07 407阅读 0赞

**二叉树的基本操作如下**

**构造一棵二叉树**

运用递归，从二叉树的根结点出发，先构造左子树再构造右子树，当输入"\#"表示为空，跳回上一层。

BiNode* BiTree::Create()
    { 
    	BiNode* bt;
    	datatype ch;
    	cin >> ch;
    	if (ch == '#')bt = NULL;
    	else
    	{ 
    		bt = new BiNode;
    		bt->data = ch;
    		bt->lchild = Create();
    		bt->rchild = Create();
    	}
    	return bt;
    }

**二叉树的前中后序的递归遍历**  
其实就是输出根结点的位置为前中后。

void BiTree::PreOrder(BiNode* bt)
    { 
    	if (bt == NULL)return;
    	else
    	{ 
    		cout << bt->data << endl;
    		PreOrder(bt->lchild);
    		PreOrder(bt->rchild);
    	}
    }
    
    void BiTree::InOrder(BiNode* bt)
    { 
    	if (bt == NULL)return;
    	else
    	{ 
    		InOrder(bt->lchild);
    		cout << bt->data << endl;
    		InOrder(bt->rchild);
    	}
    }
    
    void BiTree::PostOrder(BiNode* bt)
    { 
    	if (bt == NULL)return;，
    	else
    	{ 
    		PostOrder(bt->lchild);
    		PostOrder(bt->rchild);
    		cout << bt->data << endl;
    	}
    }

**二叉树的非递归前序遍历**  
首先我们需要一个栈，先将root入栈，然后出栈（此时出的就是root）输出，如果有右结点则入右结点，有左节点则入左节点，注意顺序，因为是前序遍历所以让右结点先入左结点后入，这样会保证左结点先出栈，循环直到栈空。

void BiTree::IterativePreorder()
    { 
    	BiNode* stack[Max];
    	int top = -1;
    	if (root == NULL)return;
    	stack[++top] = root;
    	while (top!=-1)
    	{ 
    		BiNode* p = stack[top];
    		cout << p->data << endl;
    		top--;
    		if (p->rchild != NULL)stack[++top] = p->rchild;
    		if (p->lchild != NULL)stack[++top] = p->lchild;
    	}
    }

**二叉树的层序遍历**  
需要用到一个队列，先将根结点入队。然后将队列中的队首元素（这时就是根结点）出队、输出，再把当前出队结点的左右子节点压入队列（如果左右结点不为空的话），循环直到队列为空。

在这里插入代码片void BiTree::LevelOrder()
    { 
    	BiNode* Q[Max], * q = NULL;
    	int front = -1, rear = -1;
    	if (root == NULL) return;
    	Q[++rear] = root;
    	while (front != rear)
    	{ 
    		q = Q[++front];
    		cout << q->data << endl;
    		if (q->lchild != NULL)Q[++rear] = q->lchild;
    		if (q->rchild != NULL)Q[++rear] = q->rchild;
    	}
    }

**求二叉树的高度**  
DFS，先一直往左走直到尽头，再跳回往右，把所有路径遍历一遍比较得出最大的高度。

int h=0,ht=0;
    void BiTree::get_high(BiNode* bt)
    { 
    	ht++;
    	if (bt == NULL)return;
    	if (bt->lchild == NULL && bt->rchild == NULL)
    	{ 
    		h = max(h, ht);
    		return;
    	}
    	get_high(bt->lchild);
    	ht--;
    	get_high(bt->rchild);
    	ht--;
    }

**求二叉树度为0、度为1、度为2的结点的个数**  
DFS将二叉树遍历一遍，看其左右结点是否为空逐一记录各度的结点数。

int d1=0, d2=0, d0=0;
    void BiTree::get_node(BiNode* bt)
    { 
    	if (bt->lchild != NULL && bt->rchild != NULL)
    	{ 
    		d2++;
    		get_node(bt->lchild);
    		get_node(bt->rchild);
    	}
    	else if (bt->lchild!=NULL)
    	{ 
    		d1++;
    		get_node(bt->lchild);
    	}
    	else if (bt->rchild != NULL)
    	{ 
    		d1++;
    		get_node(bt->rchild);
    	}
    	else
    	{ 
    		d0++;
    		return;
    	}
    }

总代码

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<queue>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    typedef char datatype;
    const int Max = 1e3 + 5;
    int h=0,ht=0, d1=0, d2=0, d0=0;
    
    struct BiNode
    { 
    	datatype data;
    	BiNode *lchild, *rchild;
    };
    BiNode* fa;
    class BiTree
    { 
    public:
    	BiTree() {  root = Create(); }
    	void PreOrder() {  PreOrder(root); }
    	void InOrder() {  InOrder(root); }
    	void PostOrder() {  PostOrder(root); }
    	void LevelOrder();
    	void IterativePreorder();
    	void get_high() {  h = 0;get_high(root); }
    	void get_node() {  d0 = d1 = d2 = 0;get_node(root); }
    	void get_width();
    private:
    	BiNode* Create();
    	void Release(BiNode* bt);
    	void PreOrder(BiNode* bt);
    	void InOrder(BiNode* bt);
    	void PostOrder(BiNode* bt);
    	void get_high(BiNode* bt);
    	void get_node(BiNode* bt);
    	BiNode* root;
    };
    
    void BiTree::IterativePreorder()
    { 
    	BiNode* stack[Max];
    	int top = -1;
    	if (root == NULL)return;
    	stack[++top] = root;
    	while (top!=-1)
    	{ 
    		BiNode* p = stack[top];
    		cout << p->data << endl;
    		top--;
    		if (p->rchild != NULL)stack[++top] = p->rchild;
    		if (p->lchild != NULL)stack[++top] = p->lchild;
    	}
    }
    
    void BiTree::get_node(BiNode* bt)
    { 
    	if (bt->lchild != NULL && bt->rchild != NULL)
    	{ 
    		d2++;
    		get_node(bt->lchild);
    		get_node(bt->rchild);
    	}
    	else if (bt->lchild!=NULL)
    	{ 
    		d1++;
    		get_node(bt->lchild);
    	}
    	else if (bt->rchild != NULL)
    	{ 
    		d1++;
    		get_node(bt->rchild);
    	}
    	else
    	{ 
    		d0++;
    		return;
    	}
    }
    
    void BiTree::get_high(BiNode* bt)
    { 
    	ht++;
    	if (bt == NULL)return;
    	if (bt->lchild == NULL && bt->rchild == NULL)
    	{ 
    		h = max(h, ht);
    		return;
    	}
    	get_high(bt->lchild);
    	ht--;
    	get_high(bt->rchild);
    	ht--;
    }
    
    void BiTree::PreOrder(BiNode* bt)
    { 
    	if (bt == NULL)return;
    	else
    	{ 
    		cout << bt->data << endl;
    		PreOrder(bt->lchild);
    		PreOrder(bt->rchild);
    	}
    }
    
    void BiTree::InOrder(BiNode* bt)
    { 
    	if (bt == NULL)return;
    	else
    	{ 
    		InOrder(bt->lchild);
    		cout << bt->data << endl;
    		InOrder(bt->rchild);
    	}
    }
    
    void BiTree::PostOrder(BiNode* bt)
    { 
    	if (bt == NULL)return;
    	else
    	{ 
    		PostOrder(bt->lchild);
    		PostOrder(bt->rchild);
    		cout << bt->data << endl;
    	}
    }
    
    void BiTree::LevelOrder()
    { 
    	BiNode* Q[Max], * q = NULL;
    	int front = -1, rear = -1;
    	if (root == NULL) return;
    	Q[++rear] = root;
    	while (front != rear)
    	{ 
    		q = Q[++front];
    		cout << q->data << endl;
    		if (q->lchild != NULL)Q[++rear] = q->lchild;
    		if (q->rchild != NULL)Q[++rear] = q->rchild;
    	}
    }
    
    BiNode* BiTree::Create()
    { 
    	BiNode* bt;
    	datatype ch;
    	cin >> ch;
    	if (ch == '#')bt = NULL;
    	else
    	{ 
    		bt = new BiNode;
    		bt->data = ch;
    		bt->lchild = Create();
    		bt->rchild = Create();
    	}
    	return bt;
    }

码字不易给个赞吧QAQ